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

From Vigyanwiki
No edit summary
No edit summary
Line 39: Line 39:
* प्रत्येक [[स्थानीय न्यूनतम]] एक [[वैश्विक न्यूनतम]] है;
* प्रत्येक [[स्थानीय न्यूनतम]] एक [[वैश्विक न्यूनतम]] है;
* इष्टतम सेट उत्तल है;
* इष्टतम सेट उत्तल है;
* यदि उद्देश्य फ़ंक्शन सख्ती से उत्तल है, तो समस्या में अधिकतम एक इष्टतम बिंदु होता है।
* यदि उद्देश्य फ़ंक्शन सख्ती से उत्तल है। तो समस्या में अधिकतम एक इष्टतम बिंदु होता है।
 
इन परिणामों का उपयोग [[कार्यात्मक विश्लेषण]] (हिल्बर्ट रिक्त स्थान में) जैसे [[हिल्बर्ट प्रक्षेपण प्रमेय]] अलग करने वाले हाइपरप्लेन प्रमेय और फ़ार्कस लेम्मा से ज्यामितीय धारणाओं के साथ-साथ उत्तल न्यूनीकरण के सिद्धांत द्वारा किया जाता है।


इन परिणामों का उपयोग [[कार्यात्मक विश्लेषण]] (हिल्बर्ट रिक्त स्थान में) जैसे [[हिल्बर्ट प्रक्षेपण प्रमेय]], अलग करने वाले हाइपरप्लेन प्रमेय, और फ़ार्कस लेम्मा से ज्यामितीय धारणाओं के साथ-साथ उत्तल न्यूनीकरण के सिद्धांत द्वारा किया जाता है।{{citation needed|date=July 2022}}





Revision as of 00:41, 16 February 2023

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


परिभाषा

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

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

,

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


मानक रूप

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

जहाँ:[11]

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

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

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


गुण

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

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


अनुप्रयोग

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

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

*कम से कम वर्गों

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


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

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

समस्या के लिए Lagrangian समारोह है

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

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

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

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

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

एल्गोरिदम

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

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

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


कार्यान्वयन

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

Program Language Description FOSS? Ref
CVX MATLAB Interfaces with SeDuMi and SDPT3 solvers; designed to only express convex optimization problems. Yes [26]
CVXMOD Python Interfaces with the CVXOPT solver. Yes [26]
CVXPY Python [27]
Convex.jl Julia Disciplined convex programming, supports many solvers. Yes [28]
CVXR R Yes [29]
YALMIP MATLAB, Octave Interfaces with CPLEX, GUROBI, MOSEK, SDPT3, SEDUMI, CSDP, SDPA, PENNON solvers; also supports integer and nonlinear optimization, and some nonconvex optimization. Can perform robust optimization with uncertainty in LP/SOCP/SDP constraints. Yes [26]
LMI lab MATLAB Expresses and solves semidefinite programming problems (called "linear matrix inequalities") No [26]
LMIlab translator Transforms LMI lab problems into SDP problems. Yes [26]
xLMI MATLAB Similar to LMI lab, but uses the SeDuMi solver. Yes [26]
AIMMS Can do robust optimization on linear programming (with MOSEK to solve second-order cone programming) and mixed integer linear programming. Modeling package for LP + SDP and robust versions. No [26]
ROME Modeling system for robust optimization. Supports distributionally robust optimization and uncertainty sets. Yes [26]
GloptiPoly 3 MATLAB,

Octave

Modeling system for polynomial optimization. Yes [26]
SOSTOOLS Modeling system for polynomial optimization. Uses SDPT3 and SeDuMi. Requires Symbolic Computation Toolbox. Yes [26]
SparsePOP Modeling system for polynomial optimization. Uses the SDPA or SeDuMi solvers. Yes [26]
CPLEX Supports primal-dual methods for LP + SOCP. Can solve LP, QP, SOCP, and mixed integer linear programming problems. No [26]
CSDP C Supports primal-dual methods for LP + SDP. Interfaces available for MATLAB, R, and Python. Parallel version available. SDP solver. Yes [26]
CVXOPT Python Supports primal-dual methods for LP + SOCP + SDP. Uses Nesterov-Todd scaling. Interfaces to MOSEK and DSDP. Yes [26]
MOSEK Supports primal-dual methods for LP + SOCP. No [26]
SeDuMi MATLAB, Octave, MEX Solves LP + SOCP + SDP. Supports primal-dual methods for LP + SOCP + SDP. Yes [26]
SDPA C++ Solves LP + SDP. Supports primal-dual methods for LP + SDP. Parallelized and extended precision versions are available. Yes [26]
SDPT3 MATLAB, Octave, MEX Solves LP + SOCP + SDP. Supports primal-dual methods for LP + SOCP + SDP. Yes [26]
ConicBundle Supports general-purpose codes for LP + SOCP + SDP. Uses a bundle method. Special support for SDP and SOCP constraints. Yes [26]
DSDP Supports general-purpose codes for LP + SDP. Uses a dual interior point method. Yes [26]
LOQO Supports general-purpose codes for SOCP, which it treats as a nonlinear programming problem. No [26]
PENNON Supports general-purpose codes. Uses an augmented Lagrangian method, especially for problems with SDP constraints. No [26]
SDPLR Supports general-purpose codes. Uses low-rank factorization with an augmented Lagrangian method. Yes [26]
GAMS Modeling system for linear, nonlinear, mixed integer linear/nonlinear, and second-order cone programming problems. No [26]
Optimization Services XML standard for encoding optimization problems and solutions. [26]


एक्सटेंशन

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


यह भी देखें

टिप्पणियाँ

  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 =* सॉफ्टवेयर

}}