उत्तल अनुकूलन

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

परिभाषा

उत्तल अनुकूलन समस्या एक अनुकूलन समस्या है। जिसमें उद्देश्य फलन उत्तल फलन होता है और साध्य क्षेत्र उत्तल समुच्चय होता है। एक समारोह $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$ है। यदि ऐसा कोई बिंदु उपस्थित है। तो इसे एक इष्टतम बिंदु या समाधान कहा जाता है। सभी इष्टतम बिंदुओं के समुच्चय को इष्टतम समुच्चय कहा जाता है। जो $f$ नीचे असीमित है। $C$ या न्यूनतम प्राप्त नहीं हुआ है। तो अनुकूलन समस्या को अबाधित कहा जाता है। नहीं तो $C$ रिक्त समुच्चय है। तो समस्या असाध्य कहलाती है।

मानक रूप

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

${\begin{aligned}&{\underset {\mathbf {x} }{\operatorname {minimize} }}&&f(\mathbf {x} )\\&\operatorname {subject\ to} &&g_{i}(\mathbf {x} )\leq 0,\quad i=1,\dots ,m\\&&&h_{i}(\mathbf {x} )=0,\quad i=1,\dots ,p,\end{aligned}}$

जहाँ:

• $\mathbf {x} \in \mathbb {R} ^{n}$ अनुकूलन चर है;
• उद्देश्य समारोह $f:{\mathcal {D}}\subseteq \mathbb {R} ^{n}\to \mathbb {R}$ एक उत्तल कार्य है;
• असमानता बाधा कार्य करती है $g_{i}:\mathbb {R} ^{n}\to \mathbb {R}$, $i=1,\ldots ,m$, उत्तल कार्य हैं;
• समानता बाधा कार्य करती है $h_{i}:\mathbb {R} ^{n}\to \mathbb {R}$, $i=1,\ldots ,p$, एक ठीक परिवर्तन हैं। अर्थात् इस रूप का $h_{i}(\mathbf {x} )=\mathbf {a_{i}} \cdot \mathbf {x} -b_{i}$, जहाँ $\mathbf {a_{i}}$ एक वेक्टर है और $b_{i}$ एक अदिश राशि है।

यह संकेतन खोजने की समस्या का वर्णन करता है। $\mathbf {x} \in \mathbb {R} ^{n}$ जो कम करता है। $f$