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

From Vigyanwiki
Line 394: Line 394:
[[Category: Machine Translated Page]]
[[Category: Machine Translated Page]]
[[Category:Created On 13/02/2023]]
[[Category:Created On 13/02/2023]]
[[Category:Vigyan Ready]]

Revision as of 10:45, 21 February 2023

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


परिभाषा

उत्तल अनुकूलन समस्या एक अनुकूलन समस्या है। जिसमें उद्देश्य फलन उत्तल फलन होता है और साध्य क्षेत्र उत्तल समुच्चय होता है। फलन के कुछ उपसमुच्चय का मानचित्रण करना में उत्तल है। यदि इसका डोमेन उत्तल है और सभी के लिए और सभी इसके डोमेन में निम्नलिखित नियम रखती है: । सभी सदस्यों के लिए समुच्चय S उत्तल है। और सभी हमारे पास वह है।

वस्तुतः को प्राप्त उत्तल अनुकूलन समस्या कुछ खोजने की समस्या है।

,

जहां उद्देश्य फलन उत्तल है। जैसा कि संभव समुच्चय है।[10] यदि ऐसा कोई बिंदु उपस्थित है। तो इसे इष्टतम बिंदु या समाधान कहा जाता है। सभी इष्टतम बिंदुओं के समुच्चय को इष्टतम समुच्चय कहा जाता है। जो नीचे असीमित है। न्यूनतम प्राप्त नहीं हुआ है। तो अनुकूलन समस्या को अबाधित कहा जाता है। अन्यथा रिक्त समुच्चय है। तो समस्या असाध्य कहलाती है।[11]


मानक रूप

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

जहाँ:[11]

  • अनुकूलन चर है;
  • उद्देश्य फलन उत्तल कार्य है;
  • असमानता बाधा कार्य करती है , , उत्तल कार्य हैं;
  • समानता बाधा कार्य करती है , , ठीक परिवर्तन हैं। अर्थात् इस रूप का , जहाँ दिष्‍ट है और अदिश राशि है।

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

व्यवहार्य समुच्चय अनुकूलन समस्या में सभी बिंदु सम्मिलित हैं और बाधाओं को संतुष्ट करना है। यह समुच्चय उत्तल है क्योंकि उत्तल है। उत्तल कार्यों के सबलेवल समुच्चय उत्तल हैं। अफीन समुच्चय उत्तल हैं और उत्तल समुच्चय का प्रतिच्छेदन उत्तल है।[12] उत्तल अनुकूलन समस्या का समाधान कोई बिंदु को प्राप्त है। सामान्यतः उत्तल अनुकूलन समस्या में शून्य, एक या कई समाधान हो सकते हैं।[13] इस मानक रूप में कई अनुकूलन समस्याओं को समान रूप से तैयार किया जा सकता है। उदाहरण के लिए अवतल कार्य को अधिकतम करने की समस्या उत्तल कार्य को कम करने की समस्या के रूप में समान रूप से पुन: तैयार किया जा सकता है। उत्तल समुच्चय पर अवतल कार्य को अधिकतम करने की समस्या को सामान्यतः उत्तल अनुकूलन समस्या कहा जाता है।[14]


गुण

उत्तल अनुकूलन समस्याओं के उपयोगी गुण निम्नलिखित हैं:[15][11]

इन परिणामों का उपयोग कार्यात्मक विश्लेषण (हिल्बर्ट रिक्त स्थान में) जैसे हिल्बर्ट प्रक्षेपण प्रमेय अलग करने वाले हाइपरप्लेन प्रमेय और फ़ार्कस लेम्मा से ज्यामितीय धारणाओं के साथ-साथ उत्तल न्यूनीकरण के सिद्धांत द्वारा किया जाता है।


अनुप्रयोग

निम्नलिखित समस्या वर्ग सभी उत्तल अनुकूलन समस्याएँ हैं या सरल परिवर्तनों के माध्यम से उत्तल अनुकूलन समस्याओं को कम किया जा सकता है:[11][16]

उत्तल अनुकूलन समस्याओं का पदानुक्रम। (एलपी: लीनियर प्रोग्राम, क्यूपी: क्वाड्रैटिक प्रोग्राम, एसओसीपी सेकंड-ऑर्डर कोन प्रोग्राम, एसडीपी: सेमिडेफिनिट प्रोग्राम, सीपी: कोन प्रोग्राम।)

कम से कम वर्गों में दर्शाया गया है:

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


लैग्रेंज गुणक

क्रयमूल्य फलन द्वारा मानक रूप में दी गई उत्तल न्यूनीकरण समस्या पर विचार करें और असमानता की बाधाएं के लिए . फिर डोमेन है:

समस्या के लिए लैग्रेंज फलन है

प्रत्येक बिंदु के लिए में जो कम करता है। ऊपर वास्तविक संख्याएँ उपस्थित हैं लैग्रेंज गुणक कहलाते हैं। जो इन नियमों को एक साथ पूरा करते हैं:

  1. कम करता है कुल मिलाकर
  2. कम से कम एक के साथ
  3. (पूरक शिथिलता)।

अगर कोई पूरी तरह से संभव बिंदु उपस्थित है। अर्थात बिंदु संतुष्टि देने वाला

तो उपरोक्त कथन को उसकी आवश्यकता के लिए शक्तिशाली किया जा सकता है .

इसके विपरीत यदि कुछ में संतुष्ट करता है (1)–(3) स्केलर (गणित) के लिए साथ तब कम करना निश्चित है। जब के ऊपर है।

एल्गोरिदम

अप्रतिबंधित उत्तल अनुकूलन को आसानी से ढतला हुआ वंश (स्टीपेस्ट डिसेंट की विधि का विशेष स्थिति) या अनुकूलन में न्यूटन की विधि के साथ हल किया जा सकता है। न्यूटन की विधि उपयुक्त चरण आकार के लिए लाइन खोज के साथ संयुक्त है। इन्हें गणितीय रूप से शीघ्रता से अभिसरण करने के लिए सिद्ध किया जा सकता है। विशेष रूप से बाद वाली विधि अत्यधिक प्रयोग की जाती है।[21] रैखिक समानता बाधाओं के साथ उत्तल अनुकूलन को केकेटी मैट्रिक्स विधियों का उपयोग करके भी हल किया जा सकता है। यदि उद्देश्य फ़ंक्शन द्विघात फ़ंक्शन है (जो न्यूटन की विधि की भिन्नता के लिए सामान्य है। जो काम करता है। परन्तु आरंभीकरण बिंदु बाधाओं को पूरा नहीं करता है। किन्तु यह भी कर सकता है। सामान्यतः रैखिक बीजगणित के साथ समानता की बाधाओं को दूर करके या दोहरी समस्या को हल करके हल किया जा सकता है।[21] अंत में रैखिक समानता बाधाओं और उत्तल असमानता बाधाओं दोनों के साथ उत्तल अनुकूलन को ऑब्जेक्टिव फ़ंक्शन प्लस लॉगरिदमिक बैरियर फ़ंक्शन नियमों के लिए अप्रतिबंधित उत्तल अनुकूलन विधि प्रारम्भ करके हल किया जा सकता है।[21] जब प्रारंभिक बिंदु संभव नहीं है। अर्थात बाधाओं को संतुष्ट करना। यह तथाकथित चरण विधियों से पहले होता है। जो या तो व्यवहार्य बिंदु ढूंढते हैं या दिखाते हैं कि कोई भी अस्तित्व में नहीं है। चरण I विधियों में सामान्यतः प्रश्न में खोज को कम करना सम्मिलित है। अभी तक उत्तल अनुकूलन समस्या के लिए[21] उत्तल अनुकूलन समस्याओं को निम्नलिखित समकालीन प्रकारों से भी हल किया जा सकता है:[22]

  • सबग्रेडिएंट मेथड सबग्रेडिएंट-प्रोजेक्शन एंड बंडल मेथड्स (वोल्फ, लेमारेचल, किवील), और
  • सबग्रेडिएंट मेथड सबग्रेडिएंट-प्रोजेक्शन एंड बंडल मेथड्स मेथड्स (पॉलीक),
  • आंतरिक बिंदु[1] जो स्व-समन्वय फलन स्व-समन्वय अवरोधक प्रकार्यों का उपयोग करते हैं [23] और स्व-नियमित बाधा कार्य।[24]
  • कटिंग-प्लेन
  • दीर्घवृत्त विधि
  • सबग्रेडिएंट विधि
  • ड्रिफ्ट प्लस पेनल्टी डुअल सबग्रेडिएंट्स और ड्रिफ्ट-प्लस-पेनल्टी विधि

सबग्रेडिएंट विधियों को आसानी से प्रयोग किया जा सकता है और इसलिए व्यापक रूप से उपयोग किया जाता है।[25] दोहरी सबग्रेडिएंट विधियाँ द्वैत (अनुकूलन) पर प्रयोग सबग्रेडिएंट विधियाँ हैं। ड्रिफ्ट-प्लस-पेनल्टी विधि दोहरी सबग्रेडिएंट विधि के समान है। किन्तु प्रारंभिक चर का समय औसत लेती है।


कार्यान्वयन

उत्तल अनुकूलन और संबंधित एल्गोरिदम को निम्नलिखित सॉफ्टवेयर प्रोग्रामों में प्रयोग किया गया है:

कार्यक्रम भाषा विवरण फोस? संदर्भ
सीवीएक्स मैटलैब से डू एमआई और एसडीपीटी3 सॉल्वर के साथ इंटरफेस; केवल उत्तल अनुकूलन समस्याओं को व्यक्त करने के लिए डिज़ाइन किया गया। सही [26]
सीवीएक्समॉड पाइथन सीवी एक्सओपीटी सॉल्वर के साथ इंटरफेस। सही [26]
सीवीएक्सपीवाई पाइथन [27]
कॉनवेक्स जेएल जूलिया अनुशासित उत्तल प्रोग्रामिंग, कई सॉल्वरों का समर्थन करता है। सही [28]
सीवीएक्सआर आर सही [29]
यालमिप मैटलैब आक्टेव सीपीलेक्स, गुरोबी, मोसेक, एसडीपीटी3, सेडुमि, सीएसडीपी, एसडीपीए, पेनान सॉल्वर के साथ इंटरफेस; पूर्णांक और गैर-रैखिक अनुकूलन और कुछ गैर-उत्तल अनुकूलन का भी समर्थन करता है। एलपी/एसओसीपी/एसडीपी बाधाओं में अनिश्चितता के साथ शक्तिशाली अनुकूलन कर सकते हैं। सही [26]
एलएमआई लैब मैटलैब अर्ध-निश्चित प्रोग्रामिंग समस्याओं को व्यक्त करता है और हल करता है (जिसे "रैखिक मैट्रिक्स असमानताएं" कहा जाता है) नहीं [26]
एलएमआई लैब ट्रान्सलेटर एलएमआईएन लैब की समस्याओं को एसडीपी समस्याओं में बदल देता है। सही [26]
एक्एसलएमआई मैटलैब एलएमआई लैब के समान, किन्तु सेडुमी सॉल्वर का उपयोग करता है। सही [26]
एम्स रैखिक प्रोग्रामिंग पर शक्तिशाली अनुकूलन कर सकते हैं (द्वितीय क्रम शंकु प्रोग्रामिंग को हल करने के लिए मोसेक के साथ) और मिश्रित पूर्णांक रैखिक प्रोग्रामिंग। एलपी + एसडीपी और शक्तिशाली संस्करणों के लिए मॉडलिंग पैकेज। नहीं [26]
रोमे शक्तिशाली अनुकूलन के लिए मॉडलिंग प्रणाली। वितरण रूप से शक्तिशाली अनुकूलन और अनिश्चितता समुच्चय का समर्थन करता है। . सही [26]
ग्लोप्टीपोली 3 मैटलैब ऑक्टेव बहुपद अनुकूलन के लिए मॉडलिंग प्रणाली। सही [26]
सॉस टूल्स बहुपद अनुकूलन के लिए मॉडलिंग प्रणाली। एसडीपीटी3 और सेडूमी का उपयोग करता है। प्रतीकात्मक संगणना टूलबॉक्स की आवश्यकता है। सही [26]
विरल पीओपी बहुपद अनुकूलन के लिए मॉडलिंग प्रणाली। एसडीपीए या सेडूमी सॉल्वर का उपयोग करता है। सही [26]
सीप्लेक्स एलपी + एसओसीपी के लिए प्रारंभिक-दोहरी विधियों का समर्थन करता है। एलपी, क्यूपी, एसओसीपी और मिश्रित पूर्णांक रैखिक प्रोग्रामिंग समस्याओं को हल कर सकते हैं। नहीं [26]
एसडीपी सी एलपी + एसडीपी के लिए प्रारंभिक-दोहरी विधियों का समर्थन करता है। मैटलैब आर और पाइथन के लिए उपलब्ध इंटरफेस। समानांतर संस्करण उपलब्ध है। एसडीपी सॉल्वर। सही [26]
सीवीएक्सओपीटी पाइथन एलपी + एसओसीपी + एसडीपी के लिए प्रारंभिक-दोहरी विधियों का समर्थन करता है। नेस्टरोव-टोड स्केलिंग का उपयोग करता है। मोसेक और डीएसडीपी

के लिए इंटरफेस।

सही [26]
मोसेक एलपी + एसओसीपी के लिए प्रारंभिक-दोहरी विधियों का समर्थन करता है। नहीं [26]
सेडूमी मैटलैब ऑक्टेव

मेक्स

एलपी + एसओसीपी + एसडीपी हल करता है। एलपी + एसओसीपी + एसडीपी के लिए प्रारंभिक-दोहरी विधियों का समर्थन करता है। सही [26]
एसडीपीटी सी++ एलपी + एसडीपी हल करता है। एलपी + एसडीपी के लिए प्रारंभिक-दोहरी विधियों का समर्थन करता है। समानांतर और विस्तारित सटीक संस्करण उपलब्ध हैं। सही [26]
सीएसडीपी3 मैटलैब ऑक्टेव मेक्स एलपी + एसओसीपी + एसडीपी हल करता है। एलपी + एसओसीपी + एसडीपी के लिए प्रारंभिक-दोहरी विधियों का समर्थन करता है। सही [26]
कोनिक बन्डल एलपी + एसओसीपी + एसडीपी के लिए सामान्य प्रयोजन कोड का समर्थन करता है। एक बंडल विधि का उपयोग करता है। एसडीपी और एसओसीपी बाधाओं के लिए विशेष समर्थन। सही [26]
डीएसडीपी एलपी + एसडीपी के लिए सामान्य प्रयोजन कोड का समर्थन करता है। दोहरी आंतरिक बिंदु विधि का उपयोग करता है। सही [26]
लोको एसओपीसी के लिए सामान्य-उद्देश्य कोड का समर्थन करता है, जिसे वह अरेखीय प्रोग्रामिंग समस्या के रूप में मानता है। नहीं [26]
छोटा झंडा सामान्य-उद्देश्य कोड का समर्थन करता है। संवर्धित लाग्रंगियन विधि का उपयोग करता है, विशेष रूप से एसडीपी बाधाओं के साथ समस्याओं के लिए। नहीं [26]
डीएसडीपीआर सामान्य-उद्देश्य कोड का समर्थन करता है। संवर्धित लाग्रंगियन विधि के साथ निम्न-श्रेणी गुणनखंडन का उपयोग करता है। सही [26]
जीएएमएस रेखीय, अरैखिक, मिश्रित पूर्णांक रेखीय/अरैखिक, और दूसरे क्रम की शंकु प्रोग्रामिंग समस्याओं के लिए मॉडलिंग प्रणाली। नहीं [26]
अनुकूलन सेवाएं एन्कोडिंग अनुकूलन समस्याओं और समाधानों के लिए एक्सएमएल मानक। [26]


एक्सटेंशन

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


यह भी देखें

टिप्पणियाँ

  1. 1.0 1.1 Nesterov & Nemirovskii 1994
  2. Murty, Katta; Kabadi, Santosh (1987). "Some NP-complete problems in quadratic and nonlinear programming". Mathematical Programming. 39 (2): 117–129. doi:10.1007/BF02592948. hdl:2027.42/6740. S2CID 30500771.
  3. Sahni, S. "Computationally related problems," in SIAM Journal on Computing, 3, 262--279, 1974.
  4. 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.
  5. Boyd & Vandenberghe 2004, p. 17
  6. Chritensen/Klarbring, chpt. 4.
  7. Boyd & Vandenberghe 2004
  8. Schmit, L.A.; Fleury, C. 1980: Structural synthesis by combining approximation concepts and dual methods. J. Amer. Inst. Aeronaut. Astronaut 18, 1252-1260
  9. Boyd & Vandenberghe 2004, p. 8
  10. Hiriart-Urruty, Jean-Baptiste; Lemaréchal, Claude (1996). Convex analysis and minimization algorithms: Fundamentals. p. 291. ISBN 9783540568506.
  11. 11.0 11.1 11.2 11.3 Boyd & Vandenberghe 2004, chpt. 4
  12. Boyd & Vandenberghe 2004, chpt. 2
  13. "Convex Problems".
  14. "Optimization Problem Types - Convex Optimization". 9 January 2011.
  15. Rockafellar, R. Tyrrell (1993). "Lagrange multipliers and optimality" (PDF). SIAM Review. 35 (2): 183–238. CiteSeerX 10.1.1.161.7209. doi:10.1137/1035044.
  16. Agrawal, Akshay; Verschueren, Robin; Diamond, Steven; Boyd, Stephen (2018). "A rewriting system for convex optimization problems" (PDF). Control and Decision. 5 (1): 42–60. arXiv:1709.04494. doi:10.1080/23307706.2017.1397554. S2CID 67856259.
  17. 17.0 17.1 17.2 17.3 17.4 Boyd, Stephen; Diamond, Stephen; Zhang, Junzi; Agrawal, Akshay. "Convex Optimization Applications" (PDF). Archived (PDF) from the original on 2015-10-01. Retrieved 12 Apr 2021.
  18. 18.0 18.1 18.2 Malick, Jérôme (2011-09-28). "Convex optimization: applications, formulations, relaxations" (PDF). Archived (PDF) from the original on 2021-04-12. Retrieved 12 Apr 2021.
  19. Ben Haim Y. and Elishakoff I., Convex Models of Uncertainty in Applied Mechanics, Elsevier Science Publishers, Amsterdam, 1990
  20. Ahmad Bazzi, Dirk TM Slock, and Lisa Meilhac. "Online angle of arrival estimation in the presence of mutual coupling." 2016 IEEE Statistical Signal Processing Workshop (SSP). IEEE, 2016.
  21. 21.0 21.1 21.2 21.3 Boyd, Stephen; Vandenberghe, Lieven (2004). Convex Optimization (PDF). Cambridge University Press. ISBN 978-0-521-83378-3. Retrieved 12 Apr 2021.{{cite book}}: CS1 maint: url-status (link)
  22. For methods for convex minimization, see the volumes by Hiriart-Urruty and Lemaréchal (bundle) and the textbooks by Ruszczyński, Bertsekas, and Boyd and Vandenberghe (interior point).
  23. Nesterov, Yurii; Arkadii, Nemirovskii (1995). Interior-Point Polynomial Algorithms in Convex Programming. Society for Industrial and Applied Mathematics. ISBN 978-0898715156.
  24. Peng, Jiming; Roos, Cornelis; Terlaky, Tamás (2002). "Self-regular functions and new search directions for linear and semidefinite optimization". Mathematical Programming. 93 (1): 129–171. doi:10.1007/s101070200296. ISSN 0025-5610. S2CID 28882966.
  25. Bertsekas
  26. 26.00 26.01 26.02 26.03 26.04 26.05 26.06 26.07 26.08 26.09 26.10 26.11 26.12 26.13 26.14 26.15 26.16 26.17 26.18 26.19 26.20 26.21 26.22 26.23 26.24 Borchers, Brian. "An Overview Of Software For Convex Optimization" (PDF). Archived from the original (PDF) on 2017-09-18. Retrieved 12 Apr 2021.
  27. "Welcome to CVXPY 1.1 — CVXPY 1.1.11 documentation". www.cvxpy.org. Retrieved 2021-04-12.
  28. Udell, Madeleine; Mohan, Karanveer; Zeng, David; Hong, Jenny; Diamond, Steven; Boyd, Stephen (2014-10-17). "Convex Optimization in Julia". arXiv:1410.4821 [math.OC].
  29. "Disciplined Convex Optimiation - CVXR". www.cvxgrp.org. Retrieved 2021-06-17.


संदर्भ

  • Ruszczyński, Andrzej (2006). Nonlinear Optimization. Princeton University Press.
  • Schmit, L.A.; Fleury, C. 1980: Structural synthesis by combining approximation concepts and dual methods. J. Amer. Inst. Aeronaut. Astronaut 18, 1252-1260


बाहरी संबंध

| group5 = Metaheuristics | abbr5 = heuristic | list5 =

| below =

}} | group5 =Metaheuuristic |abbr5 = heuristic | list5 =*विकासवादी एल्गोरिथ्म

| below =* सॉफ्टवेयर

}}