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

Revision as of 16:53, 20 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, \end{aligned}

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

@@ Line 1: / Line 1: @@
 {{short description|Subfield of mathematical optimization}}
-'''उत्तल अनुकूलन''' [[गणितीय अनुकूलन]] का उपक्षेत्र है। मस्याजो [[उत्तल सेट|उत्तल सेटों]] पर उत्तल कार्यों को कम करने की स का अध्ययन करता है (या समकक्ष उत्तल सेटों पर [[अवतल कार्य|अवतल कार्यों]] को अधिकतम करना)। '''उत्तल अनुकूलन''' समस्याओं के कई वर्ग बहुपद-काल एल्गोरिदम को स्वीकार करते हैं।<ref name="Nesterov 1994">{{harvnb|Nesterov|Nemirovskii|1994}}</ref> जबकि गणितीय अनुकूलन सामान्य रूप से [[एनपी कठिन]] है।<ref>
+'''उत्तल अनुकूलन''' [[गणितीय अनुकूलन]] का उपक्षेत्र है। मस्याजो [[उत्तल सेट|उत्तल समुच्चयों]] पर उत्तल कार्यों को कम करने की स का अध्ययन करता है (या समकक्ष उत्तल समुच्चयों पर [[अवतल कार्य|अवतल कार्यों]] को अधिकतम करना)। '''उत्तल अनुकूलन''' समस्याओं के कई वर्ग बहुपद-काल एल्गोरिदम को स्वीकार करते हैं।<ref name="Nesterov 1994">{{harvnb|Nesterov|Nemirovskii|1994}}</ref> जबकि गणितीय अनुकूलन सामान्य रूप से [[एनपी कठिन]] है।<ref>
 {{cite journal | last1 = Murty | first1 = Katta | last2 = Kabadi | first2 = Santosh | title =  Some NP-complete problems in quadratic and nonlinear programming | journal = Mathematical Programming | volume = 39 | issue = 2 | pages = 117–129  | year = 1987 | doi = 10.1007/BF02592948| hdl = 2027.42/6740 | s2cid = 30500771 | hdl-access = free}}</ref><ref>Sahni, S.  "Computationally related problems," in SIAM Journal on Computing, 3, 262--279, 1974.</ref><ref>[https://link.springer.com/article/10.1007/BF00120662 Quadratic programming with one negative eigenvalue is NP-hard], Panos M. Pardalos and Stephen A. Vavasis in ''Journal of Global Optimization'', Volume 1, Number 1, 1991, pg.15-22.</ref> उत्तल अनुकूलन में व्यापक श्रेणी के अनुशासन हैं। जैसे स्वचालित [[नियंत्रण प्रणाली]], अनुमान और [[संकेत आगे बढ़ाना]], संचार और नेटवर्क, इलेक्ट्रॉनिक [[सर्किट डिज़ाइन]],<ref>{{harvnb|Boyd|Vandenberghe|2004|p=17}}</ref> डेटा विश्लेषण और मॉडलिंग, [[वित्त]], सांख्यिकी ([[इष्टतम डिजाइन]])<ref>Chritensen/Klarbring, chpt. 4.</ref> और [[संरचनात्मक अनुकूलन]], जहां सन्निकटन अवधारणा कुशल प्रमाणित हुई है।<ref>{{harvnb|Boyd|Vandenberghe|2004}}</ref><ref>Schmit, L.A.; Fleury, C. 1980: ''Structural synthesis by combining approximation concepts and dual methods''. J. Amer. Inst. Aeronaut. Astronaut 18, 1252-1260</ref> कंप्यूटिंग और गणितीय अनुकूलन कम्प्यूटेशनल अनुकूलन विधियों की प्रगति के साथ उत्तल प्रोग्रामिंग लगभग [[रैखिक प्रोग्रामिंग]] के रूप में सीधी है।<ref>{{harvnb|Boyd|Vandenberghe|2004|p=8}}</ref>
@@ Line 6: / Line 6: @@
 == परिभाषा ==
-उत्तल [[अनुकूलन समस्या]] एक अनुकूलन समस्या है। जिसमें उद्देश्य फलन उत्तल फलन होता है और साध्य क्षेत्र उत्तल समुच्चय होता है। समारोह <math>f</math> के कुछ उपसमुच्चय का मानचित्रण करना <math>\mathbb{R}^n</math>में <math>\mathbb{R} \cup \{\pm \infty\}</math> उत्तल है। यदि इसका डोमेन उत्तल है और सभी के लिए <math>\theta \in [0, 1]</math> और सभी <math>x, y</math> इसके डोमेन में निम्नलिखित नियम रखती है: <math>f(\theta x + (1 - \theta)y) \leq \theta f(x) + (1 - \theta) f(y)</math>। सभी सदस्यों के लिए सेट S उत्तल है। <math>x, y \in S</math> और सभी <math>\theta \in [0, 1]</math> हमारे पास वह है। <math>\theta x + (1 - \theta) y \in S</math>
+उत्तल [[अनुकूलन समस्या]] एक अनुकूलन समस्या है। जिसमें उद्देश्य फलन उत्तल फलन होता है और साध्य क्षेत्र उत्तल समुच्चय होता है। फलन <math>f</math> के कुछ उपसमुच्चय का मानचित्रण करना <math>\mathbb{R}^n</math>में <math>\mathbb{R} \cup \{\pm \infty\}</math> उत्तल है। यदि इसका डोमेन उत्तल है और सभी के लिए <math>\theta \in [0, 1]</math> और सभी <math>x, y</math> इसके डोमेन में निम्नलिखित नियम रखती है: <math>f(\theta x + (1 - \theta)y) \leq \theta f(x) + (1 - \theta) f(y)</math>। सभी सदस्यों के लिए समुच्चय S उत्तल है। <math>x, y \in S</math> और सभी <math>\theta \in [0, 1]</math> हमारे पास वह है। <math>\theta x + (1 - \theta) y \in S</math>
 वस्तुतः <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> बाधा कार्य हैं।
-व्यवहार्य सेट <math>C</math> अनुकूलन समस्या में सभी बिंदु सम्मिलित हैं और <math>\mathbf{x} \in \mathcal{D}</math> बाधाओं को संतुष्ट करना है। यह सेट उत्तल है क्योंकि <math>\mathcal{D}</math> उत्तल है। उत्तल कार्यों के [[सबलेवल सेट]] उत्तल हैं। अफीन सेट उत्तल हैं और उत्तल सेट का प्रतिच्छेदन उत्तल है।<ref>{{harvnb|Boyd|Vandenberghe|2004|loc=chpt. 2}}</ref> उत्तल अनुकूलन समस्या का समाधान कोई बिंदु <math>\mathbf{x} \in C</math> को प्राप्त <math>\inf \{ f(\mathbf{x}) : \mathbf{x} \in C \}</math> है। सामान्यतः उत्तल अनुकूलन समस्या में शून्य, एक या कई समाधान हो सकते हैं।<ref>{{cite web | url=https://inst.eecs.berkeley.edu/~ee227a/fa10/login/l_cvx_pbs.html | title=Convex Problems }}</ref> इस मानक रूप में कई अनुकूलन समस्याओं को समान रूप से तैयार किया जा सकता है। उदाहरण के लिए अवतल कार्य को अधिकतम करने की समस्या <math>f</math> उत्तल कार्य को कम करने की समस्या के रूप में समान रूप से पुन: तैयार किया जा सकता है। <math>-f</math> उत्तल सेट पर अवतल कार्य को अधिकतम करने की समस्या को सामान्यतः उत्तल अनुकूलन समस्या कहा जाता है।<ref>{{cite web | url=https://www.solver.com/convex-optimization | title=Optimization Problem Types - Convex Optimization | date=9 January 2011 }}</ref>
+व्यवहार्य समुच्चय <math>C</math> अनुकूलन समस्या में सभी बिंदु सम्मिलित हैं और <math>\mathbf{x} \in \mathcal{D}</math> बाधाओं को संतुष्ट करना है। यह समुच्चय उत्तल है क्योंकि <math>\mathcal{D}</math> उत्तल है। उत्तल कार्यों के [[सबलेवल सेट|सबलेवल समुच्चय]] उत्तल हैं। अफीन समुच्चय उत्तल हैं और उत्तल समुच्चय का प्रतिच्छेदन उत्तल है।<ref>{{harvnb|Boyd|Vandenberghe|2004|loc=chpt. 2}}</ref> उत्तल अनुकूलन समस्या का समाधान कोई बिंदु <math>\mathbf{x} \in C</math> को प्राप्त <math>\inf \{ f(\mathbf{x}) : \mathbf{x} \in C \}</math> है। सामान्यतः उत्तल अनुकूलन समस्या में शून्य, एक या कई समाधान हो सकते हैं।<ref>{{cite web | url=https://inst.eecs.berkeley.edu/~ee227a/fa10/login/l_cvx_pbs.html | title=Convex Problems }}</ref> इस मानक रूप में कई अनुकूलन समस्याओं को समान रूप से तैयार किया जा सकता है। उदाहरण के लिए अवतल कार्य को अधिकतम करने की समस्या <math>f</math> उत्तल कार्य को कम करने की समस्या के रूप में समान रूप से पुन: तैयार किया जा सकता है। <math>-f</math> उत्तल समुच्चय पर अवतल कार्य को अधिकतम करने की समस्या को सामान्यतः उत्तल अनुकूलन समस्या कहा जाता है।<ref>{{cite web | url=https://www.solver.com/convex-optimization | title=Optimization Problem Types - Convex Optimization | date=9 January 2011 }}</ref>
@@ Line 38: / Line 38: @@
 * प्रत्येक [[स्थानीय न्यूनतम]] एक [[वैश्विक न्यूनतम]] है;
-* इष्टतम सेट उत्तल है;
+* इष्टतम समुच्चय उत्तल है;
 *
@@ Line 71: / Line 71: @@
 :<math>\mathcal{X} = \left\{x\in X \vert g_1(x), \ldots, g_m(x)\leq 0\right\}.</math>
-समस्या के लिए लैग्रेंज समारोह है
+समस्या के लिए लैग्रेंज फलन है
 :<math>L(x,\lambda_{0},\lambda_1, \ldots ,\lambda_{m})=\lambda_{0} f(x) + \lambda_{1} g_{1} (x)+\cdots + \lambda_{m} g_{m} (x).</math>
@@ Line 174: / Line 174: @@
 |रोमे
 |
-|शक्तिशाली अनुकूलन के लिए मॉडलिंग प्रणाली। वितरण रूप से शक्तिशाली अनुकूलन और [[uncertainty set|अनिश्चितता सेट]] का समर्थन करता है। .
+|शक्तिशाली अनुकूलन के लिए मॉडलिंग प्रणाली। वितरण रूप से शक्तिशाली अनुकूलन और [[uncertainty set|अनिश्चितता समुच्चय]] का समर्थन करता है। .
 |सही
 |<ref name=":3" />

Anonymous

Search

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

Namespaces

More

Page actions

Revision as of 16:53, 20 February 2023

Contents

परिभाषा

मानक रूप