प्रबल अनुकूलन

प्रबल अनुकूलन गणितीय अनुकूलन सिद्धांत का क्षेत्र है जो अनुकूलन समस्याओं से संबंधित है जिसमें अनिश्चितता के विरूद्ध प्रबल से निश्चित उपाय मांगा जाता है जिसे समस्या के मापदंडों के मान और/या उसके समाधान में नियतात्मक परिवर्तनशीलता के रूप में दर्शाया जाता है।

इतिहास

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

उदाहरण 1

निम्नलिखित रैखिक प्रोग्रामन समस्या पर विचार करें

$\max _{x,y}\ \{3x+2y\}\ \ \mathrm {subject\ to} \ \ x,y\geq 0;cx+dy\leq 10,\forall (c,d)\in P$

जहाँ $P$ का उपसमुच्चय $\mathbb {R} ^{2}$ है।

यह 'प्रबल अनुकूलन' $\forall (c,d)\in P$ की समस्या है जिसे बाधाओं के रूप में खंडित किया जाता हैं। इसका निहितार्थ यह है कि $(x,y)$ के लिए स्वीकार्य होने के लिए, बाधा $cx+dy\leq 10$ सबसे बुरी स्थिति जैसे $(c,d)\in P$ से संबंधित $(x,y)$, अर्थात् जोड़ी $(c,d)\in P$ से संतुष्ट होना चाहिए जो $cx+dy$ दिए गए मान के लिए $(x,y)$ के मान को अधिकतम मान प्राप्त करता है।

यदि पैरामीटर स्थान $P$ परिमित है (परिमित रूप से कई तत्वों से मिलकर), तो यह प्रबल अनुकूलन समस्या स्वयं रैखिक प्रोग्रामिंग समस्या है: प्रत्येक के लिए $(c,d)\in P$ रेखीय बाधा है $cx+dy\leq 10$.

यदि $P$ परिमित समुच्चय नहीं है, तो यह समस्या रैखिक अर्ध-अनंत प्रोग्रामिंग समस्या है, अर्थात् रैखिक प्रोग्रामिंग समस्या जिसमें बहुत से (2) निर्णय चर और असीम रूप से कई बाधाएँ उत्पन्न कर देता हैं।

वर्गीकरण

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

स्थानीय प्रबल

यह ऐसे स्थिति हैं जहां पैरामीटर के नाममात्र मान में छोटी गड़बड़ी के विरूद्ध प्रबल स्थान की मांग की जाती है। स्थानीय प्रबल का बहुत ही लोकप्रिय प्रारूप स्थिरता त्रिज्या प्रारूप है:

${\hat {\rho }}(x,{\hat {u}}):=\max _{\rho \geq 0}\ \{\rho :u\in S(x),\forall u\in B(\rho ,{\hat {u}})\}$

जहाँ ${\hat {u}}$ पैरामीटर के नाममात्र मान को दर्शाता है, $B(\rho ,{\hat {u}})$ त्रिज्या की गेंद को दर्शाता है $\rho$ पर केंद्रित है ${\hat {u}}$ और $S(x)$ के मानों के समुच्चय को दर्शाता है $u$ जो निर्णय से जुड़ी दी गई स्थिरता/प्रदर्शन $x$. की शर्तों को पूरा करते हैं।

शब्दों में, निर्णय की प्रबल (स्थिरता का दायरा)। $x$ पर केन्द्रित सबसे बड़ी गेंद की त्रिज्या है ${\hat {u}}$ जिनके सभी तत्व लगाए गए स्थिरता आवश्यकताओं को पूरा करते हैं $x$. तस्वीर ये है:

जहां आयताकार $U(x)$ सभी मानों के समुच्चय $u$ का प्रतिनिधित्व करता है जो $x$ के निर्णय से जुड़ा हुआ है।

वैश्विक प्रबल

सरल सार प्रबल अनुकूलन समस्या पर विचार करें

$\max _{x\in X}\ \{f(x):g(x,u)\leq b,\forall u\in U\}$

जहाँ $U$ के सभी संभावित मानों के समुच्चय को $u$ विचाराधीन रूप से दर्शाता है ।

यह इस प्रकार वैश्विक प्रबल अनुकूलन समस्या है कि प्रबल बाधा $g(x,u)\leq b,\forall u\in U$ है जिसके सभी संभावित मानों $u$ का प्रतिनिधित्व करता है।

यहाँ कठिनाई यह है कि इस प्रकार की वैश्विक बाधा बहुत अधिक मांग वाली हो सकती है क्योंकि $x\in X$ का मान ऐसा नहीं है जो इस बाधा को पूरा करता है। किन्तु यदि ऐसा $x\in X$ सम्मलित है, बाधा बहुत रूढ़िवादी हो सकती है क्योंकि यह $x\in X$ के लिए समाधान देती है, जो बहुत कम स्टाईल के लिए फंक्शन $f(x)$ उत्पन्न करता है जो अन्य निर्णयों $X$ के प्रदर्शन का प्रतिनिधि नहीं है, उदाहरण के लिए हो सकता है $x'\in X$ यह केवल प्रबल की बाधा का थोड़ा सा उल्लंघन करता है किन्तु बहुत बड़ा फंक्शन $f(x')$ देता है। ऐसे स्थितियों में प्रबल की कमी को थोड़ा आराम देना और/या समस्या के बयान को संशोधित करना आवश्यक हो सकता है।

उदाहरण 2

उस स्थिति पर विचार करें जहां उद्देश्य बाधा को पूरा करना है $g(x,u)\leq b,$. जहाँ $x\in X$ निर्णय चर को दर्शाता है और $u$ पैरामीटर है जिसके लिए संभावित मान $U$ का समुच्चय है, यदि वहाँ कोई नहीं है $x\in X$ ऐसा है कि $g(x,u)\leq b,\forall u\in U$, तो प्रबल का निम्नलिखित सहज ज्ञान युक्त उपाय स्वयं सुझाव देता है:

$\rho (x):=\max _{Y\subseteq U}\ \{size(Y):g(x,u)\leq b,\forall u\in Y\}\ ,\ x\in X$

जहाँ $size(Y)$ समुच्चय के आकार के उपयुक्त माप $Y$ को दर्शाता है, उदाहरण के लिए, यदि $U$ परिमित समुच्चय है, तब $size(Y)$ समुच्चय की प्रमुखता $Y$ के रूप में परिभाषित किया जा सकता है।

यहाँ इन शब्दों में, निर्णय की प्रबल के सबसे बड़े उपसमुच्चय $U$ का आकार है जिसके लिए विवशता $g(x,u)\leq b$ है जो प्रत्येक $u$ के लिए संतुष्ट है। इस समुच्चय में इष्टतम निर्णय तब होता है जिसकी प्रबलता सबसे ज्यादा होती है।

यह निम्नलिखित प्रबल अनुकूलन समस्या उत्पन्न करता है:

$\max _{x\in X,Y\subseteq U}\ \{size(Y):g(x,u)\leq b,\forall u\in Y\}$

वैश्विक प्रबल की यह सहज धारणा व्यवहार में अधिकांशतः उपयोग नहीं की जाती है क्योंकि इससे उत्पन्न होने वाली प्रबल अनुकूलन समस्याएं सामान्यतः (सदैव नहीं) हल करने में बहुत कठिनाई होती हैं।

उदाहरण 3

प्रबल अनुकूलन समस्या पर विचार करें

$z(U):=\max _{x\in X}\ \{f(x):g(x,u)\leq b,\forall u\in U\}$

जहाँ $g$ पर वास्तविक मानवान कार्य है $X\times U$, और मान लें कि प्रबल की बाधा के कारण इस समस्या का कोई व्यवहार्य समाधान नहीं है जिसका मान $g(x,u)\leq b,\forall u\in U$ मुख्यतः बहुत मांग होता है।

इस कठिनाई को दूर करने के लिए, आइए ${\mathcal {N}}$ का अपेक्षाकृत छोटा उपसमुच्चय हो $U$ के सामान्य मानों $u$ का प्रतिनिधित्व करता है, और निम्नलिखित प्रबल अनुकूलन समस्या पर विचार करें:

$z({\mathcal {N}}):=\max _{x\in X}\ \{f(x):g(x,u)\leq b,\forall u\in {\mathcal {N}}\}$

तब से ${\mathcal {N}}$ से बहुत छोटा है $U$, हो सकता है कि इसका इष्टतम समाधान के बड़े हिस्से पर अच्छा प्रदर्शन न करे $U$ और इसलिए $u$ ऊपर $U$ की परिवर्तनशीलता के विरूद्ध प्रबल नहीं हो सकता है।

इस कठिनाई को दूर करने का विधि बाधा $g(x,u)\leq b$ को आराम देना है जिसके मानों के लिए $u$ समुच्चय के बाहर ${\mathcal {N}}$ नियंत्रित विधियों से जिससे कि दूरी के रूप में बड़े उल्लंघनों की अनुमति दी जा सके इस प्रकार $u$ से ${\mathcal {N}}$ का मान बढ़ता है। उदाहरण के लिए, आराम की प्रबल की बाधा पर विचार करें

$g(x,u)\leq b+\beta \cdot dist(u,{\mathcal {N}})\ ,\ \forall u\in U$

जहाँ $\beta \geq 0$ नियंत्रण पैरामीटर है और $dist(u,{\mathcal {N}})$ की दूरी को दर्शाता है $u$ से ${\mathcal {N}}$. इस प्रकार, के लिए $\beta =0$ आराम की प्रबल की बाधा मूल प्रबल की बाधा को कम कर देती है।

यह निम्नलिखित (आराम) प्रबल अनुकूलन समस्या उत्पन्न करता है:

$z({\mathcal {N}},U):=\max _{x\in X}\ \{f(x):g(x,u)\leq b+\beta \cdot dist(u,{\mathcal {N}})\ ,\ \forall u\in U\}$

फंक्शन $dist$ इस प्रकार परिभाषित किया गया है

$dist(u,{\mathcal {N}})\geq 0,\forall u\in U$

और

$dist(u,{\mathcal {N}})=0,\forall u\in {\mathcal {N}}$

और इसलिए आराम की समस्या का इष्टतम समाधान मूल बाधा को संतुष्ट करता है $g(x,u)\leq b$ के सभी मानों के लिए $u$ में ${\mathcal {N}}$. यह आराम की बाधा को भी संतुष्ट करता है

जहाँ $g(x,u)\leq b+\beta \cdot dist(u,{\mathcal {N}})$ समीकरण का उपयोग किया जाता हैं।

गैर-संभाव्य प्रबल अनुकूलन प्रारूप

प्रबल अनुकूलन के इस क्षेत्र में हावी प्रतिमान वाल्ड का मैक्सिमिन प्रारूप है, अर्थात्

$\max _{x\in X}\min _{u\in U(x)}f(x,u)$

जहां $\max$ निर्णय निर्माता का प्रतिनिधित्व करता है, $\min$ प्रकृति का प्रतिनिधित्व करता है, अर्थात् अनिश्चितता, $X$ निर्णय स्थान का प्रतिनिधित्व करता है और $U(x)$ के संभावित मानों के समुच्चय को दर्शाता है $u$ निर्णय से जुड़ा हुआ है $x$. यह जेनेरिक प्रारूप का मौलिक प्रारूप है, और इसे अधिकांशतः मिनिमैक्स या अधिकतम ऑप्टिमाइज़ेशन समस्या के रूप में संदर्भित किया जाता है। गैर-संभाव्यतावादी ('नियतात्मक') प्रारूप विशेष रूप से सिग्नल प्रोसेसिंग के क्षेत्र में प्रबल अनुकूलन के लिए व्यापक रूप से उपयोग किया जा रहा है।

उपरोक्त मौलिक प्रारूप का समतुल्य गणितीय प्रोग्रामिंग (एमपी) है

$\max _{x\in X,v\in \mathbb {R} }\ \{v:v\leq f(x,u),\forall u\in U(x)\}$

इन प्रारूपों में बाधाओं को स्पष्ट रूप से सम्मलित किया जा सकता है। सामान्य विवश मौलिक प्रारूप है

$\max _{x\in X}\min _{u\in U(x)}\ \{f(x,u):g(x,u)\leq b,\forall u\in U(x)\}$

समतुल्य विवश MP प्रारूप को इस प्रकार परिभाषित किया गया है:

$\max _{x\in X,v\in \mathbb {R} }\ \{v:v\leq f(x,u),g(x,u)\leq b,\forall u\in U(x)\}$

संभावित रूप से प्रबल अनुकूलन प्रारूप

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

प्रबल समकक्ष

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

यह भी देखें

• स्थिरता त्रिज्या
• अल्पमहिष्ठ
• मिनिमैक्स अनुमानक
• मिनिमैक्स अवकलन
• प्रबल आँकड़े
• प्रबल निर्णय लेना
• स्टोकेस्टिक प्रोग्रामिंग
• स्टोकेस्टिक अनुकूलन
• सूचना-अंतराल निर्णय सिद्धांत
• तागुची विधि

अग्रिम पठन

• H.J. Greenberg. Mathematical Programming Glossary. World Wide Web, http://glossary.computing.society.informs.org/, 1996-2006. Edited by the INFORMS Computing Society.
• Ben-Tal, A.; Nemirovski, A. (1998). "Robust Convex Optimization". Mathematics of Operations Research. 23 (4): 769–805. CiteSeerX 10.1.1.135.798. doi:10.1287/moor.23.4.769.
• Ben-Tal, A.; Nemirovski, A. (1999). "Robust solutions to uncertain linear programs". Operations Research Letters. 25: 1–13. CiteSeerX 10.1.1.424.861. doi:10.1016/s0167-6377(99)00016-4.
• Ben-Tal, A.; Arkadi Nemirovski, A. (2002). "Robust optimization—methodology and applications". Mathematical Programming, Series B. 92 (3): 453–480. CiteSeerX 10.1.1.298.7965. doi:10.1007/s101070100286. S2CID 1429482.
• Ben-Tal A., El Ghaoui, L. and Nemirovski, A. (2006). Mathematical Programming, Special issue on Robust Optimization, Volume 107(1-2).
• Ben-Tal A., El Ghaoui, L. and Nemirovski, A. (2009). Robust Optimization. Princeton Series in Applied Mathematics, Princeton University Press.
• Bertsimas, D.; Sim, M. (2003). "Robust Discrete Optimization and Network Flows". Mathematical Programming. 98 (1–3): 49–71. CiteSeerX 10.1.1.392.4470. doi:10.1007/s10107-003-0396-4. S2CID 1279073.
• Bertsimas, D.; Sim, M. (2006). "Tractable Approximations to Robust Conic Optimization Problems Dimitris Bertsimas". Mathematical Programming. 107 (1): 5–36. CiteSeerX 10.1.1.207.8378. doi:10.1007/s10107-005-0677-1. S2CID 900938.
• Chen, W.; Sim, M. (2009). "Goal Driven Optimization". Operations Research. 57 (2): 342–357. doi:10.1287/opre.1080.0570.
• Chen, X.; Sim, M.; Sun, P.; Zhang, J. (2008). "A Linear-Decision Based Approximation Approach to Stochastic Programming". Operations Research. 56 (2): 344–357. doi:10.1287/opre.1070.0457.
• Chen, X.; Sim, M.; Sun, P. (2007). "A Robust Optimization Perspective on Stochastic Programming". Operations Research. 55 (6): 1058–1071. doi:10.1287/opre.1070.0441.
• Dembo, R (1991). "Scenario optimization". Annals of Operations Research. 30 (1): 63–80. doi:10.1007/bf02204809. S2CID 44126126.
• Dodson, B., Hammett, P., and Klerx, R. (2014) Probabilistic Design for Optimization and Robustness for Engineers John Wiley & Sons, Inc. ISBN 978-1-118-79619-1
• Gupta, S.K.; Rosenhead, J. (1968). "Robustness in sequential investment decisions". Management Science. 15 (2): 18–29. doi:10.1287/mnsc.15.2.B18.
• Kouvelis P. and Yu G. (1997). Robust Discrete Optimization and Its Applications, Kluwer.
• Mutapcic, Almir; Boyd, Stephen (2009). "Cutting-set methods for robust convex optimization with pessimizing oracles". Optimization Methods and Software. 24 (3): 381–406. CiteSeerX 10.1.1.416.4912. doi:10.1080/10556780802712889. S2CID 16443437.
• Mulvey, J.M.; Vanderbei, R.J.; Zenios, S.A. (1995). "Robust Optimization of Large-Scale Systems". Operations Research. 43 (2): 264–281. doi:10.1287/opre.43.2.264.
• Nejadseyfi, O., Geijselaers H.J.M, van den Boogaard A.H. (2018). "Robust optimization based on analytical evaluation of uncertainty propagation". Engineering Optimization 51 (9): 1581-1603. doi:10.1080/0305215X.2018.1536752.
• Rosenblat, M.J. (1987). "A robust approach to facility design". International Journal of Production Research. 25 (4): 479–486. doi:10.1080/00207548708919855.
• Rosenhead, M.J; Elton, M; Gupta, S.K. (1972). "Robustness and Optimality as Criteria for Strategic Decisions". Operational Research Quarterly. 23 (4): 413–430. doi:10.2307/3007957. JSTOR 3007957.
• Rustem B. and Howe M. (2002). Algorithms for Worst-case Design and Applications to Risk Management, Princeton University Press.
• Sniedovich, M (2007). "The art and science of modeling decision-making under severe uncertainty". Decision Making in Manufacturing and Services. 1 (1–2): 111–136. doi:10.7494/dmms.2007.1.2.111.
• Sniedovich, M (2008). "Wald's Maximin Model: a Treasure in Disguise!". Journal of Risk Finance. 9 (3): 287–291. doi:10.1108/15265940810875603.
• Sniedovich, M (2010). "A bird's view of info-gap decision theory". Journal of Risk Finance. 11 (3): 268–283. doi:10.1108/15265941011043648.
• Wald, A (1939). "Contributions to the theory of statistical estimation and testing hypotheses". The Annals of Mathematics. 10 (4): 299–326. doi:10.1214/aoms/1177732144.
• Wald, A (1945). "Statistical decision functions which minimize the maximum risk". The Annals of Mathematics. 46 (2): 265–280. doi:10.2307/1969022. JSTOR 1969022.
• Wald, A. (1950). Statistical Decision Functions, John Wiley, NY.
• Shabanzadeh, Morteza; Fattahi, Mohammad (2015). "Generation Maintenance Scheduling via robust optimization". 2015 23rd Iranian Conference on Electrical Engineering. pp. 1504–1509. doi:10.1109/IranianCEE.2015.7146458. ISBN 978-1-4799-1972-7. S2CID 8774918.

बाहरी संबंध

• ROME: Robust Optimization Made Easy
• Robust Decision-Making Under Severe Uncertainty
• Robustimizer: Robust optimization software