शंकु द्वैत के बारे में थोड़ा

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

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

इस लेख में मैं शंकुधारी द्वंद्व के बारे में बात करूंगा। मेरी राय में, दोहरे कार्यों के निर्माण का यह तरीका अवांछनीय रूप से ध्यान से वंचित है ...

अगला मटन ...

आमतौर पर दोहरे कार्य कैसे बनाए जाते हैं?

कुछ अनुकूलन समस्या दी जाए:

$$

$$\ min_ {x \ _ R ^ n} f (x) \\ f_i (x) \ leq 0, \ quad 1 \ leq i \ leq k \\ h_i (x) = 0, 1 \ leq i / leq m$$

दोहरी योजना का निर्माण निम्न योजना के अनुसार किया गया है:

• लैग्रैन्जियम का निर्माण करें

$$

$$L (x, \ lambda, \ mu) = f (x) + \ sum_ {i = 1} ^ k \ lambda_i f_i (x) + \ sum_ {i = 1} ^ m \ mu -i h_i (x)$$

• एक दोहरी फ़ंक्शन बनाएँ

$$

$$g (\ lambda, \ mu) = \ inf_x L (x, \ lambda, \ mu)$$

• एक दोहरा कार्य प्राप्त करें

$$

$$\ max _ {\ _ lambda, \ mu} g (\ lambda, \ mu) \\ \ lambda \ geq 0$$

इस योजना में मुख्य कठिनाई खोज चरण में वायर्ड है $$$\ inf_x L (x, \ lambda, \ mu)$ ।

यदि समस्या उत्तल नहीं है, तो यह एक ताबूत है - सामान्य स्थिति में, इसे बहुपद समय में हल नहीं किया जा सकता है (यदि हो तो $$$पी \ neq एनपी$ ) और इस तरह की समस्याओं को हम भविष्य में नहीं छूएंगे।

मान लें कि समस्या उत्तल है, तो क्या?

यदि समस्या सुचारू है, तो हम पहले क्रम की इष्टतमता स्थिति का उपयोग कर सकते हैं $$$\ nabla_x L (x, \ lambda, \ mu) = 0$ । इस स्थिति से, यदि सब कुछ ठीक है, तो यह कटौती करने के लिए या $$$x (\ lambda, \ mu) = \ arg \ min_x L (x, \ lambda, \ mu)$ और $$$g (\ lambda, \ mu) = L (x (\ lambda, \ mu), \ lambda, \ mu)$ या सीधे कार्य करते हैं $$$g (\ lambda, \ mu)$ ।

यदि समस्या सुचारू नहीं है, तो हम पहले-क्रम की स्थिति के एक एनालॉग का उपयोग कर सकते हैं $$$0 \ in \ आंशिक_x L (x, \ lambda, \ mu)$ (यहाँ $$$\ part_x L (x, \ lambda, \ mu)$ किसी फ़ंक्शन की एक सबडिफ़ेरेंशियल को दर्शाता है $$$L (x, \ lambda, \ mu)$ ), हालांकि, यह प्रक्रिया आमतौर पर बहुत अधिक जटिल है।

कभी-कभी एक समतुल्य "चिकनी" अनुकूलन समस्या होती है और एक इसके लिए एक दोहरी निर्माण कर सकता है। लेकिन संरचना के सुधार के लिए (गैर-चिकनी से चिकनी तक), एक नियम के रूप में, आपको हमेशा आयाम में वृद्धि का भुगतान करना होगा।

शंक्वाकार द्वैत

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

$$

$$\ min_ {x \ _ R ^ n} c ^ T $ \\ Ax + b \ _ K $ मे$$

जहाँ $$$ए$ - मैट्रिक्स $$$ब$ - वेक्टर $$$K$ - गैर-पतित उत्तल शंकु।

इस मामले में, दोहरी योजना का निर्माण निम्न योजना के अनुसार किया जा सकता है:

दोहरी योजना का निर्माण निम्न योजना के अनुसार किया गया है:

• लैग्रैन्जियम का निर्माण करें

$$

$$L (x, \ lambda) = c ^ Tx + \ lambda ^ T (Ax + b)$$

• एक दोहरी फ़ंक्शन बनाएँ

$$

$$g (\ lambda) = \ inf_x L (x, \ lambda) = \ start {case} \ lambda ^ T b, \ quad c + A ^ T \ lambda = 0 \\ - \ infty, \ quad c + A ^ T \ lambda \ neq 0 \ end {मामले}$$

• एक दोहरा कार्य प्राप्त करें

$$

$$\ max _ {\ _ lambda} b ^ T \ lambda \\ c + A ^ T \ lambda = 0 \\ - \ lambda \ _ K ^ * $ मे$$

जहां शंकुधारी शंकु है $$$K ^ *$ शंकु के लिए $$$K$ के रूप में परिभाषित किया गया $$$K ^ * = \ left \ {y \ in R ^ k | z ^ T y \ geq 0, \ quad \ forall z \ _ K \ right \} $ मे$ ।

जैसा कि हम देखते हैं, दोहरी समस्या के निर्माण की पूरी जटिलता को दोहरे शंकु के निर्माण में स्थानांतरित कर दी गई थी। लेकिन खुशी यह है कि दोहरे शंकु के निर्माण के लिए एक अच्छी गणना है और बहुत बार एक दोहरे शंकु को तुरंत लिखा जा सकता है।

उदाहरण

मान लें कि हमें समस्या के लिए दोहरी अनुकूलन समस्या का निर्माण करने की आवश्यकता है:

$$

$$\ min_ {x \ _ R ^ n} \ | x \ | _2 + \ _ | x \ | _1 \\ Ax \ geq b$$

यहां $$$\ | x \ | _1 = \ sum_ {i = 1} ^ n | x_i |$ । $$$\ | x \ | _2 = \ sqrt {\ sum_ {i = 1} ^ n x_i ^ 2 =$

पहली चीज जिसे आप नोटिस कर सकते हैं: उद्देश्य फ़ंक्शन को हमेशा रैखिक बनाया जा सकता है!

बल्कि, रैखिक उद्देश्य फ़ंक्शन के साथ हमेशा एक समान समस्या होती है:

$$

$$\ min_ {x \ _ in R ^ n, y \ _ in R, z \ _ in R} y + z \\ | x \ | | _2 \ leq y \\ \ | x \ | \ _ \ _q z \\ Ax \ जेक बी$$

अब आपको थोड़ा गुप्त ज्ञान का उपयोग करने की आवश्यकता है: कई

$$

$$K_1 = \ {(x, t) \ _ R ^ n \ n R में | \ Quad \ | x \ | _1 \ leq t \}$$

और

$$

$$K_2 = \ {(x, t) \ N में R ^ n \ टाइम्स R | \ Quad \ | x \ | _2 \ leq t \}$$

उत्तल शंकु हैं।

इस प्रकार, हम समस्या के बराबर अंकन पर पहुँचते हैं:

$$

$$\ min_ {x \ _ in R ^ n, y \ _ in R, z \ _ R} y + z \\ I_ {n + 1} \ start {pmatrix} x \\ y \ end {pmatrix} + 0_ / n +1} \ _ K_2 \\ I_ {n + 1} \ start {pmatrix} x \\ z \ end {pmatrix} + 0_ {n + 1} \ _ K_1 \\ Ax-b \ _ में R _ + ^ $$$

अब हम तुरंत एक दोहरी समस्या लिख ​​सकते हैं:

$$

$$\ max _ {\ _ lambda, \ mu, \ nu} -b ^ T \ nu \\ \ lambda_i + \ mu_i + [A ^ T \ nu] _i = 0, \ quad 1 / leq i \ leq n \\ \ _ lambda_ { n + 1} + 1 = 0 \\ \ mu_ {n + 1} +1 = 0 \\ - \ lambda \ _ K_2 ^ * (= K_2) \\ - \ mu में K_1 ^ * (= K_ \ _) infty}) \\ - \ n \ _ R ^ k _ + $ मे$$

या, थोड़ा सरल करने के लिए,

$$

$$\ max _ {\ _ lambda, \ mu, \ nu} -b ^ T \ nu \\ \ lambda + \ mu + A ^ T \ nu = 0 \\ \ _ \ _ lambda \ __2_ leq 1 \\ \ _ | mu \ | _ {\ infty} \ leq 1 \\ - \ nu \ _ R ^ k _ + $ मे$$

जहाँ $$$\ _ \ _ \ _ \ _ \ _ infty} = \ max_ {i} | \ mu_$ ।

आगे के अध्ययन के लिए लिंक:

• एस। बॉयड और एल। वेंडरबर्ग, उत्तल अनुकूलन, 2.6 (पृष्ठ 51)।
• ए। बेन-टाल और एल। एल। गौई और ए। नेमीरोव्स्की, रोबस्ट ऑप्टिमाइज़ेशन, ऐप। एक