मजबूत अनुकूलन के लिए एक परिचय [... और एक छोटी सी खरीदारी की सूची मैं भूल गया ...]

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

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

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

और हाँ, यह एक पोस्ट का उदाहरण है जहाँ जटिलता तेजी से बढ़ती है (पहले से ही कचरा) ...

अनुकूलन समस्या का "हल" करने का क्या मतलब है?

आइए एक संक्षिप्त अनुस्मारक के साथ शुरू करते हैं।

सामान्य रूप से अनुकूलन कार्य इस तरह दिखता है:

$$

$$\ min_ {x \ _ in R ^ n} f (x) \\ s.t. \\ x \ _ in $$$

यहां $$$च (x)$ उद्देश्य समारोह कहा जाता है, और $$$X$ - एक वैध सेट।

अनुकूलन समस्या को हल करके हम इस तरह के एक बिंदु का मतलब है $$$X ^ * $ X मे$ जिसके लिए इसे निष्पादित किया जाता है:

$$

$$f (x) - f (x ^ *) \ geq 0, \ Quad \ forall x $ में$$

यह अनिश्चितता के बिना अनुकूलन समस्या को हल करने के लिए मानक अवधारणा है।

अनिश्चितता के साथ अनुकूलन समस्या क्या है?

फ़ंक्शन की उत्पत्ति के बारे में आश्चर्य करने का समय है $$$च (x)$ और सीमाएँ $$$X$ ।

साझा करने के लिए बहुत उपयोगी है

• समस्या का संरचनात्मक तर्क (दूसरे शब्दों में, कौन से कार्य उपयोग किए जाते हैं),
• तकनीकी सीमाएँ (मानव तर्क या डेटा से स्वतंत्र),
• पैरामीटर जो डेटा से मूल्यांकन किए जाते हैं।

उदाहरण के लिए, एक व्यावसायिक व्यक्ति हमारे पास आया और लीनियर प्रोग्रामिंग समस्या को दिखाया:

$$

$$\ min_ {x \ _ R ^ 2} 2.16 x_1 + 3.7 x_2 \\ s.t. \\ 0.973 x_1 + 2.619 x_2 \ leq 3.32 \\ x_1 \ geq 0, x_2 \ geq 0$$

आप इस कार्य को पहली बार देखते हैं। एक आदमी भी (शायद नहीं, लेकिन नीले जैकेट में सब कुछ इतना सार है!)। आप चर का अर्थ नहीं जानते हैं। लेकिन अब भी, बहुत विश्वास के साथ, हम कह सकते हैं कि:

1. सबसे अधिक संभावना है कि कार्य रैखिक है, क्योंकि किसी ने ऐसा तय किया है। रैखिकता वह संरचना है जिसे किसी व्यक्ति ने चुना है।
2. प्रतिबंध $$$x_1 \ geq 0, x_2 \ geq 0$ तकनीकी हैं। यही है, वे "भौतिकी" से आए थे और डेटा से नहीं (उदाहरण के लिए, बिक्री नकारात्मक नहीं हो सकती)।
3. विशिष्ट गुणांक $$$\ {0.973, 2.619, 3.32 \}$ सीमित करने में $$$0.973 x_1 + 2.619 x_2 \ leq 3.32$ हमारे उदाहरण में डेटा से मूल्यांकन किया गया था। यही है, सबसे पहले किसी ने कहा कि चर $$$x_1$ चर के साथ जुड़ा हुआ है $$$x_2$ , तब यह कहा गया था कि संबंध रैखिक है, और अंत में, युग्मन के समीकरण में गुणांक का अनुमान डेटा से लगाया गया था। बाधाओं के लिए भी यही सच है। $$$\ {2.16, 3.7 \}$ उद्देश्य समारोह में।

जब हम अनिश्चितता के साथ कार्यों के बारे में बात करते हैं, तो हम डेटा से अनुमानित मापदंडों में अनिश्चितता पर सटीक निशाना लगाते हैं। हम तकनीकी सीमाओं या समस्या की संरचना के प्रारंभिक विकल्प को नहीं छूते हैं।

हमारी कहानी पर वापस। हमारे पास एक रैखिक समस्या है, किसी ने अनुमान लगाया कि इसमें किसी भी तरह से गुणांक है। यदि हम फ़ंक्शन में गुणांक की प्रकृति के बारे में सही थे, तो वास्तव में हमें घटनाओं के विकास के एक परिदृश्य (समस्या का एक विशिष्ट उदाहरण) के लिए समस्या को हल करने के लिए कहा गया था।

कभी-कभी यह हमारे लिए पर्याप्त होता है, और हम इसे हल करते हैं।

हालांकि, कभी-कभी एक परिदृश्य के लिए एक समस्या को हल करना एक बेवकूफ विचार है (उदाहरण के लिए, यदि समाधान डेटा भिन्नता के लिए बहुत संवेदनशील है)।

इस मामले में क्या करना है, और डेटा में अनिश्चितता कैसे मॉडल करें?

सबसे पहले, ध्यान दें कि डेटा अनिश्चितता हमेशा उद्देश्य फ़ंक्शन से बाधाओं या इसके विपरीत स्थानांतरित की जा सकती है। यह कैसे करना है, कटौती के तहत देखें।

स्टोचस्टिक, ऑनलाइन, मजबूत अनुकूलन और उत्पाद सूची

हमारे पास अनिश्चितता के कई परिदृश्य हो सकते हैं, साथ ही इसके साथ क्या करना है के लिए विकल्प। हम एक सरल उदाहरण के साथ कई मानक दृष्टिकोणों का वर्णन करते हैं।

मुझे नहीं पता कि एक सम्मानित पाठक के साथ स्थिति कैसी है, लेकिन यहां मैं शादी (सफलतापूर्वक) कर रहा हूं और समय-समय पर किराने की दुकान पर जाता हूं। एक पत्ता के साथ, निश्चित रूप से (आवेगी खरीद से अयोग्यता देता है)। कभी-कभी केवल स्टोर तक नहीं, बल्कि सशर्त औचन तक, जहां यह सस्ता है, लेकिन जहां तक ​​जाना है।

हम इस स्थिति को मॉडल करेंगे: हम खरीदारी के लिए अपने हाथों में एक पत्ती के साथ औचन आए।

ध्यान दें, पहला सवाल: मॉडल कैसे करें?

इनपुट: खरीदने के लिए उत्पादों और आवश्यक मात्रा के बारे में जानकारी।

सुविधा के लिए, हम पत्रक को कुछ पूर्णांक गैर-ऋणात्मक वेक्टर के रूप में सोच सकते हैं $$$y \ _ Z _ + ^ n $ मे$ ।

चर के रूप में, हम क्रमशः एक पूर्णांक गैर-नकारात्मक वेक्टर लेते हैं $$$x \ _ Z _ + ^ n $ मे$ - हम कितने और किन उत्पादों को अंततः खरीदेंगे (हमारा समाधान)।

बिंदु छोटा है - कुछ प्रकार के उद्देश्य फ़ंक्शन लेते हैं $$$च (x, y)$ , जो कहता है कि हमने उत्पादों की पसंद के साथ कितनी गलती की।

संदर्भ के आधार पर, फ़ंक्शन का प्रकार बदल सकता है, लेकिन इसके लिए कुछ बुनियादी आवश्यकताएं हैं:

• समारोह $$$च (x, y)$ न्यूनतम होना चाहिए $$$x ^ * = \ arg \ min_ {x \ _ R ^ n} f (x, y) = y$ (यह कि, इष्टतम में हम वही खरीदेंगे जो पत्तल में लिखा गया है)
• समारोह $$$च (x, y)$ में उत्तल होना चाहिए $$$x$ (और अधिमानतः चिकनी) - प्रभावी ढंग से गणना करने में सक्षम होने के लिए $$$मिनट$ ।

इस प्रकार, हम समस्या प्राप्त करते हैं:

$$

$$min_ {x \ _ R ^ n} f (x, y) $ मे$$

अब कल्पना करें कि पत्ता घर पर ही रहे ...

इसलिए, एक टिप्पणी के साथ, हम अनिश्चितता के साथ कार्यों की दुनिया में आ गए।

तो क्या करें अगर टास्क में $$$min_ {x \ _ R ^ n} f (x, y) $ मे$ हमारे लिए अज्ञात है $$$य$ ?

उत्तर, फिर से, संदर्भ पर निर्भर करता है।

स्टोचस्टिक अनुकूलन

स्टोकेस्टिक अनुकूलन (आमतौर पर) शामिल है

• डेटा में अनिश्चितता एक स्टोकेस्टिक प्रकृति की है। गैर-नियतात्मक पैरामीटर मानों के संभाव्य वितरण का पूरा ज्ञान
• अनिश्चितता सहित सीमाएं नरम हैं

हमारे उदाहरण में, यदि हमने स्टोकेस्टिक अनुकूलन का उपयोग करके इसे मॉडल किया है, तो हम कहेंगे

• ठीक है, मुझे पता नहीं है कि पत्रक में क्या लिखा गया था, लेकिन मैं अब 8 साल से पत्रक के साथ चल रहा हूं, और मुझे वेक्टर के वितरण के बारे में अच्छी जानकारी है $$$य$
• भले ही मैं चुनाव के साथ एक गलती करता हूं (यानी साथ $$$x$ ), घर लौटकर मुझे असली पता चला $$$य$ और, अगर मैं पूरी तरह से सुरक्षित नहीं होऊंगा, तो मैं पियेटरोचका तक जाऊंगा और वहां खरीदूंगा, और अधिक महंगा होने के बावजूद।
• अब मैं एक को चुनूंगा $$$x$ , जो मूल उद्देश्य समारोह से कुछ प्रकार के न्यूनतम और त्रुटि के लिए संभव "जुर्माना" को कम करेगा।

यह हमें इस कार्य की ओर ले जाएगा:

$$

$$\ min_ {x \ _ R ^ n} E_y [f (x, y) + \ psi (y, z)] \\ s.t. \\ x + z \ geq y$$

ध्यान दें कि इस कार्य में, हम वास्तविक रूप से दो बार निर्णय लेते हैं: पहला, औचन पर खरीदने का मुख्य निर्णय, जिसके लिए हम जिम्मेदार हैं $$$x$ , तो "त्रुटि सुधार" के साथ $$$z$ ।

इस दृष्टिकोण के साथ मुख्य समस्याएं हैं:

• मापदंडों के वितरण पर अक्सर कोई जानकारी नहीं होती है।
• सीमाएं गंभीर हो सकती हैं (उच्च जोखिम वाले कार्यों के लिए - मृत्यु, बर्बाद, परमाणु या ज़ोंबी सर्वनाश, आदि)
• यह हमेशा "सही गलतियों" (एक निर्णय एक बार किया जाता है) या इसके विपरीत, निर्णय अक्सर संभव नहीं होते हैं (इस मामले में कई नेस्टेड इंटीग्रल होंगे, और यह गिनती करना बहुत मुश्किल होगा)।

ऑनलाइन अनुकूलन

ऑनलाइन अनुकूलन एक ढांचा है जो निरंतर निर्णय लेने की खोज करता है। इस ढांचे में मॉडलिंग के लिए मानक दृष्टिकोण बहु-सशस्त्र डाकुओं में से एक है, जो पहले ही कई बार हैबे के बारे में लिखा जा चुका है।

हमारे खिलौना उदाहरण के संदर्भ में, हम करेंगे:

• लीफलेट के पहले (और कभी इस्तेमाल नहीं किया गया था)
  
• और घर पर हम उन उत्पादों के लिए प्रशंसा / डांटेंगे जिन्हें हमने खरीदा था (उसी समय हम केवल वांछित सेट के बारे में अनुमान लगा सकते थे)
• यह कार्य भोजन खरीदने के साथ-साथ उसके पूर्व, काल्पनिक राजकुमार, कुएं, या उसकी माँ के बेटों के मित्र के रूप में जल्दी से जल्दी सीखना होगा।

मजबूत अनुकूलन

रोबस्ट ऑप्टिमाइजेशन एक न्यूनतम समाधान के विचार का एक तार्किक विस्तार है।

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

इसके अलावा, मैं चाहता हूं कि कार्य को एक साधारण सॉल्वर में धकेल दिया जाए - और वे "किसी रैंडम वैरिएबल के किसी भी कार्यान्वयन के लिए" प्रतिबंधों को नहीं समझेंगे (यदि इन कार्यान्वयनों की कोई सीमित संख्या नहीं है)।

एक पत्रक के साथ समस्या में, निर्णय यहाँ और अभी किया जाना चाहिए और किसी भी परिस्थिति में मान्य रहना चाहिए:

$$

$$\ min_ {x \ _ R ^ n, t \ _ in R} t \\ s.t. \\ f (x, y) \ leq t \ quad \ forall y \\ x \ geq y \ quad \ forall y$$

यह स्पष्ट है कि इस खिलौना उदाहरण में भी, अगर आपको किसी चीज की आवश्यकता नहीं है $$$य$ , तो कोई सार्थक हल नहीं निकलेगा।

तो आप ऐसे कार्यों से कैसे निपटते हैं?

एलपी कार्य उदाहरण का उपयोग करके किसी कार्य का एक मजबूत संस्करण बनाना

अनिश्चितता के साथ एक रैखिक अनुकूलन समस्या पर विचार करें:

$$

$$\ min_ {x \ _ R ^ n} c ^ Tx + d \\ s.t. \\ Ax \ leq b$$

मापदंडों $$$\ start {pmatrix} c ^ T, d \\ A, b \ end {pmatrix}$ डेटा से प्राप्त किए गए थे और इसमें अनिश्चितता शामिल थी।

अनुमान 1: कई मूल्य (कार्यान्वयन) $$$\ start {pmatrix} c ^ T, d \\ A, b \ end {pmatrix}$ को मानकीकृत किया जा सकता है, अर्थात ऐसे हैं $$$\ start {pmatrix} c_0 ^ T, d_0 \\ A_0, b_0 \ end {pmatrix}, \ start {pmatrix} c_1 ^ T, d_1 \\ A_1, b_1 के अंत {pmatrix}, \ dots, \ start {pmatrix } c_k ^ T, d_k \\ A_k, b_k \ end {pmatrix}$ कि किसी भी डेटा कार्यान्वयन $$$\ start {pmatrix} c ^ T, d \\ A, b \ end {pmatrix}$ सेट में निहित है:

$$

$$\ start {pmatrix} c ^ T, d \\ A, b \ end {pmatrix} \ in U = \ बाएँ \ {\ start {pmatrix} c_0 ^ T, d_0 \\ A_0, b0_ अंत {pmatrix} + \ sum_ {i = 1} ^ k \ zeta_i \ start {pmatrix} c_i ^ T, d_i \\ A_i, b_i \ end {pmatrix} | Q \ subset R ^ k \ right \} $ में \ quad \ zeta$$

यहां $$$\ start {pmatrix} c ^ T_0, d_0 \\ A_0, b_0 \ end {pmrixrix}$ "नाममात्र" डेटा कहा जाता है, और $$$\ start {pmatrix} c ^ T_i, d_i \\ A_i, b_i \ end {pmatrix} \ quad (1 \ leq i \ leq k)$ - "पाली"।



हम पहले से ही जानते हैं कि सीमाओं में समस्या की सभी अनिश्चितता को हटाया जा सकता है। चलो करते हैं।

हमें समस्या आती है

$$

$$\ min_ {x \ _ R ^ n, t \ _ in R} t \\ st \\ c ^ Tx + d \ leq t, \ quad \ forall \ start {pmatrix} c ^ T, d \ end {pmatrix_1 U \\ Ax \ leq b में, \ Quad \ forall \ start {pmatrix} A, b \ end {pmatrix} \ U में \\ $$

कार्य का मजबूत संस्करण

अब मजबूत अनुकूलन में सबसे अच्छे ट्रिक में से एक के लिए समय है - कैसे अनंत बाधाओं से अच्छी बाधाओं की एक सीमित संख्या में स्थानांतरित किया जाए।

शुरू करने के लिए, एक साधारण उदाहरण पर विचार करें

$$

$$Q = \ {\ zeta \ _ in R ^ k | \ | \ zeta \ _ | _2 \ leq 1 \}$$

सिस्टम में सभी प्रतिबंध

$$

$$c ^ Tx + d \ leq t, \ quad \ forall \ start {pmatrix} c ^ T, d \ end {pmatrix} \ _ U \\ Ax \ leq b, \ quad \ forall \ start {pm_rix} A में, U \\ $ में b \ end {pmatrix}$$

एक ही प्रकार - यह सिर्फ रैखिक असमानताएं हैं। एक के साथ काम करना सीखो - हर किसी के साथ काम करना सीखो।

इसलिए, हम असमानता प्रकार के एक प्रतिबंध पर विचार करते हैं:

$$

$$a ^ Tx \ leq b \ quad \ forall (a, b) \ u = \ {(a_0, b_0) + \ _ sum_ {i = 1} ^ k \ zeta_i \ cdot (a_i, b_i) में | Q \} \ \ _ \\ (a_0 + \ _ sum_ {i = 1} ^ k \ zeta_i a_i) ^ tx \ leq b_0 + \ sum_ {i = 1} ^ k \ zeta_i b_i \ quad \ forall \ zeta \ zeta \ zeta \ Q \\ \ sum_ {i = 1} ^ k \ zeta_i \ cdot (a_i ^ T x - b_i) \ leq b_0 - a_0 ^ Tx \ quad \ forall \ zeta \ _ \ _ \ _ \ _ _ \ _ zeta \ _ में Q} \ sum_ {i = 1} ^ k \ zeta_i \ cdot (a_i ^ T x - b_i) \ leq b_0 - a_0 ^ Tx$$

मुझे समझाते हैं कि क्या हुआ।

सबसे पहले, हमने असमानता के बाईं ओर अनिश्चितता के साथ सभी भागों को स्थानांतरित कर दिया; $$$\ zeta$ ।
उसके बाद, हमने सबसे खराब मामले (प्रत्येक के लिए) को देखा $$$x$ वह उसका है)।
परिणामस्वरूप, हमें निम्नलिखित रिकॉर्ड मिला:

$$

$$g (x) = अधिकतम _ {\ zeta \ "in Q} f (x, \ zeta) \ leq b_0 - a_0 ^ Tx$$

।

अगला चरण एक स्पष्ट कार्य लिखना है $$$g (x)$ । ऐसा करने के लिए, यह अनुकूलन समस्या को हल करने के लिए पर्याप्त है $$$\ zeta$ और इष्टतम विकल्प $$$\ zeta *$ :

$$

$$\ मैक्स _ {\ _। \ zeta \ _ | _2 \ leq 1} \ sum_ {i = 1} ^ k \ zeta_i (a_i ^ Tx-b_i) = \ sqrt {\ _ sum_ {i> 1} ^ k (a_i ^ Tx) - b_i) ^ 2}$$

जो असमानता की ओर जाता है:

$$

$$\ sqrt {\ _ sum_ {i = 1} ^ k (a_i ^ Tx-b_i) ^ 2} + a_0 ^ Tx \ leq b_0$$

ध्यान दें कि परिणामी असमानता उत्तल और कोई भी है $$$x$ उसे संतुष्ट करने से मूल संतुष्ट होता है $$$^ Tx \ leq b$ किसी भी कार्यान्वयन के लिए $$$(ए, बी) यू $ मे$ ...

बंधन $$$\ sqrt {\ _ sum_ {i = 1} ^ k (a_i ^ Tx-b_i) ^ 2} + a_0 ^ Tx \ leq b_0$ बाधा का मजबूत संस्करण कहा जाता है $$$^ $ $ Tx \ leq b \ quad \ forall (a, b) \ U मे$ ।

यह मजबूत अनुकूलन में मुख्य कार्यदलों में से एक है - उत्तल बाधाओं की परिमित सेट द्वारा संभावना बाधाओं का अनुमान।

अधिक जटिल (गैर-रैखिक) बाधाओं के साथ क्या करना है?

शंकुधारी द्वैत का उपयोग करते हुए बाधाओं के मजबूत संस्करणों का निर्माण

शंक्वाकार रूप में बहुत से मानक अरेखीय अवरोधों का प्रतिनिधित्व किया जा सकता है (अर्थात, रूप में $$$कु + क $ कु मे$ जहाँ $$$K$ कुछ बंद उत्तल शंकु है):

• nonnegativity $$$X \ geq 0 \ quad \ leftrightarrow \ quad x \ R में ^ n _ +$
• सामान्य प्रतिबंध $$$\ | x \ | _p \ leq p \ quad \ leftrightarrow \ quad \ start {pmatrix} x \\ p \ end {pmatrix} \ _ में K_p ^ n = \ left \ {(x, t) \ _ in R ^ n \ बार R_ + | \ Quad \ | x \ | _p \ leq t \ right \}$
• मैट्रिक्स की सकारात्मक निश्चितता में बाधाएं $$$x_1F_1 + \ dots x_nF_n + G \ succeq 0$

वापस मजबूत प्रतिबंधों के लिए।

मान लें कि अनुकूलन समस्या के संबंध में है $$$\ zeta$ एक शंक्वाकार आकार में कमी करने में कामयाब रहे

$$

$$\ मैक्स _ {\ zeta} \ sum_ {i = 1} ^ k \ zeta_i (a_i ^ Tx - b_i) K $ में \\ s.t \\ C \ zeta + d \ $$

हम इस समस्या के लिए एक दोहरी निर्माण करते हैं।

कुछ समय पहले, मैंने इस पोस्ट में तकनीक पर थोड़ा कम ध्यान देने के लिए शंकुधारी द्वैत पर एक पोस्ट प्रकाशित किया था।

$$

$$\ _ K ^ * $ में \\ \ lambda$$

अब यह छोटी बात है - कमजोर द्वंद्व प्रमेय:

$$

$$\ max _ {[\ zeta: \ quad C \ zeta + d \ _ K]} \ ___ {i = 1} ^ k \ zeta_i (a_i ^ Tx-b_i) \ leq \ min _ \ _ lambda \ lambda ^ Td \\ जहाँ \\ G = \ left \ {\ lambda | \ quad C ^ T \ lambda + \ start {pmatrix} a_1 ^ Tx - b_1 \\ \ dots \\ a_k ^ Tx - b_k \ end {pmatrix} = 0_k; K ^ * \ right \} $ में \ quad \ lambda$$

इसलिए, प्रारंभिक बाधा के एक मजबूत सन्निकटन के रूप में $$$^ Tx \ leq b, \ quad (a, b) \ U में$ प्रतिबंध का इस्तेमाल किया जा सकता है

$$

$$\ lambda ^ Td \ leq b_0 - a_0 ^ Tx \\ G = \ left \ {\ _ambda | \ quad C ^ T \ lambda + \ start {pmatrix} a_1 ^ Tx - b_1 \\ \ dots \\ a_k ^ Tx - b_k \ end {pmatrix} = 0_k; K ^ * \ right \} $ में \ quad \ lambda$$

जहाँ $$$\ lambda$ समान चर $$$x$ ।

इसलिए हमने मूल असमानता के लिए एक मजबूत बाधा का निर्माण किया।

निष्कर्ष

हमने अच्छे उत्तल लोगों के एक समूह द्वारा खराब (स्टोचैस्टिक) बाधाओं की अनुमान लगाने की तकनीक की जांच की। यह उपयोगी हो सकता है, उदाहरण के लिए, यदि:

• आप स्वयं एल्गोरिदम लिखना नहीं चाहते हैं, लेकिन आप जिस सॉल्वर का उपयोग कर रहे हैं, वह यह नहीं जानता है कि संभावना बाधाओं के साथ कैसे काम किया जाए।
• स्टोचस्टिक मापदंडों के साथ एक समस्या है, जबकि इष्टतम डेटा में उतार-चढ़ाव के प्रति बहुत संवेदनशील है।
• और, ज़ाहिर है, अनिश्चितता वाले कार्य, जहां सभी प्रतिबंध सख्त हैं (त्रुटि की कीमत बहुत अधिक है)