द्विघात प्रोग्रामिंग

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

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

समस्या निर्माण

के साथ द्विघात प्रोग्रामिंग समस्या n चर और m बाधाओं को निम्नानुसार तैयार किया जा सकता है। दिया गया:

• एक वास्तविक संख्या-मूल्यवान, n-आयामी वेक्टर c,
• एक n×n-आयामी वास्तविक सममित मैट्रिक्स Q,
• एक m×nआयामी वास्तविक मैट्रिक्स (गणित) A, और
• एक m-आयामी असली वेक्टर b,

द्विघात प्रोग्रामिंग का उद्देश्य एक खोजना है n-आयामी वेक्टर x, वो होगा

न्यूनतम	${\tfrac {1}{2}}\mathbf {x} ^{\mathrm {T} }Q\mathbf {x} +\mathbf {c} ^{\mathrm {T} }\mathbf {x}$
विषय को	$A\mathbf {x} \preceq \mathbf {b} ,$

कहाँ x^T के वेक्टर स्थानान्तरण को दर्शाता है x, और अंकन Ax ⪯ b इसका मतलब है कि वेक्टर की हर प्रविष्टि Ax सदिश की संबंधित प्रविष्टि से कम या उसके बराबर है b (घटक-वार असमानता)।

कम से कम वर्ग

एक विशेष मामले के रूप में जब क्यू सकारात्मक निश्चित मैट्रिक्स | सममित सकारात्मक-निश्चित है, तो लागत फ़ंक्शन कम से कम वर्गों में घट जाती है:

न्यूनतम	${\tfrac {1}{2}}\|R\mathbf {x} -\mathbf {d} \|^{2}$
विषय को	$A\mathbf {x} \preceq \mathbf {b} ,$

कहाँ Q = R^TR के चोल्स्की अपघटन से अनुसरण करता है Q और c = −R^T d. इसके विपरीत, इस तरह के किसी भी कम से कम वर्ग कार्यक्रम को सामान्य गैर-स्क्वायर के लिए भी QP के रूप में समान रूप से तैयार किया जा सकता है R आव्यूह।

सामान्यीकरण

किसी फ़ंक्शन को कम करते समय f किसी संदर्भ बिंदु के पड़ोस में x₀, Q इसके हेसियन मैट्रिक्स पर सेट है H(f(x₀)) और c इसकी ग्रेडियेंट पर सेट है ∇f(x₀). एक संबंधित प्रोग्रामिंग समस्या, द्विघात रूप से विवश द्विघात प्रोग्रामिंग, चर पर द्विघात बाधाओं को जोड़कर उत्पन्न की जा सकती है।

समाधान के तरीके

सामान्य समस्याओं के लिए विभिन्न तरीकों का आमतौर पर उपयोग किया जाता है, जिनमें शामिल हैं

* आंतरिक बिंदु विधि,

* सक्रिय सेट,

*संवर्धित Lagrangian विधि,

* संयुग्मी ढाल विधि,

• ग्रेडिएंट प्रोजेक्शन विधि,

* सिंप्लेक्स एल्गोरिदम का विस्तार।

जिस मामले में Q सकारात्मक निश्चित मैट्रिक्स है, समस्या उत्तल अनुकूलन के अधिक सामान्य क्षेत्र का एक विशेष मामला है।

समानता की कमी

द्विघात प्रोग्रामिंग विशेष रूप से सरल होती है जब Q सकारात्मक निश्चित मैट्रिक्स है और केवल समानता की बाधाएं हैं; विशेष रूप से, समाधान प्रक्रिया रैखिक है। Lagrange गुणकों का उपयोग करके और Lagrangian के चरम की तलाश करके, यह आसानी से दिखाया जा सकता है कि समानता की समस्या का समाधान

${\text{Minimize}}\quad {\tfrac {1}{2}}\mathbf {x} ^{\mathrm {T} }Q\mathbf {x} +\mathbf {c} ^{\mathrm {T} }\mathbf {x}$

${\text{subject to}}\quad E\mathbf {x} =\mathbf {d}$

रैखिक प्रणाली द्वारा दिया गया है

${\begin{bmatrix}Q&E^{\top }\\E&0\end{bmatrix}}{\begin{bmatrix}\mathbf {x} \\\lambda \end{bmatrix}}={\begin{bmatrix}-\mathbf {c} \\\mathbf {d} \end{bmatrix}}$

कहाँ λ लैग्रेंज मल्टीप्लायरों का एक सेट है जो साथ में समाधान से निकलता है x.

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

यदि बाधाएँ चरों को बहुत कसकर नहीं जोड़ती हैं, तो चरों को बदलने के लिए एक अपेक्षाकृत सरल हमला है ताकि बाधाएँ बिना शर्त संतुष्ट हों। उदाहरण के लिए मान लीजिए d = 0 (अशून्य के लिए सामान्यीकरण सीधा है)। बाधा समीकरणों को देखते हुए:

$E\mathbf {x} =0$

एक नया चर पेश करें y द्वारा परिभाषित

$Z\mathbf {y} =\mathbf {x}$

कहाँ y का आयाम है x बाधाओं की संख्या घटाएं। तब

$EZ\mathbf {y} =\mathbf {0}$

और अगर Z इसलिए चुना जाता है EZ = 0 बाधा समीकरण हमेशा संतुष्ट रहेगा। ऐसे खोज रहे हैं Z की शून्य जगह खोजने पर जोर देता है E, जो की संरचना के आधार पर कमोबेश सरल है E. द्विघात रूप में प्रतिस्थापन एक अप्रतिबंधित न्यूनीकरण समस्या देता है:

${\tfrac {1}{2}}\mathbf {x} ^{\top }Q\mathbf {x} +\mathbf {c} ^{\top }\mathbf {x} \quad \implies \quad {\tfrac {1}{2}}\mathbf {y} ^{\top }Z^{\top }QZ\mathbf {y} +\left(Z^{\top }\mathbf {c} \right)^{\top }\mathbf {y}$

जिसका समाधान इसके द्वारा दिया गया है:

$Z^{\top }QZ\mathbf {y} =-Z^{\top }\mathbf {c}$

कुछ शर्तों के तहत Q, कम मैट्रिक्स Z^TQZ सकारात्मक निश्चित रहेगा। संयुग्मी प्रवणता पद्धति पर भिन्नता लिखना संभव है जो की स्पष्ट गणना से बचा जाता है Z.

लग्रंगियन द्वैत

See also: दोहरी समस्या

किसी QP की Lagrangian Dual समस्या भी एक QP है। इसे देखने के लिए आइए हम उस मामले पर ध्यान दें जहां c = 0 और Q सकारात्मक निश्चित है। लैग्रेंज गुणक फलन को हम इस प्रकार लिखते हैं

$L(x,\lambda )={\tfrac {1}{2}}x^{\top }Qx+\lambda ^{\top }(Ax-b).$

(Lagrangian) दोहरे कार्य को परिभाषित करना g(λ) जैसा $g(\lambda )=\inf _{x}L(x,\lambda )$, हम का एक infinum पाते हैं L, का उपयोग कर $\nabla _{x}L(x,\lambda )=0$ और सकारात्मक-निश्चितता Q:

$x^{*}=-Q^{-1}A^{\top }\lambda .$

इसलिए दोहरा कार्य है

$g(\lambda )=-{\tfrac {1}{2}}\lambda ^{\top }AQ^{-1}A^{\top }\lambda -\lambda ^{\top }b,$

और इसलिए QP का Lagrangian दोहरा है

${\text{maximize}}_{\lambda \geq 0}\quad -{\tfrac {1}{2}}\lambda ^{\top }AQ^{-1}A^{\top }\lambda -\lambda ^{\top }b$

Lagrangian द्वैत सिद्धांत के अलावा, अन्य द्वैत युग्म हैं (जैसे वोल्फ द्वैत, आदि)।

जटिलता

सकारात्मक-निश्चित मैट्रिक्स के लिए Qदीर्घवृत्ताभ विधि (कमजोर) बहुपद समय में समस्या को हल करती है। यदि, दूसरी ओर, Q अनिश्चित है, तो समस्या एनपी कठिन है। इन गैर-उत्तल समस्याओं के लिए कई स्थिर बिंदु और स्थानीय न्यूनतम हो सकते हैं। वास्तव में, भले ही Q केवल एक नकारात्मक eigenvalue है, समस्या (दृढ़ता से) एनपी-हार्ड है।

पूर्णांक बाधाएँ

कुछ स्थितियाँ ऐसी होती हैं जहाँ सदिश के एक या अधिक अवयव होते हैं x पूर्णांक मान लेने की आवश्यकता होगी। इससे मिश्रित-पूर्णांक द्विघात प्रोग्रामिंग (MIQP) समस्या का निर्माण होता है। MIQP के अनुप्रयोगों में जल संसाधन शामिल हैं और ट्रैकिंग त्रुटि # इंडेक्स फंड निर्माण।

सॉल्वर और स्क्रिप्टिंग (प्रोग्रामिंग) भाषाएं

नाम	संक्षिप्त जानकारी
AIMMS	अनुकूलन और शेड्यूलिंग-प्रकार की समस्याओं को मॉडलिंग और हल करने के लिए एक सॉफ्टवेयर सिस्टम
ALGLIB	डुअल लाइसेंस (जीपीएल/मालिकाना) न्यूमेरिकल लाइब्रेरी (सी++, .नेट)।
एएमपीएल	बड़े पैमाने पर गणितीय अनुकूलन के लिए एक लोकप्रिय मॉडलिंग भाषा।
एपीमॉनिटर	मॉडलिंग और अनुकूलन सुइट के लिए एल.पी., क्यूपी, एनएलपी, मिलप, मिनएलपी, औरडीएई मैटलैब और पायथन में सिस्टम।
आर्टिलिस नाइट्रो	अरेखीय अनुकूलन के लिए एक एकीकृत पैकेज
सीजीएएल	एक खुला स्रोत कम्प्यूटेशनल ज्यामिति पैकेज जिसमें द्विघात प्रोग्रामिंग सॉल्वर शामिल है।
सीप्लेक्स	एक एपीआई (सी, सी ++, जावा, .नेट, पायथन, मैटलैब और आर) के साथ लोकप्रिय सॉल्वर। शिक्षाविदों के लिए नि: शुल्क।
एक्सेल सॉल्वर फ़ंक्शन	स्प्रैडशीट्स के लिए समायोजित एक अरैखिक सॉल्वर जिसमें फ़ंक्शन मूल्यांकन पुनर्गणना कोशिकाओं पर आधारित होते हैं। मूल संस्करण एक्सेल के लिए एक मानक ऐड-ऑन के रूप में उपलब्ध है।
जीएएमएस	गणितीय अनुकूलन के लिए एक उच्च स्तरीय मॉडलिंग प्रणाली
जीएनयू ऑक्टेव	एक नि: शुल्क (इसका लाइसेंस है GPLv3) संख्यात्मक कंप्यूटिंग के लिए सामान्य-उद्देश्य और मैट्रिक्स-उन्मुख प्रोग्रामिंग-भाषा, मैटलैब के समान। जीएनयू ऑक्टेव में क्वाड्रैटिक प्रोग्रामिंग इसके माध्यम से उपलब्ध है qp कमांड
हइस	रैखिक प्रोग्रामिंग (एलपी), मिश्रित-पूर्णांक प्रोग्रामिंग (एमआईपी), और उत्तल द्विघात प्रोग्रामिंग (क्यूपी) मॉडल को हल करने के लिए ओपन-सोर्स सॉफ़्टवेयर
आईएमएसएल	गणितीय और सांख्यिकीय कार्यों का एक सेट जिसे प्रोग्रामर अपने सॉफ्टवेयर अनुप्रयोगों में एम्बेड कर सकते हैं।
आईपीओपीटी	इपॉप्ट (इंटीरियर पॉइंट ऑप्टिमाइज़र) बड़े पैमाने पर नॉनलाइनियर ऑप्टिमाइज़ेशन के लिए एक सॉफ्टवेयर पैकेज है।
मेपल	गणित के लिए सामान्य प्रयोजन प्रोग्रामिंग भाषा। मेपल में द्विघात समस्या का समाधान इसके माध्यम से पूरा किया जाता है QPSolve कमांड.
मैटलैब	संख्यात्मक कंप्यूटिंग के लिए एक सामान्य-उद्देश्य और मैट्रिक्स-उन्मुख प्रोग्रामिंग-भाषा। मैटलैब में द्विघात प्रोग्रामिंग के लिए बेस मैटलैब उत्पाद के अलावा ऑप्टिमाइज़ेशन टूलबॉक्स की आवश्यकता होती है
गणितीय	प्रतीकात्मक और संख्यात्मक क्षमताओं सहित गणित के लिए एक सामान्य-उद्देश्य प्रोग्रामिंग-भाषा।
मोसेक	कई भाषाओं (सी ++, जावा, .नेट, मैटलैब और पायथन) के लिए एपीआई के साथ बड़े पैमाने पर अनुकूलन के लिए एक सॉल्वर।
एनएजी न्यूमेरिकल लाइब्रेरी	द्वारा विकसित गणितीय और सांख्यिकीय दिनचर्या का एक संग्रहसंख्यात्मक एल्गोरिदम समूह या कई प्रोग्रामिंग लैंग्वेज (सी, सी++, फोरट्रान, विजुअल बेसिक, जावा और सी#) और पैकेज (मैटलैब, एक्सेल, आर, लैबव्यू)। एनएजी लाइब्रेरी के ऑप्टिमाइज़ेशन चैप्टर में विरल और गैर-विरल रेखीय बाधा मैट्रिस दोनों के साथ द्विघात प्रोग्रामिंग समस्याओं के लिए रूटीन शामिल हैं, साथ में लीनियर, नॉनलाइनियर के अनुकूलन के लिए रूटीन के साथ, नॉनलाइनियर, बाउंडेड या नो कंस्ट्रेंट्स के साथ लीनियर या नॉनलाइनियर फ़ंक्शंस के वर्गों का योग। . एनएजी लाइब्रेरी में स्थानीय और वैश्विक अनुकूलन दोनों के लिए और निरंतर या पूर्णांक समस्याओं के लिए रूटीन हैं।
पाइथन	अधिकांश उपलब्ध सॉल्वरों के लिए बाइंडिंग के साथ उच्च-स्तरीय प्रोग्रामिंग भाषा। द्विघात प्रोग्रामिंग के माध्यम से उपलब्ध है solve_qp फ़ंक्शन या किसी विशिष्ट सॉल्वर को सीधे कॉल करके.
आर (फोरट्रान)	GPLफ़ंक्शन या एक विशिष्ट सॉल्वर को कॉल करके डायरेक्टली यूनिवर्सल क्रॉस-प्लेटफ़ॉर्म सांख्यिकीय संगणना फ्रेमवर्क। एक्टली
एसएएस / ओआर	लीनियर, इंटीजर, नॉनलाइनियर, डेरिवेटिव-फ्री, नेटवर्क, कॉम्बिनेटोरियल और कंस्ट्रेंट ऑप्टिमाइजेशन के लिए सॉल्वर का एक सूट; बीजगणितीय मॉडलिंग भाषा ऑप्टमॉडल; और विशिष्ट समस्याओं/बाजारों के उद्देश्य से विभिन्न प्रकार के लंबवत समाधान, जिनमें से सभी पूरी तरह से एकीकृत हैं एसएएस सिस्टम.
सुआन्शु	हल करने के लिए ऑप्टिमाइज़ेशन एल्गोरिदम का एक ओपन-सोर्स सूटएल.पी., क्यूपी, एसओसीपी, एसडीपी, एसक्यूपी जावा में
टीके सॉल्वर	यूनिवर्सल टेक्निकल सिस्टम्स, इंक द्वारा व्यावसायिक रूप से घोषित, नियम-आधारित भाषा पर आधारित गणितीय मॉडलिंग और समस्या निवारण सॉफ्टवेयर सिस्टम।
टॉमलैब	वैश्विक अनुकूलन, पूर्णांक प्रोग्रामिंग, सभी प्रकार के न्यूनतम वर्ग, रैखिक, द्विघात और अप्रतिबंधित प्रोग्रामिंग का समर्थन करता है मैटलैब. टॉमलैब जैसे सॉल्वर का समर्थन करता है सीप्लेक्स, स्नाप्त और नाइट्रो.
एक्सप्रेस	बड़े पैमाने पर रैखिक कार्यक्रमों, द्विघात कार्यक्रमों, सामान्य गैर-रैखिक और मिश्रित-पूर्णांक कार्यक्रमों के लिए सॉल्वर। कई प्रोग्रामिंग भाषाओं के लिए एपीआई है, एक मॉडलिंग भाषा मोसेल भी है और एएमपीएल के साथ काम करती है, जीएएमएस. अकादमिक उपयोग के लिए नि: शुल्क।

यह भी देखें

• अनुक्रमिक द्विघात प्रोग्रामिंग
• रैखिक प्रोग्रामिंग
• क्रिटिकल लाइन विधि

अग्रिम पठन

• Cottle, Richard W.; Pang, Jong-Shi; Stone, Richard E. (1992). The linear complementarity problem. Computer Science and Scientific Computing. Boston, MA: Academic Press, Inc. pp. xxiv+762 pp. ISBN 978-0-12-192350-1. MR 1150683.
• Garey, Michael R.; Johnson, David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 978-0-7167-1045-5. A6: MP2, pg.245.
• Gould, Nicholas I. M.; Toint, Philippe L. (2000). "A Quadratic Programming Bibliography" (PDF). RAL Numerical Analysis Group Internal Report 2000-1.

बाहरी संबंध

• A page about QP
• NEOS Optimization Guide: Quadratic Programming
• Quadratic Programming

| group5 = Metaheuristics | abbr5 = heuristic | list5 =

• Evolutionary algorithm
• Hill climbing
• Local search
• Simulated annealing
• Tabu search

| below =

• Software

}} | group5 =Metaheuuristic |abbr5 = heuristic | list5 =*विकासवादी एल्गोरिथ्म

• पहाड़ी की चढ़ाई
• स्थानीय खोज
• तैयार किए हुयी धातु पे पानी चढाने की कला
• तब्बू खोज

| below =* सॉफ्टवेयर

}}