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

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

परिभाषा

उत्तल अनुकूलन समस्या एक अनुकूलन समस्या है। जिसमें उद्देश्य फलन उत्तल फलन होता है और साध्य क्षेत्र उत्तल समुच्चय होता है। फलन $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(\mathbf {x} )$ इन सब में $\mathbf {x}$ संतुष्टि देने वाला