ढाल वंश

Question

मैं ढाल वंश का उपयोग कर एन मानकों में एक समारोह के मिनट खोजने की कोशिश कर रहा हूँ। हालांकि मैं ऐसा करना चाहता हूं कि पैरामीटर के पूर्ण मूल्यों के योग को सीमित करने के दौरान 1 (या < = 1, कोई फर्क नहीं पड़ता)। इस कारण से मैं लैग्रेज गुणक की विधि का उपयोग कर रहा हूं, इसलिए यदि मेरा फ़ंक्शन f (x) है, तो मैं f (x) + lambda * (g (x) -1) को कम कर दूंगा जहां जी (x) एक चिकनी अनुमान है पैरामीटर के पूर्ण मूल्यों का योग।

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

फिलहाल मैं सीजी के पायथन (एससीआई) कार्यान्वयन का उपयोग कर रहा हूं, इसलिए मैं वास्तव में उन सुझावों को प्राथमिकता दूंगा जिनके लिए मुझे सीजी कोड को दोबारा लिखने/ट्विक करने की आवश्यकता नहीं है लेकिन मौजूदा विधि का उपयोग करें।

Answer 1

समस्या यह है कि जब Lagrange गुणकों का उपयोग, महत्वपूर्ण अंक लाग्रंगियन के स्थानीय न्यूनतम में नहीं होती है - वे के बजाय काठी अंक पर होते हैं। चूंकि ढाल वाले मूल एल्गोरिदम को स्थानीय मिनीमा खोजने के लिए डिज़ाइन किया गया है, इसलिए जब आप इसे बाधाओं के साथ समस्या देते हैं तो यह अभिसरण करने में विफल रहता है।

• एक संख्यात्मक विधि है जो काठी अंक खोजने के लिए सक्षम है, उदाहरण के लिए उपयोग:

  आम तौर पर तीन समाधान कर रहे हैं न्यूटन की विधि। हालांकि, इन्हें आमतौर पर ढाल और हेसियन दोनों के लिए विश्लेषणात्मक अभिव्यक्ति की आवश्यकता होती है।

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

व्यक्तिगत रूप से, मैं तीसरे दृष्टिकोण के साथ जाऊंगा, और इसके लिए एक विश्लेषणात्मक अभिव्यक्ति प्राप्त करना बहुत मुश्किल है, तो Lagrangian के ढाल के वर्ग के ढाल के ढाल को खोजने के लिए।

इसके अलावा, आप काफी यह अपने प्रश्न में स्पष्ट नहीं बनाते हैं - आप ढाल वंश का उपयोग कर, या तटरक्षक (संयुग्म ढ़ाल) कर रहे हैं?

Answer 2

शायद बहुत देर हो चुकी ओपी के लिए उपयोगी हो करने के लिए, लेकिन एक ही स्थिति में दूसरों के लिए उपयोगी हो सकता है:

पूर्ण-मूल्य की कमी के साथ एक समस्या अक्सर एक समान समस्या केवल रैखिक की कमी है, से में पुनर्निर्मित किया जा सकता है कुछ "सहायक" चर जोड़ना।

उदाहरण के लिए, समस्या 1 पर विचार करें:

ढूँढें (x1, x2) कि अरेखीय बाधा को च (x1, x2) विषय को कम करता है | x1 | + | x2 | < = 10।

एक रेखीय-बाधा संस्करण, समस्या 2 है:

ढूँढें (x1, x2, x3, x4) है कि कम से कम निम्नलिखित रैखिक कमी के च (x1, x2) विषय:

1. x1 < = x3
2. -x1 < = x3
3. x2 < = x4
4. -x2 < = x4
5. x3 + x4 < = 10

नोट:

• (x1, x2, x3, x4) समस्या 2 के लिए बाधाओं को संतुष्ट करता है, तो (x1, x2) समस्या 1 के लिए की कमी (संतुष्ट क्योंकि x3> = abs (x1), x4> = abs (x2))
• यदि (x1, x2) समस्या 1 के लिए बाधाओं को पूरा करता है, तो हम समस्या के लिए संगत बाधाओं को बढ़ा सकते हैं (x1, x2, x3, x4) 2 x3 = abs (x1), x4 = abs (x2)
• x3, x4 को लक्ष्य फ़ंक्शन
पर कोई प्रभाव नहीं पड़ता है

यह इस प्रकार है कि समस्या 2 के लिए इष्टतम खोजने से आपको समस्या 1 के लिए इष्टतम मिलेगा, और इसके विपरीत।