Convex optimization
उत्तल अनुकूलन गणितीय अनुकूलन का एक उपक्षेत्र है जो उत्तल समुच्चयों पर उत्तल कार्यों को न्यूनतम करने की समस्या का अध्ययन करता है (या, समतुल्य रूप से, उत्तल समुच्चयों पर अवतल कार्यों को अधिकतम करना)। उत्तल अनुकूलन समस्याओं के कई वर्ग बहुपद-समय एल्गोरिदम को स्वीकार करते हैं, जबकि गणितीय अनुकूलन सामान्य रूप से एनपी-हार्ड होता है। कन्वेक्स अनुकूलन में स्वचालित नियंत्रण प्रणाली, आकलन और संकेत प्रसंस्करण, संचार और नेटवर्क, इलेक्ट्रॉनिक सर्किट डिजाइन, डेटा विश्लेषण और मॉडलिंग, वित्त, सांख्यिकी (इष्टतम प्रयोगात्मक डिजाइन), और संरचनात्मक अनुकूलन जैसे विषयों की एक विस्तृत श्रृंखला में अनुप्रयोग हैं, जहां सन्निकटन अवधारणा कुशल साबित हुई है। कम्प्यूटिंग और अनुकूलन एल्गोरिदम में हाल की प्रगति के साथ, उत्तल प्रोग्रामिंग लगभग रैखिक प्रोग्रामिंग के रूप में सीधी है। परिभाषा एक उत्तल अनुकूलन समस्या एक अनुकूलन समस्या है जिसमें वस्तुनिष्ठ फलन एक उत्तल फलन है और व्यवहार्य समुच्चय एक उत्तल समुच्चय है। इनटू के कुछ उपसमुच्चय का मानचित्रण करने वाला एक फलन उत्तल होता है यदि इसका क्षेत्र उत्तल होता है और इसके क्षेत्र में सभी के लिए निम्नलिखित शर्त होती हैः एक समुच्चय S उत्तल है यदि सभी सदस्यों और सभी के लिए, हमारे पास वह है। ठोस रूप से, एक उत्तल अनुकूलन समस्या कुछ प्राप्त करने की समस्या है, जहां वस्तुनिष्ठ कार्य उत्तल है, जैसा कि व्यवहार्य सेट है। यदि ऐसा कोई बिंदु मौजूद है, तो इसे एक इष्टतम बिंदु या समाधान के रूप में संदर्भित किया जाता है; सभी इष्टतम बिंदुओं के सेट को इष्टतम सेट कहा जाता है। यदि नीचे असीमित है या अधिकतम प्राप्त नहीं किया जाता है, तो अनुकूलन समस्या को असीमित कहा जाता है। अन्यथा, यदि खाली सेट है, तो समस्या को अव्यवहारिक कहा जाता है। एक उत्तल अनुकूलन समस्या मानक रूप में होती है यदि इसे इस प्रकार लिखा जाता है कि कहाँः अनुकूलन चर है; वस्तुनिष्ठ कार्य एक उत्तल कार्य है; असमानता बाधा कार्य, उत्तल कार्य हैं; समानता बाधा कार्य, एफ़ाइन परिवर्तन हैं, जो इस रूप के हैंः, जहाँ एक सदिश है और एक स्केलर है। यह संकेतन खोजने की समस्या का वर्णन करता है जो सभी संतोषजनक में न्यूनतम है, और,। कार्य समस्या का वस्तुनिष्ठ कार्य है, और कार्य और बाधा कार्य हैं। अनुकूलन समस्या के व्यवहार्य समूह में बाधाओं को संतुष्ट करने वाले सभी बिंदु शामिल होते हैं। यह समुच्चय उत्तल है क्योंकि उत्तल है, उत्तल कार्यों के उप-स्तरीय समुच्चय उत्तल हैं, अफाइन समुच्चय उत्तल हैं, और उत्तल समुच्चय का प्रतिच्छेदन उत्तल है। उत्तल अनुकूलन समस्या का समाधान किसी भी बिंदु को प्राप्त करना है। सामान्य तौर पर, एक उत्तल अनुकूलन समस्या में शून्य, एक या कई समाधान हो सकते हैं। कई अनुकूलन समस्याओं को इस मानक रूप में समान रूप से तैयार किया जा सकता है। उदाहरण के लिए, एक अवतल फलन को अधिकतम करने की समस्या को उत्तल फलन को न्यूनतम करने की समस्या के रूप में समान रूप से फिर से तैयार किया जा सकता है। उत्तल समूह पर अवतल फलन को अधिकतम करने की समस्या को आमतौर पर उत्तल अनुकूलन समस्या कहा जाता है। उत्तल अनुकूलन समस्याओं के निम्नलिखित उपयोगी गुण हैंः प्रत्येक स्थानीय न्यूनतम एक वैश्विक न्यूनतम है; इष्टतम समुच्चय उत्तल है; यदि वस्तुनिष्ठ फलन सख्ती से उत्तल है, तो समस्या का अधिकतम एक इष्टतम बिंदु होता है। इन परिणामों का उपयोग कार्यात्मक विश्लेषण (हिल्बर्ट रिक्त स्थान में) से ज्यामितीय धारणाओं के साथ उत्तल लघुकरण के सिद्धांत द्वारा किया जाता है जैसे कि हिल्बर्ट प्रक्षेपण प्रमेय, अलग हाइपरप्लेन प्रमेय और फ़र्कस लेम्मा। अनुप्रयोग निम्नलिखित समस्या वर्ग सभी उत्तल अनुकूलन समस्याएं हैं, या सरल परिवर्तनों के माध्यम से उत्तल अनुकूलन समस्याओं के लिए कम किया जा सकता हैः न्यूनतम वर्ग रैखिक प्रोग्रामिंग उत्तल द्विघात लघुकरण रैखिक बाधाओं के साथ उत्तल द्विघात लघुकरण उत्तल द्विघात बाधाओं के साथ द्विघात लघुकरण शंकु अनुकूलन ज्यामितीय प्रोग्रामिंग दूसरा क्रम शंकु प्रोग्रामिंग उपयुक्त बाधाओं के साथ अर्ध-परिमित प्रोग्रामिंग एन्ट्रापी अधिकतमकरण उत्तल अनुकूलन में निम्नलिखित के लिए व्यावहारिक अनुप्रयोग हैं। पोर्टफोलियो अनुकूलन। सबसे खराब स्थिति जोखिम विश्लेषण। इष्टतम विज्ञापन। सांख्यिकीय प्रतिगमन की भिन्नताएँ (नियमितकरण और मात्रात्मक प्रतिगमन सहित)। मॉडल फिटिंग (विशेष रूप से बहुस्तरीय वर्गीकरण)। विद्युत उत्पादन अनुकूलन। संयोजन अनुकूलन। अनिश्चितता का गैर-संभावित प्रतिरूपण। ताररहित संकेतों का उपयोग करके स्थानीयकरण लैग्रेंज गुणक लागत फलन और असमानता बाधाओं द्वारा मानक रूप में दी गई उत्तल न्यूनतम समस्या पर विचार करें। फिर डोमेन हैः समस्या के लिए लैग्रैन्जियन फ़ंक्शन है प्रत्येक बिंदु के लिए जो कम करता है, वहाँ वास्तविक संख्याएँ मौजूद हैं जिन्हें लैग्रैन्ज गुणक कहा जाता है, जो इन शर्तों को एक साथ पूरा करते हैंः कम से कम एक (पूरक शिथिलता) के साथ सभी को कम करता है। यदि कोई "कड़ाई से व्यवहार्य बिंदु" मौजूद है, यानी एक संतोषजनक बिंदु है तो उपरोक्त कथन को इसकी आवश्यकता के लिए मजबूत किया जा सकता है। इसके विपरीत, यदि कुछ स्केलर के लिए (1)-(3) को संतुष्ट करते हैं तो निश्चित रूप से कम करने के लिए निश्चित है। एल्गोरिदम अनियंत्रित उत्तल अनुकूलन को आसानी से ढाल वंश (सबसे तीव्र वंश का एक विशेष मामला) या न्यूटन की विधि के साथ हल किया जा सकता है, जो एक उपयुक्त चरण आकार के लिए रेखा खोज के साथ संयुक्त है; इन्हें गणितीय रूप से जल्दी से अभिसरण करने के लिए साबित किया जा सकता है, विशेष रूप से बाद की विधि। रैखिक समानता बाधाओं के साथ उत्तल अनुकूलन को केकेटी मैट्रिक्स तकनीकों का उपयोग करके भी हल किया जा सकता है यदि वस्तुनिष्ठ कार्य एक द्विघात कार्य है (जो न्यूटन की विधि की भिन्नता के लिए सामान्यीकृत होता है, जो तब भी काम करता है जब आरंभीकरण का बिंदु बाधाओं को संतुष्ट नहीं करता है), लेकिन आमतौर पर रैखिक बीजगणित के साथ समानता बाधाओं को समाप्त करके या दोहरी समस्या को हल करके भी हल किया जा सकता है। अंत में, रैखिक समानता बाधाओं और उत्तल असमानता बाधाओं दोनों के साथ उत्तल अनुकूलन को वस्तुनिष्ठ कार्य और लघुगणक बाधा शर्तों के लिए एक अनियंत्रित उत्तल अनुकूलन तकनीक लागू करके हल किया जा सकता है। (जब प्रारंभिक बिंदु संभव नहीं होता है-यानी, बाधाओं को संतुष्ट करना-यह तथाकथित चरण I विधियों से पहले होता है, जो या तो एक व्यवहार्य बिंदु पाते हैं या दिखाते हैं कि कोई भी मौजूद नहीं है। चरण I विधियों में आम तौर पर विचाराधीन खोज को एक और उत्तल अनुकूलन समस्या तक कम करना शामिल है।) कन्वेक्स अनुकूलन समस्याओं को निम्नलिखित समकालीन तरीकों से भी हल किया जा सकता हैः बंडल विधियाँ (वोल्फ, लेमरेचल, किविल), और सबग्रेडिएंट प्रोजेक्शन विधियाँ (पॉलीक), आंतरिक-बिंदु विधियाँ, जो स्व-समन्वय बाधा कार्यों और स्व-नियमित बाधा कार्यों का उपयोग करती हैं। कटिंग-प्लेन विधियाँ एलिप्सॉइड विधि सबग्रेडिएंट विधि दोहरी सबग्रेडिएंट और ड्रिफ्ट-प्लस-पेनल्टी विधि सबग्रेडिएंट विधियों को सरलता से लागू किया जा सकता है और इसलिए व्यापक रूप से उपयोग किया जाता है। दोहरी उप-प्रवणता विधियाँ एक दोहरी समस्या पर लागू उप-प्रवणता विधियाँ हैं। ड्रिफ्ट-प्लस-पेनल्टी विधि दोहरी उप-प्रवणता विधि के समान है, लेकिन प्राइमल चर का औसत समय लेती है। सॉफ्टवेयर उत्तल अनुकूलन के लिए एक बड़ा सॉफ्टवेयर पारिस्थितिकी तंत्र है। इस पारिस्थितिकी तंत्र की दो मुख्य श्रेणियां हैंः एक ओर समाधानकर्ता और दूसरी ओर मॉडलिंग उपकरण (या इंटरफेस)। समाधानकर्ता एल्गोरिदम को स्वयं लागू करते हैं और आमतौर पर सी में लिखे जाते हैं। उन्हें उपयोगकर्ताओं को बहुत विशिष्ट प्रारूपों में अनुकूलन समस्याओं को निर्दिष्ट करने की आवश्यकता होती है जो मॉडलिंग के दृष्टिकोण से स्वाभाविक नहीं हो सकते हैं। मॉडलिंग उपकरण सॉफ्टवेयर के अलग-अलग टुकड़े हैं जो उपयोगकर्ता को उच्च-स्तरीय वाक्यविन्यास में एक अनुकूलन निर्दिष्ट करने देते हैं। वे उपयोगकर्ता के उच्च-स्तरीय मॉडल और समाधानकर्ता के इनपुट/आउटपुट प्रारूप से सभी परिवर्तनों का प्रबंधन करते हैं। नीचे दी गई तालिका मॉडलिंग उपकरणों (जैसे सी. वी. एक्स. पी. वाई. और Convex.jl) और समाधानकर्ताओं (जैसे सी. वी. एक्स. ओ. पी. टी. और एम. ओ. एस. ई. के) का मिश्रण दिखाती है। यह तालिका किसी भी तरह से संपूर्ण नहीं है। उत्तल अनुकूलन के विस्तारों में बाइकोनवेक्स, सूडो-कन्वेक्स और क्वासीकॉनवेक्स कार्यों का अनुकूलन शामिल है। उत्तल विश्लेषण के सिद्धांत का विस्तार और गैर-उत्तल लघुकरण समस्याओं को लगभग हल करने के लिए पुनरावृत्ति विधियाँ सामान्यीकृत उत्तलता के क्षेत्र में होती हैं, जिसे अमूर्त उत्तल विश्लेषण के रूप में भी जाना जाता है। द्वैत करूश-कुह्न-टकर स्थितियों अनुकूलन समस्या समीपस्थ ढाल विधि टिप्पणियाँ संदर्भ हिरियार्ट-उरुटी, जीन-बैप्टिस्ट, और लेमरेचल, क्लाउड को भी देखें। (2004)। कन्वेक्स विश्लेषण की मूल बातें। बर्लिनः स्प्रिंगर। नेस्टरोव, यूरी। (2004)। कन्वेक्स ऑप्टिमाइजेशन पर परिचयात्मक व्याख्यान, क्लूवर अकादमिक प्रकाशक श्मिट, एल. ए.; फ्लूरी, सी. 1980: अनुमानित अवधारणाओं और दोहरी विधियों के संयोजन द्वारा संरचनात्मक संश्लेषण। जे. आमेर। इंस्टा. एरोनॉट। अंतरिक्ष यात्री 18,1252-1260 बाहरी लिंक EE364a: कन्वेक्स ऑप्टिमाइजेशन I और EE364b: कन्वेक्स ऑप्टिमाइजेशन II, स्टैनफोर्ड कोर्स होमपेज 6.253: कन्वेक्स एनालिसिस एंड ऑप्टिमाइजेशन, एक एम. आई. टी. ओ. सी. डब्ल्यू कोर्स होमपेज ब्रायन बोर्चर्स, कन्वेक्स ऑप्टिमाइजेशन के लिए सॉफ्टवेयर का अवलोकन लीवेन वैंडेनबर्ग और स्टीफन पी. बॉयड कन्वेक्स विश्लेषण गणितीय ऑप्टिमाइजेशन