समन्वय वंश

समन्वय वंश अनुकूलन कलनविधि है जो किसी फलन के न्यूनतम को खोजने के लिए क्रमिक रूप से समन्वयित दिशाओं को कम करता है। प्रत्येक पुनरावृत्ति पर, कलनविधि समन्वय प्रणाली को निर्धारित करता है या समन्वय चयन नियम के माध्यम से समन्वय ब्लॉक करता है, फिर अन्य सभी निर्देशांक या समन्वय ब्लॉकों को ठीक करते समय संबंधित समन्वय हाइपरप्लेन पर ठीक या अनुचित विधि से कम करता है। उपयुक्त चरण आकार निर्धारित करने के लिए समन्वय प्रणाली दिशा के साथ लाइन खोज वर्तमान पुनरावृति पर की जा सकती है। समन्वय अवरोहण अलग-अलग और व्युत्पन्न-मुक्त दोनों संदर्भों में प्रयुक्त होता है।

विवरण

समन्वय वंश इस विचार पर आधारित है कि बहुभिन्नरूपी कार्य का न्यूनीकरण $F(\mathbf {x} )$ इसे एक समय में एक दिशा में कम से कम करके प्राप्त किया जा सकता है, अर्थात, लूप में अविभाज्य (या कम से कम बहुत सरल) अनुकूलन समस्याओं का समाधान करना। चक्रीय समन्वय अवतरण के सबसे सरल स्थिति में, एक समय में एक दिशा के माध्यम से चक्रीय रूप से पुनरावृत्ति करता है, समय में प्रत्येक समन्वय दिशा के संबंध में उद्देश्य समारोह को कम करता है। यही है, प्रारंभिक चर मानों से प्रारंभ करना

$\mathbf {x} ^{0}=(x_{1}^{0},\ldots ,x_{n}^{0})$,

गोल $k+1$, $\mathbf {x} ^{k+1}$ से $\mathbf {x} ^{k}$ को एकल चर अनुकूलन समस्याओं को क्रमिक रूप से समाधान करके परिभाषित करता है

$x_{i}^{k+1}={\underset {y\in \mathbb {R} }{\operatorname {arg\,min} }}\;f(x_{1}^{k+1},\dots ,x_{i-1}^{k+1},y,x_{i+1}^{k},\dots ,x_{n}^{k})$

प्रत्येक चर $x_{i}$ का $\mathbf {x}$ के लिए, $i$ 1 से $n$.

इस प्रकार, प्रारंभिक अनुमान के साथ प्रारंभ होता है $\mathbf {x} ^{0}$ स्थानीय न्यूनतम के लिए $F$, और अनुक्रम $\mathbf {x} ^{0},\mathbf {x} ^{1},\mathbf {x} ^{2},\dots$ पुनरावृत्त रूप से प्राप्त करता है

प्रत्येक पुनरावृत्ति में लाइन खोज करने से, स्वचालित रूप से होता है

$F(\mathbf {x} ^{0})\geq F(\mathbf {x} ^{1})\geq F(\mathbf {x} ^{2})\geq \dots .$

यह दिखाया जा सकता है कि इस अनुक्रम में समान अभिसरण गुण हैं जैसे कि सबसे तेज वंश। समन्वय दिशाओं के साथ लाइन खोज के चक्र के बाद कोई संशोधन नहीं होने का अर्थ है कि स्थिर बिंदु तक पहुंच गया है।

यह प्रक्रिया नीचे सचित्र है।

अलग स्थिति

निरंतर भिन्न कार्य F के स्थिति में, समन्वय वंश कलनविधि को इस रूप में स्केच किया जा सकता है:

• प्रारंभिक पैरामीटर सदिश चुनें x.
• जब तक अभिसरण नहीं हो जाता, या पुनरावृत्तियों की कुछ निश्चित संख्या के लिए:
  • एक सूचकांक चुनें i से 1 को n.
  • कदम का आकार चुनें α.
  • अद्यतन x_i को x_i − α∂F/∂x_i(x).

चरण आकार को विभिन्न विधियों से चुना जा सकता है, उदाहरण के लिए, स्पष्ट न्यूनतम के लिए समाधान करके f(x_i) = F(x) (अर्थात, F लेकिन सभी चर के साथ x_i फ़िक्स्ड), या पारंपरिक लाइन खोज मानदंड द्वारा।

सीमाएं

समन्वय वंश में दो समस्याएं हैं। उनमें से गैर-चिकनापन बहुभिन्नरूपी कार्य कर रहा है। निम्नलिखित चित्र से पता चलता है कि यदि किसी फलन के स्तर वक्र सुचारू नहीं हैं, तो समन्वय वंश पुनरावृत्ति गैर-स्थिर बिंदु पर अटक सकती है। मान लीजिए कि कलनविधि बिंदु (-2, -2) पर है; फिर दो अक्ष-संरेखित दिशाएँ हैं जिन पर वह कदम उठाने के लिए विचार कर सकता है, जो लाल तीरों द्वारा इंगित किया गया है। चूँकि, इन दो दिशाओं के साथ हर कदम उद्देश्य समारोह के मूल्य में वृद्धि करेगा (न्यूनतमकरण समस्या मानते हुए), इसलिए कलनविधि कोई कदम नहीं उठाएगा, तथापि दोनों कदम एक साथ कलनविधि को इष्टतम के निकट लाएंगे। चूँकि इस उदाहरण से पता चलता है कि समन्वय वंश आवश्यक रूप से इष्टतम के लिए अभिसरण नहीं है, उचित परिस्थितियों में औपचारिक अभिसरण दिखाना संभव है।

दूसरी समस्या, समांतरता में कठिनाई है। चूंकि समन्वय वंश की प्रकृति दिशाओं के माध्यम से चक्रित करना है और प्रत्येक समन्वय दिशा के संबंध में वस्तुनिष्ठ कार्य को कम करना है, इसलिए समन्वय वंश बड़े पैमाने पर समानता के लिए स्पष्ट प्रत्याशी नहीं है। हाल के शोध कार्यों से पता चला है कि बड़े पैमाने पर समानता प्रत्येक समन्वय दिशा के संबंध में वस्तुनिष्ठ कार्य के परिवर्तन को सुविधा से समन्वयित करने के लिए प्रयुक्त होती है।

अनुप्रयोग

समन्वय वंश कलनविधि अपनी सरलता के कारण चिकित्सकों के बीच लोकप्रिय हैं, लेकिन इसी गुण ने अनुकूलन शोधकर्ताओं को अधिक रोचक (जटिल) विधियों के पक्ष में बड़े पैमाने पर उनकी उपेक्षा करने के लिए प्रेरित किया है। परिकलित टोमोग्राफी के क्षेत्र में समन्वय वंश अनुकूलन का प्रारंभिक अनुप्रयोग था जहां यह शीघ्रता से अभिसरण पाया गया है और बाद में नैदानिक बहु-स्लाइस हेलिकल स्कैन सीटी पुनर्निर्माण के लिए उपयोग किया गया। प्रोटीन संरचना भविष्यवाणी में चक्रीय समन्वय वंश कलनविधि (सीसीडी) प्रयुक्त किया गया है। इसके अतिरिक्त, मशीन सीखने में बड़े पैमाने पर समस्याओं के आगमन के साथ समन्वय वंश के उपयोग में रुचि बढ़ गई है, जहां रैखिक समर्थन सदिश यंत्र को प्रशिक्षित करने जैसी समस्याओं पर प्रयुक्त होने पर समन्वय वंश को अन्य विधियों के लिए प्रतिस्पर्धी दिखाया गया है। (लिब्लिनियर और गैर-नकारात्मक आव्यूह गुणनखंडन देखें)। वे उन समस्याओं के लिए आकर्षक हैं जहां प्रवणता की गणना करना संभव नहीं है, संभवतया इसलिए कि ऐसा करने के लिए आवश्यक डेटा कंप्यूटर नेटवर्क में वितरित किया जाता है।

यह भी देखें

• अनुकूली समन्वय वंश
• संयुग्म ढाल
• ढतला हुआ वंश
• रेखा खोज
• गणितीय अनुकूलन
• अनुकूलन में न्यूटन की विधि | न्यूटन की विधि
• स्टोचैस्टिक प्रवणता डिसेंट - समन्वय के अतिरिक्त एक समय में एक उदाहरण का उपयोग करता है

संदर्भ

• Bezdek, J. C.; Hathaway, R. J.; Howard, R. E.; Wilson, C. A.; Windham, M. P. (1987), "Local convergence analysis of a grouped variable version of coordinate descent", Journal of Optimization Theory and Applications, Kluwer Academic/Plenum Publishers, vol. 54, no. 3, pp. 471–477, doi:10.1007/BF00940196, S2CID 120052975
• Bertsekas, Dimitri P. (1999). Nonlinear Programming, Second Edition Athena Scientific, Belmont, Massachusetts. ISBN 1-886529-00-0.
• Luo, Zhiquan; Tseng, P. (1992), "On the convergence of the coordinate descent method for convex differentiable minimization", Journal of Optimization Theory and Applications, Kluwer Academic/Plenum Publishers, vol. 72, no. 1, pp. 7–35, doi:10.1007/BF00939948, hdl:1721.1/3164, S2CID 121091844.
• Wu, TongTong; Lange, Kenneth (2008), "Coordinate descent algorithms for Lasso penalized regression", The Annals of Applied Statistics, Institute of Mathematical Statistics, vol. 2, no. 1, pp. 224–244, arXiv:0803.3876, doi:10.1214/07-AOAS147, S2CID 16350311.
• Richtarik, Peter; Takac, Martin (April 2011), "Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function", Mathematical Programming, Springer, vol. 144, no. 1–2, pp. 1–38, arXiv:1107.2848, doi:10.1007/s10107-012-0614-z, S2CID 16816638.
• Richtarik, Peter; Takac, Martin (December 2012), "Parallel coordinate descent methods for big data optimization", ArXiv:1212.0873, arXiv:1212.0873.

| group5 = Metaheuristics | abbr5 = heuristic | list5 =

• Evolutionary algorithm
• Hill climbing
• Local search
• Simulated annealing
• Tabu search

| below =

• Software

}} | group5 =Metaheuuristic |abbr5 = heuristic | list5 =*विकासवादी एल्गोरिथ्म

• पहाड़ी की चढ़ाई
• स्थानीय खोज
• तैयार किए हुयी धातु पे पानी चढाने की कला
• तब्बू खोज

| below =* सॉफ्टवेयर

}}