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

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

इतिहास

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}})$

बाहर ${\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