उत्तल अनुकूलन: Difference between revisions

Revision as of 08:54, 19 February 2023

उत्तल अनुकूलन गणितीय अनुकूलन का उपक्षेत्र है। मस्याजो उत्तल सेटों पर उत्तल कार्यों को कम करने की स का अध्ययन करता है (या समकक्ष उत्तल सेटों पर अवतल कार्यों को अधिकतम करना)। उत्तल अनुकूलन समस्याओं के कई वर्ग बहुपद-काल एल्गोरिदम को स्वीकार करते हैं।^[1] जबकि गणितीय अनुकूलन सामान्य रूप से एनपी कठिन है।^[2]^[3]^[4] उत्तल अनुकूलन में व्यापक श्रेणी के अनुशासन हैं। जैसे स्वचालित नियंत्रण प्रणाली, अनुमान और संकेत आगे बढ़ाना, संचार और नेटवर्क, इलेक्ट्रॉनिक सर्किट डिज़ाइन,^[5] डेटा विश्लेषण और मॉडलिंग, वित्त, सांख्यिकी (इष्टतम डिजाइन)^[6] और संरचनात्मक अनुकूलन, जहां सन्निकटन अवधारणा कुशल प्रमाणित हुई है।^[7]^[8] कंप्यूटिंग और गणितीय अनुकूलन कम्प्यूटेशनल अनुकूलन विधियों की प्रगति के साथ उत्तल प्रोग्रामिंग लगभग रैखिक प्रोग्रामिंग के रूप में सीधी है।^[9]

परिभाषा

उत्तल अनुकूलन समस्या एक अनुकूलन समस्या है। जिसमें उद्देश्य फलन उत्तल फलन होता है और साध्य क्षेत्र उत्तल समुच्चय होता है। समारोह $f$ के कुछ उपसमुच्चय का मानचित्रण करना $\mathbb {R} ^{n}$ में $\mathbb {R} \cup \{\pm \infty \}$ उत्तल है। यदि इसका डोमेन उत्तल है और सभी के लिए $\theta \in [0,1]$ और सभी $x,y$ इसके डोमेन में निम्नलिखित नियम रखती है: $f(\theta x+(1-\theta )y)\leq \theta f(x)+(1-\theta )f(y)$ । सभी सदस्यों के लिए सेट S उत्तल है। $x,y\in S$ और सभी $\theta \in [0,1]$ हमारे पास वह है। $\theta x+(1-\theta )y\in S$

वस्तुतः $\mathbf {x^{\ast }} \in C$ को प्राप्त उत्तल अनुकूलन समस्या कुछ खोजने की समस्या है।

\inf\{f(\mathbf {x} ):\mathbf {x} \in C\}

,

जहां उद्देश्य समारोह $f:{\mathcal {D}}\subseteq \mathbb {R} ^{n}\to \mathbb {R}$ उत्तल है। जैसा कि संभव सेट $C$ है।^[10] यदि ऐसा कोई बिंदु उपस्थित है। तो इसे इष्टतम बिंदु या समाधान कहा जाता है। सभी इष्टतम बिंदुओं के समुच्चय को इष्टतम समुच्चय कहा जाता है। जो $f$ नीचे असीमित है। $C$ न्यूनतम प्राप्त नहीं हुआ है। तो अनुकूलन समस्या को अबाधित कहा जाता है। अन्यथा $C$ रिक्त समुच्चय है। तो समस्या असाध्य कहलाती है।^[11]

मानक रूप

उत्तल अनुकूलन समस्या मानक रूप में होती है। यदि इसे इस रूप में लिखा जाए

\begin{aligned} \underset{x}{minimize} & f (x) \\ s u b j e c t t o & g_{i} (x) \leq 0, i = 1, \dots \end{aligned}

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

@@ Line 10: / Line 10: @@
 वस्तुतः <math>\mathbf{x^\ast} \in C</math> को प्राप्त उत्तल अनुकूलन समस्या कुछ खोजने की समस्या है।
 :<math>\inf \{ f(\mathbf{x}) : \mathbf{x} \in C \}</math>,
-जहां उद्देश्य समारोह <math>f :\mathcal D \subseteq \mathbb{R}^n \to \mathbb{R}</math> उत्तल है। जैसा कि संभव सेट <math>C</math> है।<ref>{{cite book|url=https://books.google.com/books?id=Gdl4Jc3RVjcC&q=lemarechal+convex+analysis+and+minimization|title=Convex analysis and minimization algorithms: Fundamentals|last1=Hiriart-Urruty|first1=Jean-Baptiste|last2=Lemaréchal|first2=Claude|year=1996|page=291|isbn=9783540568506}}</ref> यदि ऐसा कोई बिंदु उपस्थित है। तो इसे  इष्टतम बिंदु या समाधान कहा जाता है। सभी इष्टतम बिंदुओं के समुच्चय को इष्टतम समुच्चय कहा जाता है। जो <math>f</math> नीचे असीमित है। <math>C</math> न्यूनतम प्राप्त नहीं हुआ है। तो अनुकूलन समस्या को अबाधित कहा जाता है। अन्यथा <math>C</math> रिक्त समुच्चय है। तो समस्या असाध्य कहलाती है।<ref name="bv4">{{harvnb|Boyd|Vandenberghe|2004|loc=chpt. 4}}</ref>
+जहां उद्देश्य समारोह <math>f :\mathcal D \subseteq \mathbb{R}^n \to \mathbb{R}</math> उत्तल है। जैसा कि संभव सेट <math>C</math> है।<ref>{{cite book|url=https://books.google.com/books?id=Gdl4Jc3RVjcC&q=lemarechal+convex+analysis+and+minimization|title=Convex analysis and minimization algorithms: Fundamentals|last1=Hiriart-Urruty|first1=Jean-Baptiste|last2=Lemaréchal|first2=Claude|year=1996|page=291|isbn=9783540568506}}</ref> यदि ऐसा कोई बिंदु उपस्थित है। तो इसे इष्टतम बिंदु या समाधान कहा जाता है। सभी इष्टतम बिंदुओं के समुच्चय को इष्टतम समुच्चय कहा जाता है। जो <math>f</math> नीचे असीमित है। <math>C</math> न्यूनतम प्राप्त नहीं हुआ है। तो अनुकूलन समस्या को अबाधित कहा जाता है। अन्यथा <math>C</math> रिक्त समुच्चय है। तो समस्या असाध्य कहलाती है।<ref name="bv4">{{harvnb|Boyd|Vandenberghe|2004|loc=chpt. 4}}</ref>
@@ Line 25: / Line 25: @@
 * <math>\mathbf{x} \in \mathbb{R}^n</math> अनुकूलन चर है;
-* उद्देश्य समारोह <math>f: \mathcal D \subseteq \mathbb{R}^n \to \mathbb{R}</math> एक उत्तल कार्य है;
+* उद्देश्य समारोह <math>f: \mathcal D \subseteq \mathbb{R}^n \to \mathbb{R}</math> उत्तल कार्य है;
 * असमानता बाधा कार्य करती है <math>g_i : \mathbb{R}^n \to \mathbb{R}</math>, <math>i=1, \ldots, m</math>, उत्तल कार्य हैं;
-* समानता बाधा कार्य करती है <math>h_i : \mathbb{R}^n \to \mathbb{R}</math>, <math>i=1, \ldots, p</math>,  [[affine परिवर्तन|ठीक परिवर्तन]] हैं। अर्थात् इस रूप का <math>h_i(\mathbf{x}) = \mathbf{a_i}\cdot \mathbf{x} - b_i</math>, जहाँ <math>\mathbf{a_i}</math> वेक्टर है और <math>b_i</math> अदिश राशि है।
+* समानता बाधा कार्य करती है <math>h_i : \mathbb{R}^n \to \mathbb{R}</math>, <math>i=1, \ldots, p</math>, [[affine परिवर्तन|ठीक परिवर्तन]] हैं। अर्थात् इस रूप का <math>h_i(\mathbf{x}) = \mathbf{a_i}\cdot \mathbf{x} - b_i</math>, जहाँ <math>\mathbf{a_i}</math> वेक्टर है और <math>b_i</math> अदिश राशि है।
 यह संकेतन खोजने की समस्या का वर्णन करता है। <math>\mathbf{x} \in \mathbb{R}^n</math> जो कम करता है। <math>f(\mathbf{x})</math> इन सब में <math>\mathbf{x}</math> संतुष्टि देने वाला <math>g_i(\mathbf{x}) \leq 0</math>, <math>i=1, \ldots, m</math> और <math>h_i(\mathbf{x}) = 0</math>, <math>i=1, \ldots, p</math>. कार्यक्रम <math>f</math> समस्या का उद्देश्य कार्य है और कार्य <math>g_i</math> और <math>h_i</math> बाधा कार्य हैं।
@@ Line 50: / Line 50: @@
 {{cite journal|url=https://web.stanford.edu/~boyd/papers/pdf/cvxpy_rewriting.pdf|last1=Agrawal|first1=Akshay|last2=Verschueren|first2=Robin|last3=Diamond|first3=Steven|last4=Boyd|first4=Stephen|title=A rewriting system for convex optimization problems|journal=Control and Decision|volume=5|issue=1|year=2018|pages=42–60|doi=10.1080/23307706.2017.1397554|arxiv=1709.04494|s2cid=67856259}}</ref>
-  [[File:Hierarchy compact convex.png|thumb|उत्तल अनुकूलन समस्याओं का एक पदानुक्रम। (एलपी: लीनियर प्रोग्राम, क्यूपी: क्वाड्रैटिक प्रोग्राम, एसओसीपी सेकंड-ऑर्डर कोन प्रोग्राम, एसडीपी: सेमिडेफिनिट प्रोग्राम, सीपी: कोन प्रोग्राम।)]][[कम से कम वर्गों]] में दर्शाया गया है:
+  [[File:Hierarchy compact convex.png|thumb|उत्तल अनुकूलन समस्याओं का पदानुक्रम। (एलपी: लीनियर प्रोग्राम, क्यूपी: क्वाड्रैटिक प्रोग्राम, एसओसीपी सेकंड-ऑर्डर कोन प्रोग्राम, एसडीपी: सेमिडेफिनिट प्रोग्राम, सीपी: कोन प्रोग्राम।)]][[कम से कम वर्गों]] में दर्शाया गया है:
 *रैखिक प्रोग्रामिंग
 * रैखिक बाधाओं के साथ उत्तल [[द्विघात प्रोग्रामिंग]]
@@ Line 80: / Line 80: @@
 # <math>\lambda_{1}g_{1}(x)=\cdots = \lambda_{m}g_{m}(x) = 0</math> (पूरक शिथिलता)।
-अगर कोई पूरी तरह से संभव बिंदु उपस्थित है। अर्थात एक बिंदु <math>z</math> संतुष्टि देने वाला
+अगर कोई पूरी तरह से संभव बिंदु उपस्थित है। अर्थात बिंदु <math>z</math> संतुष्टि देने वाला
 :<math>g_{1}(z), \ldots, g_{m}(z)<0,</math>
@@ Line 88: / Line 88: @@
 == एल्गोरिदम ==
-अप्रतिबंधित उत्तल अनुकूलन को आसानी से [[ढतला हुआ वंश]] (स्टीपेस्ट डिसेंट की विधि का एक विशेष स्थिति) या अनुकूलन में न्यूटन की विधि के साथ हल किया जा सकता है। न्यूटन की विधि एक उपयुक्त चरण आकार के लिए लाइन खोज के साथ संयुक्त है। इन्हें गणितीय रूप से शीघ्रता से अभिसरण करने के लिए सिद्ध किया जा सकता है। विशेष रूप से बाद वाली विधि अत्यधिक प्रयोग की जाती है।<ref name=":2">{{Cite book|last1=Boyd|first1=Stephen|url=https://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf|title=Convex Optimization|last2=Vandenberghe|first2=Lieven|publisher=[[Cambridge University Press]]|year=2004|isbn=978-0-521-83378-3|access-date=12 Apr 2021|url-status=live}}</ref> रैखिक समानता बाधाओं के साथ उत्तल अनुकूलन को [[केकेटी मैट्रिक्स]] विधियों का उपयोग करके भी हल किया जा सकता है। यदि उद्देश्य फ़ंक्शन एक द्विघात फ़ंक्शन है (जो न्यूटन की विधि की भिन्नता के लिए सामान्य है। जो काम करता है। परन्तु आरंभीकरण बिंदु बाधाओं को पूरा नहीं करता है। लेकिन यह भी कर सकता है। सामान्यतः रैखिक बीजगणित के साथ समानता की बाधाओं को दूर करके या दोहरी समस्या को हल करके हल किया जा सकता है।<ref name=":2" /> अंत में रैखिक समानता बाधाओं और उत्तल असमानता बाधाओं दोनों के साथ उत्तल अनुकूलन को ऑब्जेक्टिव फ़ंक्शन प्लस [[लॉगरिदमिक बैरियर फ़ंक्शन]] नियमों के लिए एक अप्रतिबंधित उत्तल अनुकूलन विधि प्रारम्भ करके हल किया जा सकता है।<ref name=":2" /> जब प्रारंभिक बिंदु संभव नहीं है। अर्थात बाधाओं को संतुष्ट करना। यह तथाकथित चरण विधियों से पहले होता है। जो या तो एक व्यवहार्य बिंदु ढूंढते हैं या दिखाते हैं कि कोई भी अस्तित्व में नहीं है। चरण I विधियों में सामान्यतः प्रश्न में खोज को कम करना सम्मिलित है। अभी तक एक और उत्तल अनुकूलन समस्या के लिए<ref name=":2" /> उत्तल अनुकूलन समस्याओं को निम्नलिखित समकालीन तरीकों से भी हल किया जा सकता है:<ref>For methods for convex minimization, see the volumes by Hiriart-Urruty and Lemaréchal (bundle) and the textbooks by [[Andrzej Piotr Ruszczyński|Ruszczyński]], [[Dimitri Bertsekas|Bertsekas]], and
+अप्रतिबंधित उत्तल अनुकूलन को आसानी से [[ढतला हुआ वंश]] (स्टीपेस्ट डिसेंट की विधि का विशेष स्थिति) या अनुकूलन में न्यूटन की विधि के साथ हल किया जा सकता है। न्यूटन की विधि उपयुक्त चरण आकार के लिए लाइन खोज के साथ संयुक्त है। इन्हें गणितीय रूप से शीघ्रता से अभिसरण करने के लिए सिद्ध किया जा सकता है। विशेष रूप से बाद वाली विधि अत्यधिक प्रयोग की जाती है।<ref name=":2">{{Cite book|last1=Boyd|first1=Stephen|url=https://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf|title=Convex Optimization|last2=Vandenberghe|first2=Lieven|publisher=[[Cambridge University Press]]|year=2004|isbn=978-0-521-83378-3|access-date=12 Apr 2021|url-status=live}}</ref> रैखिक समानता बाधाओं के साथ उत्तल अनुकूलन को [[केकेटी मैट्रिक्स]] विधियों का उपयोग करके भी हल किया जा सकता है। यदि उद्देश्य फ़ंक्शन द्विघात फ़ंक्शन है (जो न्यूटन की विधि की भिन्नता के लिए सामान्य है। जो काम करता है। परन्तु आरंभीकरण बिंदु बाधाओं को पूरा नहीं करता है। किन्तु यह भी कर सकता है। सामान्यतः रैखिक बीजगणित के साथ समानता की बाधाओं को दूर करके या दोहरी समस्या को हल करके हल किया जा सकता है।<ref name=":2" /> अंत में रैखिक समानता बाधाओं और उत्तल असमानता बाधाओं दोनों के साथ उत्तल अनुकूलन को ऑब्जेक्टिव फ़ंक्शन प्लस [[लॉगरिदमिक बैरियर फ़ंक्शन]] नियमों के लिए अप्रतिबंधित उत्तल अनुकूलन विधि प्रारम्भ करके हल किया जा सकता है।<ref name=":2" /> जब प्रारंभिक बिंदु संभव नहीं है। अर्थात बाधाओं को संतुष्ट करना। यह तथाकथित चरण विधियों से पहले होता है। जो या तो व्यवहार्य बिंदु ढूंढते हैं या दिखाते हैं कि कोई भी अस्तित्व में नहीं है। चरण I विधियों में सामान्यतः प्रश्न में खोज को कम करना सम्मिलित है। अभी तक उत्तल अनुकूलन समस्या के लिए<ref name=":2" /> उत्तल अनुकूलन समस्याओं को निम्नलिखित समकालीन  प्रकारों से भी हल किया जा सकता है:<ref>For methods for convex minimization, see the volumes by Hiriart-Urruty and Lemaréchal (bundle) and the textbooks by [[Andrzej Piotr Ruszczyński|Ruszczyński]], [[Dimitri Bertsekas|Bertsekas]], and
 Boyd and Vandenberghe (interior point).
 </ref>
@@ Line 98: / Line 98: @@
 * [[सबग्रेडिएंट विधि]]
 *[[ड्रिफ्ट प्लस पेनल्टी]] डुअल सबग्रेडिएंट्स और ड्रिफ्ट-प्लस-पेनल्टी विधि
-सबग्रेडिएंट विधियों को आसानी से प्रयोग किया जा सकता है और इसलिए व्यापक रूप से उपयोग किया जाता है।<ref>Bertsekas</ref> दोहरी सबग्रेडिएंट विधियाँ एक [[द्वैत (अनुकूलन)]] पर प्रयोग सबग्रेडिएंट विधियाँ हैं। ड्रिफ्ट-प्लस-पेनल्टी विधि दोहरी सबग्रेडिएंट विधि के समान है। लेकिन प्रारंभिक चर का समय औसत लेती है।
+सबग्रेडिएंट विधियों को आसानी से प्रयोग किया जा सकता है और इसलिए व्यापक रूप से उपयोग किया जाता है।<ref>Bertsekas</ref> दोहरी सबग्रेडिएंट विधियाँ [[द्वैत (अनुकूलन)]] पर प्रयोग सबग्रेडिएंट विधियाँ हैं। ड्रिफ्ट-प्लस-पेनल्टी विधि दोहरी सबग्रेडिएंट विधि के समान है। किन्तु प्रारंभिक चर का समय औसत लेती है।
@@ Line 162: / Line 162: @@
 |एक्एसलएमआई
 |[[MATLAB|मैटलैब]]
-|एलएमआई लैब के समान, लेकिन सेडुमी सॉल्वर का उपयोग करता है।
+|एलएमआई लैब के समान, किन्तु सेडुमी सॉल्वर का उपयोग करता है।
 |सही
 |<ref name=":3" />
@@ Line 255: / Line 255: @@
 |लोको
 |
-|एसओपीसी के लिए सामान्य-उद्देश्य कोड का समर्थन करता है, जिसे वह एक अरेखीय प्रोग्रामिंग समस्या के रूप में मानता है।
+|एसओपीसी के लिए सामान्य-उद्देश्य कोड का समर्थन करता है, जिसे वह अरेखीय प्रोग्रामिंग समस्या के रूप में मानता है।
 |नहीं
 |<ref name=":3" />

Anonymous

Search

उत्तल अनुकूलन: Difference between revisions

Namespaces

More

Page actions

Revision as of 08:54, 19 February 2023

Contents

परिभाषा

मानक रूप