Sum-of-squares optimization
एक सम-ऑफ-स्क्वायर अनुकूलन कार्यक्रम एक रैखिक लागत कार्य और निर्णय चर पर एक विशेष प्रकार की बाधा के साथ एक अनुकूलन समस्या है। ये बाधाएं इस रूप में हैं कि जब निर्णय चर का उपयोग कुछ बहुपदों में गुणांक के रूप में किया जाता है, तो उन बहुपदों में बहुपद एस. ओ. एस. गुण होना चाहिए। शामिल बहुपदों की अधिकतम डिग्री को तय करते समय, सम-ऑफ-स्क्वायर ऑप्टिमाइजेशन को सेमीडिफाइनाइट प्रोग्रामिंग में ढील के लैसेर पदानुक्रम के रूप में भी जाना जाता है। सम-ऑफ-स्क्वायर अनुकूलन तकनीकों को विभिन्न क्षेत्रों में लागू किया गया है, जिसमें नियंत्रण सिद्धांत (विशेष रूप से, बहुपद सदिश क्षेत्रों द्वारा वर्णित गतिशील प्रणालियों के लिए बहुपद लियापुनोव कार्यों की खोज के लिए), सांख्यिकी, वित्त और मशीन लर्निंग शामिल हैं। "स्क्वेयर्स प्रोग्रामिंग के योग का उपयोग करके नियंत्रण लियापुनोव कार्यों की खोज"। मेंः एलर्टन कॉन्फ़। कम., कंट्रोल एंड कम्प्यूटिंग पर। पीपी। 210-219. </रेफ> ए। चक्रवर्ती, पी. सीलर और जी. बालास, "फॉलिंग-लीफ मोड में एफ/ए-18 उड़ान नियंत्रकों की संवेदनशीलता-अरैखिक विश्लेषण", ए. आई. ए. ए. जर्नल ऑफ गाइडेंस, कंट्रोल एंड डायनेमिक्स, वॉल्यूम। 34 नं. 1 (2011), पीपी। 73-85। अनुकूलन समस्या के लिए एक सदिश और बहुपदों को देखते हुए, एक सम-ऑफ-स्क्वेयर्स अनुकूलन समस्या को इस प्रकार लिखा जाता है यहाँ "एस. ओ. एस". सम-ऑफ-स्क्वेयर्स (एस. ओ. एस.) बहुपदों के वर्ग का प्रतिनिधित्व करता है। मात्राएँ निर्णय चर हैं। एस. ओ. एस. कार्यक्रमों को एस. ओ. एस. बहुपद कार्यक्रम की द्वैतता का उपयोग करके अर्धपरिमित कार्यक्रमों (एस. डी. पी.) में परिवर्तित किया जा सकता है और सकारात्मक-अर्धपरिमित मैट्रिक्स का उपयोग करके सीमित बहुपद अनुकूलन के लिए एक छूट, निम्नलिखित खंड देखें। दोहरी समस्याः सीमित बहुपद अनुकूलन मान लीजिए कि हमारे पास एक-चर बहुपद है, और मान लीजिए कि हम इस बहुपद को एक सबसेट पर कम करना चाहेंगे। इसके अलावा मान लीजिए कि सबसेट पर बाधाओं को अधिकतम डिग्री की बहुपद समानताओं का उपयोग करके कूटबद्ध किया जा सकता है, प्रत्येक रूप जहां अधिकतम डिग्री का बहुपद है। इस अनुकूलन समस्या के लिए एक प्राकृतिक, हालांकि आम तौर पर गैर-उत्तल कार्यक्रम निम्नलिखित हैः जहां-आयामी सदिश अधिकतम डिग्री में प्रत्येक एकाक्षर के लिए एक प्रविष्टि के साथ है, ताकि प्रत्येक मल्टीसेट के लिए, बहुपद के गुणांक का एक मैट्रिक्स है जिसे हम कम करना चाहते हैं, और बहुपद के गुणांक का एक मैट्रिक्स है जो सबसेट पर-th बाधा को कूटबद्ध करता है। हमारे खोज स्थान में अतिरिक्त, निश्चित स्थिरांक सूचकांक, बहुपदों को लिखने की सुविधा के लिए और एक मैट्रिक्स प्रतिनिधित्व में जोड़ा जाता है। यह प्रोग्राम आम तौर पर गैर-उत्तल होता है, क्योंकि बाधाएं () उत्तल नहीं होती हैं। इस न्यूनतम समस्या के लिए एक संभावित उत्तल छूट एक सकारात्मक-समपरिमित मैट्रिक्स के साथ चरों के रैंक-एक मैट्रिक्स को बदलने के लिए अर्धपरिमित प्रोग्रामिंग का उपयोग करती हैः हम आकार के प्रत्येक एकाधिकार को अधिकांश सूचकांकों के एक बहुसमुच्चय द्वारा अनुक्रमित करते हैं। इस तरह के प्रत्येक एकाधिकार के लिए, हम कार्यक्रम में एक चर बनाते हैं, और हम चर को मैट्रिक्स बनाने के लिए व्यवस्थित करते हैं, जहां वास्तविक मैट्रिक्स का सेट होता है जिनकी पंक्तियों और स्तंभों को अधिकतम आकार के तत्वों के बहुसमुच्चय के साथ पहचाना जाता है। फिर हम चर में निम्नलिखित अर्ध-परिमित प्रोग्राम लिखते हैंः इसके अधीनः जहां फिर से बहुपद के गुणांक का मैट्रिक्स है जिसे हम कम करना चाहते हैं, और बहुपद एन्कोडिंग के गुणांक का मैट्रिक्स है जो सबसेट पर-th बाधा है। तीसरा अवरोध यह सुनिश्चित करता है कि मैट्रिक्स के भीतर कई बार दिखाई देने वाले एक एकाधिकार का मूल्य पूरे मैट्रिक्स में बराबर है, और द्विघात रूप में मौजूद समरूपताओं का सम्मान करने के लिए जोड़ा जाता है। द्वैतता कोई भी उपरोक्त अर्ध-परिमित क्रमादेश के दोहरे को ले सकता है और निम्नलिखित क्रमादेश प्राप्त कर सकता हैः हमारे पास बाधा के अनुरूप एक चर है (जहां द्वारा अनुक्रमित प्रविष्टि के लिए शून्य को बचाने वाली सभी प्रविष्टियों के साथ मैट्रिक्स है), प्रत्येक बहुपद बाधा के लिए एक वास्तविक चर और बहुसमुच्चय के प्रत्येक समूह के लिए, हमारे पास समरूपता बाधा के लिए एक दोहरे चर है। धनात्मक-समपरिमितता बाधा यह सुनिश्चित करती है कि किसी भी धनात्मक-समपरिमित मैट्रिक्स के लिए धनात्मक-समपरिमित मैट्रिक्स के लक्षण वर्णन द्वारा हम वैक्टर के लिए लिख सकते हैं। इस प्रकार किसी भी के लिए, जहां हमने अधिकतम डिग्री के बहुपद के गुणांक के साथ वैक्टर की पहचान की है। यह एक सम-ऑफ-स्क्वेयर्स प्रमाण देता है कि मान खत्म हो गया है। उपरोक्त को बहुपद असमानताओं द्वारा परिभाषित क्षेत्रों तक भी विस्तारित किया जा सकता है। सम-ऑफ-स्क्वायर पदानुक्रम सम-ऑफ-स्क्वायर पदानुक्रम (एस. ओ. एस. पदानुक्रम), जिसे लैसेर पदानुक्रम के रूप में भी जाना जाता है, बढ़ती शक्ति और बढ़ती कम्प्यूटेशनल लागत के उत्तल छूट का एक पदानुक्रम है। प्रत्येक प्राकृतिक संख्या के लिए संबंधित उत्तल विश्राम को एस. ओ. एस. पदानुक्रम के th स्तर या-th दौर के रूप में जाना जाता है। सेंट राउंड, जब, एक बुनियादी सेमीडिफाइनाइट प्रोग्राम से मेल खाता है, या अधिकतम डिग्री के बहुपदों पर सम-ऑफ-स्क्वायर ऑप्टिमाइजेशन के लिए। पदानुक्रम के पहले स्तर पर बुनियादी उत्तल कार्यक्रम को-th स्तर तक बढ़ाने के लिए, कार्यक्रम में अतिरिक्त चर और बाधाएं जोड़ी जाती हैं ताकि कार्यक्रम में अधिकतम डिग्री के बहुपदों पर विचार किया जा सके। एस. ओ. एस. पदानुक्रम का नाम इस तथ्य से लिया गया है कि-th स्तर पर वस्तुनिष्ठ फलन का मान दोहरे के माध्यम से अधिकतम डिग्री के बहुपदों का उपयोग करके एक सम-ऑफ-स्क्वायर प्रूफ से घिरा हुआ है (ऊपर "द्वैत" देखें)। नतीजतन, कोई भी सम-ऑफ-स्क्वायर प्रमाण जो अधिकतम डिग्री के बहुपदों का उपयोग करता है, उसका उपयोग वस्तुनिष्ठ मूल्य को बांधने के लिए किया जा सकता है, जिससे किसी को छूट की जकड़न पर गारंटी साबित करने की अनुमति मिलती है। बर्ग के एक प्रमेय के संयोजन में, यह आगे इंगित करता है कि पर्याप्त रूप से कई दौर दिए जाने पर, किसी भी निश्चित अंतराल पर विश्राम मनमाने ढंग से तंग हो जाता है। बर्ग के परिणाम में कहा गया है कि एक सीमित अंतराल के भीतर प्रत्येक गैर-नकारात्मक वास्तविक बहुपद को पर्याप्त रूप से उच्च डिग्री के वास्तविक बहुपदों के योग-वर्ग के साथ उस अंतराल पर सटीकता के भीतर अनुमानित किया जा सकता है, और इस प्रकार यदि बिंदु के एक फलन के रूप में बहुपद वस्तुनिष्ठ मूल्य है, यदि असमानता ब्याज के क्षेत्र में सभी के लिए है, तो इस तथ्य का एक योग-वर्ग प्रमाण होना चाहिए। व्यवहार्य क्षेत्र पर वस्तुनिष्ठ कार्य का न्यूनतम होना चुनते हुए, हमारे पास परिणाम है। कम्प्यूटेशनल लागत चर में एक फ़ंक्शन पर अनुकूलन करते समय, पदानुक्रम के-th स्तर को चर पर एक अर्ध-परिमित कार्यक्रम के रूप में लिखा जा सकता है, और दीर्घवृत्तीय विधि का उपयोग करके समय पर हल किया जा सकता है। सम-ऑफ-स्क्वेयर्स पृष्ठभूमि एक बहुपद वर्गों का योग (एस. ओ. एस.) है यदि ऐसे बहुपद मौजूद हैं। उदाहरण के लिए, वर्गों का योग है जहाँ से ध्यान दें कि यदि वर्गों का योग है तो सभी के लिए। बहुपद एस. ओ. एस. के विस्तृत विवरण available.Parrilo, पी. (2003) "अर्ध-बीजगणितीय समस्याओं के लिए अर्ध-परिमित प्रोग्रामिंग छूट" हैं। गणितीय प्रोग्रामिंग सर। बी 96 (2), 293-320। द्विघात रूपों को व्यक्त किया जा सकता है जहाँ एक सममित मैट्रिक्स है। इसी तरह, डिग्री ≤ 2d "के बहुपदों को इस प्रकार व्यक्त किया जा सकता है कि वेक्टर में डिग्री के सभी एकाक्षर होते हैं। इसे ग्राम मैट्रिक्स रूप के रूप में जाना जाता है। एक महत्वपूर्ण तथ्य यह है कि एस. ओ. एस. केवल तभी है जब एक सममित और धनात्मक-समपरिमित मैट्रिक्स मौजूद हो। यह एस. ओ. एस. बहुपदों और सकारात्मक-अर्ध-परिमित मैट्रिक्स के बीच एक संबंध प्रदान करता है। सॉफ्टवेयर उपकरण SOSTOOLS, जीएनयू जीपीएल के तहत लाइसेंस प्राप्त है। संदर्भ मार्गदर्शिका arXiv: 1310.4716 [math.OC] पर उपलब्ध है, और इसके आंतरिक के बारे में एक प्रस्तुति यहां उपलब्ध है। सी. डी. सी. एस.-एस. ओ. एस., सी. डी. सी. एस. का एक पैकेज है, जो बड़े पैमाने पर एस. ओ. एस. कार्यक्रमों से निपटने के लिए एक संवर्धित लैग्रैन्जियन विधि समाधानक है। जूलिया के लिए जे. यू. एम. पी. का समऑफस्क्वायर्स विस्तार। जूलिया के लिए टी. एस. एस. ओ. एस., एक बहुपद अनुकूलन उपकरण है जो स्पार्सिटी अनुकूलित क्षण-एस. ओ. एस. पदानुक्रम पर आधारित है। सीमित बहुपद अनुकूलन की दोहरी समस्या के लिए, MATLAB/ऑक्टेव के लिए ग्लोप्टीपोली, पायथन के लिए Ncpol2sdPA और जूलिया के लिए मोमेंटऑप्ट। संदर्भ गणितीय अनुकूलन वास्तविक बीजगणितीय ज्यामिति