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

उत्तल अनुकूलन उत्तल फलनों को उत्तल समुच्चयों पर न्यूनतम करने का अध्ययन है, जो समस्याओं का एक ऐसा वर्ग है जिसके लिए स्थानीय इष्टतम वैश्विक होते हैं और कुशल एल्गोरिदम मौजूद होते हैं।

Definition

एक उत्तल अनुकूलन समस्या उत्तल असमानता बाधाओं और एफाइन समानता बाधाओं के अधीन एक उत्तल उद्देश्य को न्यूनतम करती है; व्यवहार्य समुच्चय उत्तल होता है, जो यह सुनिश्चित करता है कि कोई भी स्थानीय न्यूनतम भी एक वैश्विक न्यूनतम होता है।

Scope

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

Core questions

• किसी समस्या को उत्तल के रूप में कैसे पहचाना या पुनर्गठित किया जा सकता है?
• उत्तलता क्यों गारंटी देती है कि स्थानीय इष्टतम वैश्विक होते हैं?
• द्वैत एक उत्तल समस्या और उसके समाधान के बारे में क्या बताता है?
• कौन से एल्गोरिदम उत्तल समस्याओं को कुशलता से और किन गारंटियों के साथ हल करते हैं?

Key theories

उत्तल समस्याओं की वैश्विक इष्टतमता

क्योंकि एक उत्तल समुच्चय पर एक उत्तल फलन में कोई नकली स्थानीय न्यूनतम नहीं होता है, कोई भी स्थानीय रूप से इष्टतम बिंदु वैश्विक रूप से इष्टतम होता है, जिससे उत्तल समस्याओं को विश्वसनीय रूप से हल किया जा सकता है।

लैग्रेंजियन द्वैत और KKT शर्तें

प्रत्येक उत्तल समस्या में एक संबद्ध द्वैत समस्या होती है जो इष्टतमता प्रमाण पत्र प्रदान करती है, और बाधा योग्यताओं के तहत कारुश-कुह्न-टकर शर्तें इष्टतमता के लिए आवश्यक और पर्याप्त होती हैं।

आंतरिक-बिंदु विधियाँ

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

Clinical relevance

उत्तल अनुकूलन मशीन लर्निंग, सिग्नल और इमेज प्रोसेसिंग, नियंत्रण, वित्त, और इंजीनियरिंग डिजाइन में व्यापक है, क्योंकि कई अनुमान और निर्णय समस्याओं को उत्तल प्रोग्रामों के रूप में ढाला जा सकता है और बड़े पैमाने पर विश्वसनीय रूप से हल किया जा सकता है।

History

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

Key figures

• R. Tyrrell Rockafellar
• Stephen Boyd
• Yurii Nesterov
• Narendra Karmarkar

Seminal works

• boyd2004
• rockafellar1970

Frequently asked questions

संभव होने पर उत्तल मॉडल को प्राथमिकता क्यों दें?

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

क्या रैखिक प्रोग्रामिंग एक प्रकार का उत्तल अनुकूलन है?

हाँ। एक रैखिक प्रोग्राम एक पॉलीहेड्रॉन पर एक रैखिक उद्देश्य को न्यूनतम करता है, और दोनों रैखिक फलन और पॉलीहेड्रा उत्तल होते हैं, इसलिए रैखिक प्रोग्रामिंग उत्तल अनुकूलन का एक विशेष, विशेष रूप से अच्छी तरह से समझा गया मामला है।