द्विघात प्रोग्रामिंग: Difference between revisions

Latest revision as of 15:39, 20 October 2023

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

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

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

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

दिया गया:

एक वास्तविक संख्या-मूल्यवान, $n$ -आयामी सदिश $c$ ,
एक $n \times n$ -आयामी वास्तविक सममित आव्यूह $Q$ ,
एक $m \times 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$ , और अंकन $A x ⪯ b$ इसका अर्थ है कि सदिश की हर प्रविष्टि $A x$ सदिश की संबंधित प्रविष्टि से कम या उसके बराबर है $b$ (घटक-वार असमानता)।

कम से कम वर्ग

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

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

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

सामान्यीकरण

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

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

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

आंतरिक बिंदु विधि,
सक्रिय समुच्चय,^[3]
संवर्धित लाग्रंगियन विधि,^[4]
संयुग्मी ढाल विधि,
ग्रेडिएंट प्रोजेक्शन विधि,
सिंप्लेक्स एल्गोरिदम का विस्तार।^[3]

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

समानता की कमी

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

{\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), एक अच्छा संख्यात्मक दृष्टिकोण खोजने के लिए इसे संभावित रूप से बहुत कठिन बना देता है, और समस्या पर निर्भर रहने के लिए कई दृष्टिकोण हैं।^[5]

यदि बाधाएँ चरों को बहुत कसकर नहीं जोड़ती हैं, तो चरों को बदलने के लिए एक अपेक्षाकृत सरल आघात है जिससे बाधाएँ बिना शर्त संतुष्ट हों। उदाहरण के लिए मान लीजिए $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 T QZ$ धनात्मक निश्चित रहेगा। संयुग्मी प्रवणता पद्धति पर भिन्नता लिखना संभव है जो की स्पष्ट गणना से बचा जाता है $Z$ .^[6]

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

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

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

(लाग्रंगियन) दोहरे कार्य को परिभाषित करना $g (λ)$ जैसा $g(\lambda )=\inf _{x}L(x,\lambda )$ , हम का एक इंफिनियम पाते हैं $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,

और इसलिए क्यूपी का लाग्रंगियन दोहरा है

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

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

जटिलता

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

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

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

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

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

यह भी देखें

अनुक्रमिक द्विघात प्रोग्रामिंग

रैखिक प्रोग्रामिंग
क्रिटिकल लाइन विधि

संदर्भ

↑ Wright, Stephen J. (2015), "Continuous Optimization (Nonlinear and Linear Programming)", in Nicholas J. Higham; et al. (eds.), The Princeton Companion to Applied Mathematics, Princeton University Press, pp. 281–293
↑ Nocedal, Jorge; Wright, Stephen J. (2006). Numerical Optimization (2nd ed.). Berlin, New York: Springer-Verlag. p. 449. ISBN 978-0-387-30303-1..
↑ ^3.0 ^3.1 Murty, Katta G. (1988). Linear complementarity, linear and nonlinear programming. Sigma Series in Applied Mathematics. Vol. 3. Berlin: Heldermann Verlag. pp. xlviii+629 pp. ISBN 978-3-88538-403-8. MR 0949214. Archived from the original on 2010-04-01.
↑ Delbos, F.; Gilbert, J.Ch. (2005). "Global linear convergence of an augmented Lagrangian algorithm for solving convex quadratic optimization problems" (PDF). Journal of Convex Analysis. 12: 45–69. Archived (PDF) from the original on 2022-10-09.
↑ Google search.
↑ Gould, Nicholas I. M.; Hribar, Mary E.; Nocedal, Jorge (April 2001). "On the Solution of Equality Constrained Quadratic Programming Problems Arising in Optimization". SIAM J. Sci. Comput. 23 (4): 1376–1395. CiteSeerX 10.1.1.129.7555. doi:10.1137/S1064827598345667.
↑ Kozlov, M. K.; S. P. Tarasov; Leonid G. Khachiyan (1979). "[Polynomial solvability of convex quadratic programming]". Doklady Akademii Nauk SSSR. 248: 1049–1051. Translated in: Soviet Mathematics - Doklady. 20: 1108–1111. {{cite journal}}: Missing or empty |title= (help)
↑ Sahni, S. (1974). "Computationally related problems" (PDF). SIAM Journal on Computing. 3 (4): 262–279. CiteSeerX 10.1.1.145.8685. doi:10.1137/0203021.
↑ Pardalos, Panos M.; Vavasis, Stephen A. (1991). "Quadratic programming with one negative eigenvalue is (strongly) NP-hard". Journal of Global Optimization. 1 (1): 15–22. doi:10.1007/bf00120662. S2CID 12602885.
↑ Lazimy, Rafael (1982-12-01). "Mixed-integer quadratic programming". Mathematical Programming (in English). 22 (1): 332–349. doi:10.1007/BF01581047. ISSN 1436-4646. S2CID 8456219.
↑ Propato Marco; Uber James G. (2004-07-01). "Booster System Design Using Mixed-Integer Quadratic Programming". Journal of Water Resources Planning and Management. 130 (4): 348–352. doi:10.1061/(ASCE)0733-9496(2004)130:4(348).
↑ Cornuéjols, Gérard; Peña, Javier; Tütüncü, Reha (2018). Optimization Methods in Finance (2nd ed.). Cambridge, UK: Cambridge University Press. pp. 167–168. ISBN 9781107297340.

अग्रिम पठन

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.

बाहरी संबंध

[PrincetonCompanion-1] Wright, Stephen J. (2015), "Continuous Optimization (Nonlinear and Linear Programming)", in Nicholas J. Higham; et al. (eds.), The Princeton Companion to Applied Mathematics, Princeton University Press, pp. 281–293

[2] Nocedal, Jorge; Wright, Stephen J. (2006). Numerical Optimization (2nd ed.). Berlin, New York: Springer-Verlag. p. 449. ISBN 978-0-387-30303-1..

[ioe.engin.umich-3] 3.0 ^3.1 Murty, Katta G. (1988). Linear complementarity, linear and nonlinear programming. Sigma Series in Applied Mathematics. Vol. 3. Berlin: Heldermann Verlag. pp. xlviii+629 pp. ISBN 978-3-88538-403-8. MR 0949214. Archived from the original on 2010-04-01.

[4] Delbos, F.; Gilbert, J.Ch. (2005). "Global linear convergence of an augmented Lagrangian algorithm for solving convex quadratic optimization problems" (PDF). Journal of Convex Analysis. 12: 45–69. Archived (PDF) from the original on 2022-10-09.

[5] Google search.

[6] Gould, Nicholas I. M.; Hribar, Mary E.; Nocedal, Jorge (April 2001). "On the Solution of Equality Constrained Quadratic Programming Problems Arising in Optimization". SIAM J. Sci. Comput. 23 (4): 1376–1395. CiteSeerX 10.1.1.129.7555. doi:10.1137/S1064827598345667.

[7] Kozlov, M. K.; S. P. Tarasov; Leonid G. Khachiyan (1979). "[Polynomial solvability of convex quadratic programming]". Doklady Akademii Nauk SSSR. 248: 1049–1051. Translated in: Soviet Mathematics - Doklady. 20: 1108–1111. {{cite journal}}: Missing or empty |title= (help)

[8] Sahni, S. (1974). "Computationally related problems" (PDF). SIAM Journal on Computing. 3 (4): 262–279. CiteSeerX 10.1.1.145.8685. doi:10.1137/0203021.

[9] Pardalos, Panos M.; Vavasis, Stephen A. (1991). "Quadratic programming with one negative eigenvalue is (strongly) NP-hard". Journal of Global Optimization. 1 (1): 15–22. doi:10.1007/bf00120662. S2CID 12602885.

[10] Lazimy, Rafael (1982-12-01). "Mixed-integer quadratic programming". Mathematical Programming (in English). 22 (1): 332–349. doi:10.1007/BF01581047. ISSN 1436-4646. S2CID 8456219.

[11] Propato Marco; Uber James G. (2004-07-01). "Booster System Design Using Mixed-Integer Quadratic Programming". Journal of Water Resources Planning and Management. 130 (4): 348–352. doi:10.1061/(ASCE)0733-9496(2004)130:4(348).

[12] Cornuéjols, Gérard; Peña, Javier; Tütüncü, Reha (2018). Optimization Methods in Finance (2nd ed.). Cambridge, UK: Cambridge University Press. pp. 167–168. ISBN 9781107297340.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

@@ Line 1: / Line 1: @@
 {{Short description|Solving an optimization problem with a quadratic objective function}}
-क्वाड्रैटिक प्रोग्रामिंग (क्यूपी) [[द्विघात फंक्शन]] से जुड़े कुछ [[गणितीय अनुकूलन]] [[अनुकूलन समस्या]] को हल करने की प्रक्रिया है। विशेष रूप से, एक चर पर रैखिक [[विवश अनुकूलन]] के अधीन एक बहुभिन्नरूपी द्विघात फ़ंक्शन को अनुकूलित (न्यूनतम या अधिकतम) करना चाहता है। द्विघात प्रोग्रामिंग एक प्रकार की अरैखिक प्रोग्रामिंग है।
+'''द्विघात प्रोग्रामिंग''' (क्यूपी) द्विघात फलन से जुड़े कुछ [[गणितीय अनुकूलन|गणितीय अनुकूलन समस्याओं]]  को हल करने की प्रक्रिया है। विशेष रूप से, एक चर पर रैखिक विवश अनुकूलन के अधीन एक बहुभिन्नरूपी द्विघात फ़ंक्शन को अनुकूलित (न्यूनतम या अधिकतम) करना चाहता है। द्विघात प्रोग्रामिंग एक प्रकार की अरैखिक प्रोग्रामिंग है।
- इस संदर्भ में प्रोग्रामिंग गणितीय समस्याओं को हल करने के लिए औपचारिक प्रक्रिया को संदर्भित करता है। यह उपयोग 1940 के दशक का है और विशेष रूप से कंप्यूटर प्रोग्रामिंग की हालिया धारणा से जुड़ा नहीं है। भ्रम से बचने के लिए, कुछ व्यवसायी अनुकूलन शब्द पसंद करते हैं - उदाहरण के लिए, द्विघात अनुकूलन।<ref name="PrincetonCompanion">{{Citation|last=Wright|first=Stephen J.|year=2015|title=Continuous Optimization (Nonlinear and Linear Programming)|editor=Nicholas J. Higham|display-editors=etal|encyclopedia=The Princeton Companion to Applied Mathematics|pages=281–293|publisher=Princeton University Press}}</ref>
+इस संदर्भ में प्रोग्रामिंग गणितीय समस्याओं को हल करने के लिए औपचारिक प्रक्रिया को संदर्भित करता है। यह उपयोग 1940 के दशक का है और विशेष रूप से कंप्यूटर प्रोग्रामिंग की हालिया धारणा से जुड़ा नहीं है। भ्रम से बचने के लिए, कुछ व्यवसायी अनुकूलन शब्द पसंद करते हैं - उदाहरण के लिए, द्विघात अनुकूलन।<ref name="PrincetonCompanion">{{Citation|last=Wright|first=Stephen J.|year=2015|title=Continuous Optimization (Nonlinear and Linear Programming)|editor=Nicholas J. Higham|display-editors=etal|encyclopedia=The Princeton Companion to Applied Mathematics|pages=281–293|publisher=Princeton University Press}}</ref>
 == समस्या निर्माण ==
 के साथ द्विघात प्रोग्रामिंग समस्या {{mvar|n}} चर और {{mvar|m}} बाधाओं को निम्नानुसार तैयार किया जा सकता है।<ref>{{Cite book | last1=Nocedal | first1=Jorge | last2=Wright | first2=Stephen J. | title=Numerical Optimization | url=https://archive.org/details/numericaloptimiz00noce_639 | url-access=limited | publisher=[[Springer-Verlag]] | location=Berlin, New York | edition=2nd | isbn=978-0-387-30303-1 | year=2006 | page=[https://archive.org/details/numericaloptimiz00noce_639/page/n469 449] }}.</ref>
 दिया गया:
-* एक [[वास्तविक संख्या]]-मूल्यवान, {{mvar|n}}-आयामी वेक्टर {{math|'''c'''}},
+* एक [[वास्तविक संख्या]]-मूल्यवान, {{mvar|n}}-आयामी सदिश {{math|'''c'''}},
-* एक {{math|''n''×''n''}}-आयामी वास्तविक [[सममित मैट्रिक्स]] {{mvar|Q}},
+* एक {{math|''n''×''n''}}-आयामी वास्तविक सममित आव्यूह {{mvar|Q}},
-* एक {{math|''m''×''n''}}आयामी वास्तविक [[मैट्रिक्स (गणित)]] {{mvar|A}}, और
+* एक {{math|''m''×''n''}}आयामी वास्तविक आव्यूह (गणित) {{mvar|A}}, और
-* एक {{mvar|m}}-आयामी असली वेक्टर {{math|'''b'''}},
+* एक {{mvar|m}}-आयामी असली सदिश {{math|'''b'''}},
-द्विघात प्रोग्रामिंग का उद्देश्य एक खोजना है {{mvar|n}}-आयामी वेक्टर {{math|'''x'''}}, वो होगा
+द्विघात प्रोग्रामिंग का उद्देश्य एक खोजना है {{mvar|n}}-आयामी सदिश {{math|'''x'''}}, वो होगा
 :{| cellspacing="10"
@@ Line 22: / Line 23: @@
 | <math>A \mathbf{x} \preceq \mathbf{b},</math>
 |}
-कहाँ {{math|'''x'''<sup>T</sup>}} के वेक्टर स्थानान्तरण को दर्शाता है {{math|'''x'''}}, और अंकन {{math|''A'''''x''' ⪯ '''b'''}} इसका अर्थ है कि वेक्टर की हर प्रविष्टि {{math|''A'''''x'''}} सदिश की संबंधित प्रविष्टि से कम या उसके बराबर है {{math|'''b'''}} (घटक-वार असमानता)।
+यहाँ {{math|'''x'''<sup>T</sup>}} के सदिश स्थानान्तरण को दर्शाता है {{math|'''x'''}}, और अंकन {{math|''A'''''x''' ⪯ '''b'''}} इसका अर्थ है कि सदिश की हर प्रविष्टि {{math|''A'''''x'''}} सदिश की संबंधित प्रविष्टि से कम या उसके बराबर है {{math|'''b'''}} (घटक-वार असमानता)।
 === कम से कम वर्ग ===
-एक विशेष मामले के रूप में जब क्यू [[सकारात्मक निश्चित मैट्रिक्स]] | सममित सकारात्मक-निश्चित है, तो लागत फ़ंक्शन कम से कम वर्गों में घट जाती है:
+एक विशेष स्थिति के रूप में जब क्यू [[सकारात्मक निश्चित मैट्रिक्स|धनात्मक निश्चित आव्यूह]] | सममित धनात्मक-निश्चित है, तो लागत फ़ंक्शन कम से कम वर्गों में घट जाती है:
 :{| cellspacing="10"
 |-
@@ Line 35: / Line 36: @@
 | <math>A \mathbf{x} \preceq \mathbf{b},</math>
 |}
-कहाँ {{math|1=''Q'' = ''R''<sup>T</sup>''R''}} के [[चोल्स्की अपघटन]] से अनुसरण करता है {{math|''Q''}} और {{math|1='''c''' = −''R''<sup>T</sup> '''d'''}}. इसके विपरीत, इस प्रकार के किसी भी कम से कम वर्ग कार्यक्रम को सामान्य गैर-स्क्वायर के लिए भी QP के रूप में समान रूप से तैयार किया जा सकता है {{math|''R''}} आव्यूह।
+यहाँ {{math|1=''Q'' = ''R''<sup>T</sup>''R''}} के [[चोल्स्की अपघटन]] से अनुसरण करता है {{math|''Q''}} और {{math|1='''c''' = −''R''<sup>T</sup> '''d'''}}. इसके विपरीत, इस प्रकार के किसी भी कम से कम वर्ग कार्यक्रम को सामान्य गैर-स्क्वायर के लिए भी क्यूपी के रूप में समान रूप से तैयार किया जा सकता है {{math|''R''}} आव्यूह।
 === सामान्यीकरण ===
-किसी फ़ंक्शन को कम करते समय {{mvar|f}} किसी संदर्भ बिंदु के पड़ोस में {{math|''x''<sub>0</sub>}}, {{mvar|Q}} इसके [[हेसियन मैट्रिक्स]] पर सेट है {{math|'''H'''(''f''('''x'''<sub>0</sub>))}} और {{math|'''c'''}} इसकी [[ग्रेडियेंट]] पर सेट है {{math|∇''f''('''x'''<sub>0</sub>)}}. एक संबंधित प्रोग्रामिंग समस्या, द्विघात रूप से विवश द्विघात प्रोग्रामिंग, चर पर द्विघात बाधाओं को जोड़कर उत्पन्न की जा सकती है।
+किसी फ़ंक्शन को कम करते समय {{mvar|f}} किसी संदर्भ बिंदु के पड़ोस में {{math|''x''<sub>0</sub>}}, {{mvar|Q}} इसके [[हेसियन मैट्रिक्स|हेसियन आव्यूह]] पर समुच्चय है {{math|'''H'''(''f''('''x'''<sub>0</sub>))}} और {{math|'''c'''}} इसकी [[ग्रेडियेंट]] पर समुच्चय है {{math|∇''f''('''x'''<sub>0</sub>)}}. एक संबंधित प्रोग्रामिंग समस्या, द्विघात रूप से विवश द्विघात प्रोग्रामिंग, चर पर द्विघात बाधाओं को जोड़कर उत्पन्न की जा सकती है।
 == समाधान के तरीके ==
@@ Line 45: / Line 46: @@
 सामान्य समस्याओं के लिए विभिन्न तरीकों का सामान्यतः उपयोग किया जाता है, जिनमें सम्मलित हैं
-: * [[आंतरिक बिंदु विधि]],
+:* आंतरिक बिंदु विधि,
-: * [[सक्रिय सेट]],<ref name="ioe.engin.umich">{{cite book|last=Murty|first=Katta G.|title=Linear complementarity, linear and nonlinear programming|series=Sigma Series in Applied Mathematics|volume=3|publisher=Heldermann Verlag|location=Berlin|year=1988|pages=xlviii+629 pp|isbn=978-3-88538-403-8|url=http://ioe.engin.umich.edu/people/fac/books/murty/linear_complementarity_webbook/|mr=949214|url-status=dead|archive-url=https://web.archive.org/web/20100401043940/http://ioe.engin.umich.edu/people/fac/books/murty/linear_complementarity_webbook/|archive-date=2010-04-01}}</ref>
+:* सक्रिय समुच्चय,<ref name="ioe.engin.umich">{{cite book|last=Murty|first=Katta G.|title=Linear complementarity, linear and nonlinear programming|series=Sigma Series in Applied Mathematics|volume=3|publisher=Heldermann Verlag|location=Berlin|year=1988|pages=xlviii+629 pp|isbn=978-3-88538-403-8|url=http://ioe.engin.umich.edu/people/fac/books/murty/linear_complementarity_webbook/|mr=949214|url-status=dead|archive-url=https://web.archive.org/web/20100401043940/http://ioe.engin.umich.edu/people/fac/books/murty/linear_complementarity_webbook/|archive-date=2010-04-01}}</ref>
-: *[[संवर्धित Lagrangian विधि]],<ref>{{cite journal | first1 = F. | last1 = Delbos | first2 = J.Ch. | last2 = Gilbert | year = 2005 | title = Global linear convergence of an augmented Lagrangian algorithm for solving convex quadratic optimization problems | journal = Journal of Convex Analysis | volume = 12 | pages = 45–69 |url=http://www.heldermann-verlag.de/jca/jca12/jca1203_b.pdf |archive-url=https://ghostarchive.org/archive/20221009/http://www.heldermann-verlag.de/jca/jca12/jca1203_b.pdf |archive-date=2022-10-09 |url-status=live}}</ref>
+:* संवर्धित लाग्रंगियन विधि,<ref>{{cite journal | first1 = F. | last1 = Delbos | first2 = J.Ch. | last2 = Gilbert | year = 2005 | title = Global linear convergence of an augmented Lagrangian algorithm for solving convex quadratic optimization problems | journal = Journal of Convex Analysis | volume = 12 | pages = 45–69 |url=http://www.heldermann-verlag.de/jca/jca12/jca1203_b.pdf |archive-url=https://ghostarchive.org/archive/20221009/http://www.heldermann-verlag.de/jca/jca12/jca1203_b.pdf |archive-date=2022-10-09 |url-status=live}}</ref>
-: * [[संयुग्मी ढाल विधि]],
+:* संयुग्मी ढाल विधि,
 :*ग्रेडिएंट प्रोजेक्शन विधि,
-: * [[सिंप्लेक्स एल्गोरिदम]] का विस्तार।<ref name="ioe.engin.umich" />
+:* सिंप्लेक्स एल्गोरिदम का विस्तार।<ref name="ioe.engin.umich" />
-जिस मामले में {{mvar|Q}} सकारात्मक निश्चित मैट्रिक्स है, समस्या [[उत्तल अनुकूलन]] के अधिक सामान्य क्षेत्र का एक विशेष स्थिति है।
+जिस स्थिति में {{mvar|Q}} धनात्मक निश्चित आव्यूह है, समस्या [[उत्तल अनुकूलन]] के अधिक सामान्य क्षेत्र का एक विशेष स्थिति है।
 === समानता की कमी ===
-द्विघात प्रोग्रामिंग विशेष रूप से सरल होती है जब {{mvar|Q}} सकारात्मक निश्चित मैट्रिक्स है और एकमात्र समानता की बाधाएं हैं; विशेष रूप से, समाधान प्रक्रिया रैखिक है। Lagrange गुणकों का उपयोग करके और Lagrangian के चरम की तलाश करके, यह आसानी से दिखाया जा सकता है कि समानता की समस्या का समाधान
+द्विघात प्रोग्रामिंग विशेष रूप से सरल होती है जब {{mvar|Q}} धनात्मक निश्चित आव्यूह है और एकमात्र समानता की बाधाएं हैं; विशेष रूप से, समाधान प्रक्रिया रैखिक है। लाग्रेंज गुणकों का उपयोग करके और लाग्रंगियन के चरम की तलाश करके, यह आसानी से दिखाया जा सकता है कि समानता की समस्या का समाधान
 :<math>\text{Minimize} \quad \tfrac{1}{2} \mathbf{x}^\mathrm{T} Q\mathbf{x} + \mathbf{c}^\mathrm{T} \mathbf{x}</math>
@@ Line 71: / Line 72: @@
 \begin{bmatrix} -\mathbf c \\ \mathbf d \end{bmatrix}
 </math>
-कहाँ {{math|λ}} लैग्रेंज मल्टीप्लायरों का एक सेट है जो साथ में समाधान से निकलता है {{math|'''x'''}}.
+यहाँ {{math|λ}} लैग्रेंज मल्टीप्लायरों का एक समुच्चय है जो साथ में समाधान से निकलता है {{math|'''x'''}}.
-इस प्रणाली तक पहुँचने का सबसे आसान साधन प्रत्यक्ष समाधान है (उदाहरण के लिए, LU गुणन), जो छोटी समस्याओं के लिए बहुत ही व्यावहारिक है। बड़ी समस्याओं के लिए, प्रणाली कुछ असामान्य कठिनाइयाँ उत्पन्न करती है, विशेष रूप से यह कि समस्या कभी भी सकारात्मक निश्चित नहीं होती है (के होने पर भी {{mvar|Q}} is), एक अच्छा संख्यात्मक दृष्टिकोण खोजने के लिए इसे संभावित रूप से बहुत कठिन बना देता है, और समस्या पर निर्भर रहने के लिए कई दृष्टिकोण हैं।<ref>[https://scholar.google.com/scholar?hl=en&q=saddle+point+indefinite+constrained+linear Google search.]</ref>
+इस प्रणाली तक पहुँचने का सबसे आसान साधन प्रत्यक्ष समाधान है (उदाहरण के लिए, LU गुणन), जो छोटी समस्याओं के लिए बहुत ही व्यावहारिक है। बड़ी समस्याओं के लिए, प्रणाली कुछ असामान्य कठिनाइयाँ उत्पन्न करती है, विशेष रूप से यह कि समस्या कभी भी धनात्मक निश्चित नहीं होती है (के होने पर भी {{mvar|Q}} is), एक अच्छा संख्यात्मक दृष्टिकोण खोजने के लिए इसे संभावित रूप से बहुत कठिन बना देता है, और समस्या पर निर्भर रहने के लिए कई दृष्टिकोण हैं।<ref>[https://scholar.google.com/scholar?hl=en&q=saddle+point+indefinite+constrained+linear Google search.]</ref>
-यदि बाधाएँ चरों को बहुत कसकर नहीं जोड़ती हैं, तो चरों को बदलने के लिए एक अपेक्षाकृत सरल हमला है जिससे बाधाएँ बिना शर्त संतुष्ट हों। उदाहरण के लिए मान लीजिए {{math|1='''d''' = 0}} (अशून्य के लिए सामान्यीकरण सीधा है)। बाधा समीकरणों को देखते हुए:
+यदि बाधाएँ चरों को बहुत कसकर नहीं जोड़ती हैं, तो चरों को बदलने के लिए एक अपेक्षाकृत सरल आघात है जिससे बाधाएँ बिना शर्त संतुष्ट हों। उदाहरण के लिए मान लीजिए {{math|1='''d''' = 0}} (अशून्य के लिए सामान्यीकरण सीधा है)। बाधा समीकरणों को देखते हुए:
 :<math>E\mathbf{x} = 0</math>
@@ Line 81: / Line 82: @@
 :<math>Z \mathbf{y} = \mathbf x</math>
-कहाँ {{math|'''y'''}} का आयाम है {{math|'''x'''}} बाधाओं की संख्या घटाएं। तब
+यहाँ {{math|'''y'''}} का आयाम है {{math|'''x'''}} बाधाओं की संख्या घटाएं। तब
 :<math>E Z \mathbf{y} = \mathbf 0</math>
@@ Line 91: / Line 92: @@
 :<math>Z^\top Q Z \mathbf{y} = -Z^\top \mathbf{c}</math>
-कुछ शर्तों के अनुसार  {{mvar|Q}}, कम मैट्रिक्स {{math|''Z''<sup>T</sup>''QZ''}} सकारात्मक निश्चित रहेगा। संयुग्मी प्रवणता पद्धति पर भिन्नता लिखना संभव है जो की स्पष्ट गणना से बचा जाता है {{mvar|Z}}.<ref>{{Cite journal | last1 = Gould| first1 = Nicholas I. M.| last2 = Hribar| first2 = Mary E.| last3 = Nocedal| first3 = Jorge|date=April 2001| title = On the Solution of Equality Constrained Quadratic Programming Problems Arising in Optimization| journal = SIAM J. Sci. Comput.| pages = 1376–1395| volume = 23| issue = 4| citeseerx = 10.1.1.129.7555| doi = 10.1137/S1064827598345667}}</ref>
+कुछ शर्तों के अनुसार  {{mvar|Q}}, कम आव्यूह {{math|''Z''<sup>T</sup>''QZ''}} धनात्मक निश्चित रहेगा। संयुग्मी प्रवणता पद्धति पर भिन्नता लिखना संभव है जो की स्पष्ट गणना से बचा जाता है {{mvar|Z}}.<ref>{{Cite journal | last1 = Gould| first1 = Nicholas I. M.| last2 = Hribar| first2 = Mary E.| last3 = Nocedal| first3 = Jorge|date=April 2001| title = On the Solution of Equality Constrained Quadratic Programming Problems Arising in Optimization| journal = SIAM J. Sci. Comput.| pages = 1376–1395| volume = 23| issue = 4| citeseerx = 10.1.1.129.7555| doi = 10.1137/S1064827598345667}}</ref>
 == लग्रंगियन द्वैत ==
 {{See also|दोहरी समस्या}}
-किसी QP की Lagrangian Dual समस्या भी एक QP है। इसे देखने के लिए आइए हम उस मामले पर ध्यान दें जहां {{math|1=''c'' = 0}} और {{mvar|Q}} सकारात्मक निश्चित है। लैग्रेंज गुणक फलन को हम इस प्रकार लिखते हैं
+किसी क्यूपी की लाग्रंगियन दोहरी समस्या भी एक क्यूपी है। इसे देखने के लिए आइए हम उस स्थिति पर ध्यान दें जहां {{math|1=''c'' = 0}} और {{mvar|Q}} धनात्मक निश्चित है। लैग्रेंज गुणक फलन को हम इस प्रकार लिखते हैं
 :<math>L(x,\lambda) = \tfrac{1}{2} x^\top Qx + \lambda^\top (Ax-b). </math>
-(Lagrangian) दोहरे कार्य को परिभाषित करना {{math|''g''(λ)}} जैसा <math>g(\lambda) = \inf_{x} L(x,\lambda) </math>, हम का एक infinum पाते हैं {{mvar|L}}, का उपयोग कर <math>\nabla_{x} L(x,\lambda)=0</math> और सकारात्मक-निश्चितता {{mvar|Q}}:
+(लाग्रंगियन) दोहरे कार्य को परिभाषित करना {{math|''g''(λ)}} जैसा <math>g(\lambda) = \inf_{x} L(x,\lambda) </math>, हम का एक इंफिनियम पाते हैं {{mvar|L}}, का उपयोग कर <math>\nabla_{x} L(x,\lambda)=0</math> और धनात्मक-निश्चितता {{mvar|Q}}:
 :<math>x^* = -Q^{-1} A^\top \lambda.</math>
 इसलिए दोहरा कार्य है
 :<math>g(\lambda) = -\tfrac{1}{2} \lambda^\top AQ^{-1}A^\top \lambda - \lambda^\top b,</math>
-और इसलिए QP का Lagrangian दोहरा है
+और इसलिए क्यूपी का लाग्रंगियन दोहरा है
 :<math>\text{maximize}_{\lambda\geq 0} \quad  -\tfrac{1}{2} \lambda^\top AQ^{-1} A^\top \lambda - \lambda^\top b</math>
-Lagrangian द्वैत सिद्धांत के अतिरिक्त, अन्य द्वैत युग्म हैं (जैसे वोल्फ द्वैत, आदि)।
+लाग्रंगियन द्वैत सिद्धांत के अतिरिक्त, अन्य द्वैत युग्म हैं (जैसे वोल्फ द्वैत, आदि)।
 == जटिलता ==
-[[सकारात्मक-निश्चित मैट्रिक्स]] के लिए {{mvar|Q}}दीर्घवृत्ताभ विधि (कमजोर) बहुपद समय में समस्या को हल करती है।<ref>{{cite journal| last=Kozlov | first=M. K. |author2=S. P. Tarasov | author3-link=Leonid Khachiyan |author3=Leonid G. Khachiyan | year=1979 | title=[Polynomial solvability of convex quadratic programming] | journal=[[Doklady Akademii Nauk SSSR]] | volume=248 | pages=1049–1051}} Translated in: {{cite journal| journal=Soviet Mathematics - Doklady | volume=20 | pages=1108–1111}}</ref> यदि, दूसरी ओर, {{mvar|Q}} अनिश्चित है, तो समस्या [[एनपी कठिन]] है।<ref>{{cite journal | last = Sahni | first = S. | title = Computationally related problems | journal = SIAM Journal on Computing | volume = 3 | issue = 4 | pages = 262–279 | year = 1974 | doi=10.1137/0203021| url = http://www.cise.ufl.edu/~sahni/papers/comp.pdf | citeseerx = 10.1.1.145.8685 }}</ref> इन गैर-उत्तल समस्याओं के लिए कई स्थिर बिंदु और स्थानीय न्यूनतम हो सकते हैं। वास्तव में, होने पर भी {{mvar|Q}} एकमात्र एक नकारात्मक [[eigenvalue]] है, समस्या (दृढ़ता से) एनपी-हार्ड है।<ref>{{cite journal | title = Quadratic programming with one negative eigenvalue is (strongly) NP-hard | first1 = Panos M. | last1 = Pardalos | first2 = Stephen A. | last2 = Vavasis | journal = Journal of Global Optimization | volume = 1 | issue = 1 | year = 1991 | pages = 15–22 | doi=10.1007/bf00120662| s2cid = 12602885 }}</ref>
+धनात्मक-निश्चित आव्यूह के लिए {{mvar|Q}} दीर्घवृत्ताभ विधि (कमजोर) बहुपद समय में समस्या को हल करती है।<ref>{{cite journal| last=Kozlov | first=M. K. |author2=S. P. Tarasov | author3-link=Leonid Khachiyan |author3=Leonid G. Khachiyan | year=1979 | title=[Polynomial solvability of convex quadratic programming] | journal=[[Doklady Akademii Nauk SSSR]] | volume=248 | pages=1049–1051}} Translated in: {{cite journal| journal=Soviet Mathematics - Doklady | volume=20 | pages=1108–1111}}</ref> यदि, दूसरी ओर, {{mvar|Q}} अनिश्चित है, तो समस्या [[एनपी कठिन]] है।<ref>{{cite journal | last = Sahni | first = S. | title = Computationally related problems | journal = SIAM Journal on Computing | volume = 3 | issue = 4 | pages = 262–279 | year = 1974 | doi=10.1137/0203021| url = http://www.cise.ufl.edu/~sahni/papers/comp.pdf | citeseerx = 10.1.1.145.8685 }}</ref> इन गैर-उत्तल समस्याओं के लिए कई स्थिर बिंदु और स्थानीय न्यूनतम हो सकते हैं। वास्तव में, होने पर भी {{mvar|Q}} एकमात्र एक नकारात्मक [[eigenvalue|इगेनवलुए]] है, समस्या (दृढ़ता से) एनपी-हार्ड है।<ref>{{cite journal | title = Quadratic programming with one negative eigenvalue is (strongly) NP-hard | first1 = Panos M. | last1 = Pardalos | first2 = Stephen A. | last2 = Vavasis | journal = Journal of Global Optimization | volume = 1 | issue = 1 | year = 1991 | pages = 15–22 | doi=10.1007/bf00120662| s2cid = 12602885 }}</ref>
 == पूर्णांक बाधाएँ ==
-कुछ स्थितियाँ ऐसी होती हैं जहाँ सदिश के एक या अधिक अवयव होते हैं {{math|'''x'''}} [[पूर्णांक]] मान लेने की आवश्यकता होगी। इससे मिश्रित-पूर्णांक द्विघात प्रोग्रामिंग (MIQP) समस्या का निर्माण होता है।<ref>{{Cite journal|last=Lazimy|first=Rafael|date=1982-12-01|title=Mixed-integer quadratic programming|journal=Mathematical Programming| language=en| volume=22| issue=1| pages=332–349| doi=10.1007/BF01581047| s2cid=8456219|issn=1436-4646}}</ref> MIQP के अनुप्रयोगों में [[जल संसाधन]] सम्मलित हैं<ref>{{Cite journal|last1=Propato Marco|last2=Uber James G.|date=2004-07-01|title=Booster System Design Using Mixed-Integer Quadratic Programming|journal=Journal of Water Resources Planning and Management|volume=130|issue=4|pages=348–352|doi=10.1061/(ASCE)0733-9496(2004)130:4(348)}}</ref> और ट्रैकिंग त्रुटि # इंडेक्स फंड निर्माण।<ref>{{Cite book|last1=Cornuéjols|first1=Gérard|url=https://www.cambridge.org/core/books/optimization-methods-in-finance/8A4996C5DB2006224E4D983B5BC95E3B|title=Optimization Methods in Finance|last2=Peña|first2=Javier|last3=Tütüncü|first3=Reha|publisher=Cambridge University Press|year=2018|isbn=9781107297340|edition=2nd|location=Cambridge, UK|pages=167–168}}</ref>
+कुछ स्थितियाँ ऐसी होती हैं जहाँ सदिश के एक या अधिक अवयव होते हैं {{math|'''x'''}} [[पूर्णांक]] मान लेने की आवश्यकता होगी। इससे मिश्रित-पूर्णांक द्विघात प्रोग्रामिंग (एमआईक्यूपी) समस्या का निर्माण होता है।<ref>{{Cite journal|last=Lazimy|first=Rafael|date=1982-12-01|title=Mixed-integer quadratic programming|journal=Mathematical Programming| language=en| volume=22| issue=1| pages=332–349| doi=10.1007/BF01581047| s2cid=8456219|issn=1436-4646}}</ref> एमआईक्यूपी के अनुप्रयोगों में [[जल संसाधन]] सम्मलित हैं<ref>{{Cite journal|last1=Propato Marco|last2=Uber James G.|date=2004-07-01|title=Booster System Design Using Mixed-Integer Quadratic Programming|journal=Journal of Water Resources Planning and Management|volume=130|issue=4|pages=348–352|doi=10.1061/(ASCE)0733-9496(2004)130:4(348)}}</ref> और ट्रैकिंग त्रुटि इंडेक्स फंड निर्माण सम्मलित है।।<ref>{{Cite book|last1=Cornuéjols|first1=Gérard|url=https://www.cambridge.org/core/books/optimization-methods-in-finance/8A4996C5DB2006224E4D983B5BC95E3B|title=Optimization Methods in Finance|last2=Peña|first2=Javier|last3=Tütüncü|first3=Reha|publisher=Cambridge University Press|year=2018|isbn=9781107297340|edition=2nd|location=Cambridge, UK|pages=167–168}}</ref>
@@ Line 124: / Line 123: @@
 !संक्षिप्त जानकारी
 |-
-|[[AIMMS]]|| अनुकूलन और शेड्यूलिंग-प्रकार की समस्याओं को मॉडलिंग और हल करने के लिए एक सॉफ्टवेयर सिस्टम
+|[[AIMMS|एआईएमएमएस]]|| अनुकूलन और शेड्यूलिंग-प्रकार की समस्याओं को मॉडलिंग और हल करने के लिए एक सॉफ्टवेयर सिस्टम
 |-
-|[[ALGLIB]]|| डुअल लाइसेंस (जीपीएल/मालिकाना) न्यूमेरिकल लाइब्रेरी (सी++, .नेट)।
+|[[ALGLIB|एएलजीएलआईबी]]|| डुअल लाइसेंस (जीपीएल/मालिकाना) न्यूमेरिकल लाइब्रेरी (सी++, .नेट)।
 |-
 |[[AMPL|एएमपीएल]]|| बड़े पैमाने पर गणितीय अनुकूलन के लिए एक लोकप्रिय मॉडलिंग भाषा।
@@ Line 136: / Line 135: @@
 |[[CGAL|सीजीएएल]]|| एक खुला स्रोत कम्प्यूटेशनल ज्यामिति पैकेज जिसमें द्विघात प्रोग्रामिंग सॉल्वर सम्मलित है।
 |-
-|[[CPLEX|सीप्लेक्स]]|| एक एपीआई (सी, सी ++, जावा, .नेट, पायथन, मैटलैब और आर) के साथ लोकप्रिय सॉल्वर। शिक्षाविदों के लिए नि: शुल्क।
+|[[CPLEX|सीप्लेक्स]]|| एक एपीआई (सी, सी ++, जावा, .नेट, पायथन, मैटलैब और आर) के साथ लोकप्रिय सॉल्वर। शिक्षाविदों के लिए नि: शुल्क हैं ।
 |-
 |[[Microsoft Excel|एक्सेल]] सॉल्वर फ़ंक्शन|| स्प्रैडशीट्स के लिए समायोजित एक अरैखिक सॉल्वर जिसमें फ़ंक्शन मूल्यांकन पुनर्गणना कोशिकाओं पर आधारित होते हैं। मूल संस्करण एक्सेल के लिए एक मानक ऐड-ऑन के रूप में उपलब्ध है।
@@ Line 142: / Line 141: @@
 |[[General Algebraic Modeling System|जीएएमएस]] || गणितीय अनुकूलन के लिए एक उच्च स्तरीय मॉडलिंग प्रणाली
 |-
-|[[GNU Octave|जीएनयू ऑक्टेव]]|| एक नि: शुल्क (इसका लाइसेंस है [[GPL]]v3) संख्यात्मक कंप्यूटिंग के लिए सामान्य-उद्देश्य और मैट्रिक्स-उन्मुख प्रोग्रामिंग-भाषा, मैटलैब के समान। जीएनयू ऑक्टेव में क्वाड्रैटिक प्रोग्रामिंग इसके माध्यम से उपलब्ध है [https://www.gnu.org/software/octave/doc/interpreter/Quadratic-Programming.html qp] कमांड
+|[[GNU Octave|जीएनयू ऑक्टेव]]|| एक नि: शुल्क (इसका लाइसेंस है [[GPL|जीपीएलवी]]3) संख्यात्मक कंप्यूटिंग के लिए सामान्य-उद्देश्य और आव्यूह-उन्मुख प्रोग्रामिंग-भाषा, मैटलैब के समान। जीएनयू ऑक्टेव में क्वाड्रैटिक प्रोग्रामिंग इसके माध्यम से उपलब्ध है [https://www.gnu.org/software/octave/doc/interpreter/Quadratic-Programming.html क्यूपी] कमांड
 |-
-|[[HiGHS optimization solver|हइस]]|| रैखिक प्रोग्रामिंग (एलपी), मिश्रित-पूर्णांक प्रोग्रामिंग (एमआईपी), और उत्तल द्विघात प्रोग्रामिंग (क्यूपी) मॉडल को हल करने के लिए ओपन-सोर्स सॉफ़्टवेयर
+|[[HiGHS optimization solver|हइस]]|| रैखिक प्रोग्रामिंग (एलपी), मिश्रित-पूर्णांक प्रोग्रामिंग (एमआईपी), और उत्तल द्विघात प्रोग्रामिंग (क्यूपी) मॉडल को हल करने के लिए ओपन-सोर्स सॉफ़्टवेयर है।
 |-
-|[[IMSL Numerical Libraries|आईएमएसएल]]|| गणितीय और सांख्यिकीय कार्यों का एक सेट जिसे प्रोग्रामर अपने सॉफ्टवेयर अनुप्रयोगों में एम्बेड कर सकते हैं।
+|[[IMSL Numerical Libraries|आईएमएसएल]]|| गणितीय और सांख्यिकीय कार्यों का एक समुच्चय जिसे प्रोग्रामर अपने सॉफ्टवेयर अनुप्रयोगों में एम्बेड कर सकते हैं।
 |-
 |[[IPOPT|आईपीओपीटी]]|| इपॉप्ट (इंटीरियर पॉइंट ऑप्टिमाइज़र) बड़े पैमाने पर नॉनलाइनियर ऑप्टिमाइज़ेशन के लिए एक सॉफ्टवेयर पैकेज है।
 |-
-|[[Maple (software)|मेपल]]|| गणित के लिए सामान्य प्रयोजन प्रोग्रामिंग भाषा। मेपल में द्विघात समस्या का समाधान इसके माध्यम से पूरा किया जाता है [http://www.maplesoft.com/support/help/Maple/view.aspx?path=Optimization/QPSolve QPSolve] कमांड.
+|[[Maple (software)|मेपल]]|| गणित के लिए सामान्य प्रयोजन प्रोग्रामिंग भाषा। मेपल में द्विघात समस्या का समाधान इसके माध्यम से पूरा किया जाता है [http://www.maplesoft.com/support/help/Maple/view.aspx?path=Optimization/QPSolve क्यूपी] [https://pypi.org/project/qpsolvers/ हल] कमांड.
 |-
-|[[MATLAB|मैटलैब]]|| संख्यात्मक कंप्यूटिंग के लिए एक सामान्य-उद्देश्य और मैट्रिक्स-उन्मुख प्रोग्रामिंग-भाषा। मैटलैब में द्विघात प्रोग्रामिंग के लिए बेस मैटलैब उत्पाद के अतिरिक्त ऑप्टिमाइज़ेशन टूलबॉक्स की आवश्यकता होती है
+|[[MATLAB|मैटलैब]]|| संख्यात्मक कंप्यूटिंग के लिए एक सामान्य-उद्देश्य और आव्यूह-उन्मुख प्रोग्रामिंग-भाषा। मैटलैब में द्विघात प्रोग्रामिंग के लिए बेस मैटलैब उत्पाद के अतिरिक्त ऑप्टिमाइज़ेशन टूलबॉक्स की आवश्यकता होती है
 |-
 |[[Mathematica|गणितीय]]|| प्रतीकात्मक और संख्यात्मक क्षमताओं सहित गणित के लिए एक सामान्य-उद्देश्य प्रोग्रामिंग-भाषा।
@@ Line 160: / Line 159: @@
 |[[NAG Numerical Library|एनएजी न्यूमेरिकल लाइब्रेरी]]|| के माध्यम से विकसित गणितीय और सांख्यिकीय दिनचर्या का एक संग्रह[[Numerical Algorithms Group|संख्यात्मक एल्गोरिदम समूह]] या कई प्रोग्रामिंग लैंग्वेज (सी, सी++, फोरट्रान, विजुअल बेसिक, जावा और सी#) और पैकेज (मैटलैब, एक्सेल, आर, लैबव्यू)। एनएजी लाइब्रेरी के ऑप्टिमाइज़ेशन चैप्टर में विरल और गैर-विरल रेखीय बाधा मैट्रिस दोनों के साथ द्विघात प्रोग्रामिंग समस्याओं के लिए रूटीन सम्मलित हैं, साथ में लीनियर, नॉनलाइनियर के अनुकूलन के लिए रूटीन के साथ, नॉनलाइनियर, बाउंडेड या नो कंस्ट्रेंट्स के साथ लीनियर या नॉनलाइनियर फ़ंक्शंस के वर्गों का योग। . एनएजी लाइब्रेरी में स्थानीय और वैश्विक अनुकूलन दोनों के लिए और निरंतर या पूर्णांक समस्याओं के लिए रूटीन हैं।
 |-
-|[[Python (programming language)|पाइथन]]||अधिकांश उपलब्ध सॉल्वरों के लिए बाइंडिंग के साथ उच्च-स्तरीय प्रोग्रामिंग भाषा। द्विघात प्रोग्रामिंग के माध्यम से उपलब्ध है [https://pypi.org/project/qpsolvers/ solve_qp] फ़ंक्शन या किसी विशिष्ट सॉल्वर को सीधे कॉल करके.
+|[[Python (programming language)|पाइथन]]||अधिकांश उपलब्ध सॉल्वरों के लिए बाइंडिंग के साथ उच्च-स्तरीय प्रोग्रामिंग भाषा। द्विघात प्रोग्रामिंग के माध्यम से उपलब्ध है [https://pypi.org/project/qpsolvers/ हल क्यूपी] फ़ंक्शन या किसी विशिष्ट सॉल्वर को सीधे कॉल करके.
 |-
-|[[R (programming language)|आर (फोरट्रान)]] ||[[GNU General Public License|GPL]]फ़ंक्शन या एक विशिष्ट सॉल्वर को कॉल करके डायरेक्टली यूनिवर्सल क्रॉस-प्लेटफ़ॉर्म सांख्यिकीय संगणना फ्रेमवर्क। एक्टली
+|[[R (programming language)|आर (फोरट्रान)]] ||[[GNU General Public License|जीपीएल]] फ़ंक्शन या एक विशिष्ट सॉल्वर को कॉल करके डायरेक्टली यूनिवर्सल क्रॉस-प्लेटफ़ॉर्म सांख्यिकीय संगणना फ्रेमवर्क। एक्टली
 |-
 |[[SAS System|एसएएस / ओआर]]|| लीनियर, इंटीजर, नॉनलाइनियर, डेरिवेटिव-फ्री, नेटवर्क, कॉम्बिनेटोरियल और कंस्ट्रेंट ऑप्टिमाइजेशन के लिए सॉल्वर का एक सूट; [[Index.php?title=बीजगणितीय मॉडलिंग भाषा|बीजगणितीय मॉडलिंग भाषा]] ऑप्टमॉडल; और विशिष्ट समस्याओं/बाजारों के उद्देश्य से विभिन्न प्रकार के लंबवत समाधान, जिनमें से सभी पूरी प्रकार से एकीकृत हैं [[SAS System|एसएएस सिस्टम]].
 |-
-|[[SuanShu_numerical_library|सुआन्शु]]|| हल करने के लिए ऑप्टिमाइज़ेशन एल्गोरिदम का एक ओपन-सोर्स सूट[[Linear programming|एल.पी.]], क्यूपी, [[SOCP|एसओसीपी]], [[Semidefinite_programming|एसडीपी]], [[Sequential_quadratic_programming|एसक्यूपी]] जावा में
+|[[SuanShu_numerical_library|सुआन्शु]]|| हल करने के लिए ऑप्टिमाइज़ेशन एल्गोरिदम का एक ओपन-सोर्स सूट [[Linear programming|एल.पी.]], क्यूपी, [[SOCP|एसओसीपी]], [[Semidefinite_programming|एसडीपी]], [[Sequential_quadratic_programming|एसक्यूपी]] जावा में
 |-
 |[[TK Solver|टीके सॉल्वर]]|| यूनिवर्सल टेक्निकल सिस्टम्स, इंक  के माध्यम से व्यावसायिक रूप से घोषित, नियम-आधारित भाषा पर आधारित गणितीय मॉडलिंग और समस्या निवारण सॉफ्टवेयर सिस्टम।
@@ Line 172: / Line 171: @@
 |[[TOMLAB|टॉमलैब]]||वैश्विक अनुकूलन, पूर्णांक प्रोग्रामिंग, सभी प्रकार के न्यूनतम वर्ग, रैखिक, द्विघात और अप्रतिबंधित प्रोग्रामिंग का समर्थन करता है [[MATLAB|मैटलैब]]. टॉमलैब जैसे सॉल्वर का समर्थन करता है [[CPLEX|सीप्लेक्स]], [[SNOPT|स्नाप्त]] और [[KNITRO|नाइट्रो]].
 |-
-|[[FICO Xpress|एक्सप्रेस]]||बड़े पैमाने पर रैखिक कार्यक्रमों, द्विघात कार्यक्रमों, सामान्य गैर-रैखिक और मिश्रित-पूर्णांक कार्यक्रमों के लिए सॉल्वर। कई प्रोग्रामिंग भाषाओं के लिए एपीआई है, एक मॉडलिंग भाषा मोसेल भी है और एएमपीएल के साथ काम करती है, [[General Algebraic Modeling System|जीएएमएस]]. अकादमिक उपयोग के लिए नि: शुल्क।
+|[[FICO Xpress|एक्सप्रेस]]||बड़े पैमाने पर रैखिक कार्यक्रमों, द्विघात कार्यक्रमों, सामान्य गैर-रैखिक और मिश्रित-पूर्णांक कार्यक्रमों के लिए सॉल्वर। कई प्रोग्रामिंग भाषाओं के लिए एपीआई है, एक मॉडलिंग भाषा मोसेल भी है और एएमपीएल के साथ काम करती है, [[General Algebraic Modeling System|जीएएमएस]]. अकादमिक उपयोग के लिए नि: शुल्क  है।
 |}
 == यह भी देखें ==
-* [[अनुक्रमिक द्विघात प्रोग्रामिंग]]
-*[[रैखिक प्रोग्रामिंग]]
+* अनुक्रमिक द्विघात प्रोग्रामिंग
-* [[क्रिटिकल लाइन विधि]]
+*रैखिक प्रोग्रामिंग
+* क्रिटिकल लाइन विधि
 ==संदर्भ==
 {{Reflist}}
 ==अग्रिम पठन==
@@ Line 196: / Line 196: @@
   |date=2000
 }}
 ==बाहरी संबंध==
 *[http://www.numerical.rl.ac.uk/qp/qp.html A page about QP]
@@ Line 203: / Line 201: @@
 *[https://www.math.uh.edu/~rohop/fall_06/Chapter3.pdf Quadratic Programming]
-{{Mathematical programming}}
+[[Category:Articles with hatnote templates targeting a nonexistent page]]
-{{Optimization algorithms}}
+[[Category:CS1 English-language sources (en)]]
-[[Category: अनुकूलन एल्गोरिदम और तरीके]]
+[[Category:CS1 errors]]
+[[Category:Collapse templates]]
-[[Category: Machine Translated Page]]
 [[Category:Created On 13/02/2023]]
+[[Category:Lua-based templates]]
+[[Category:Machine Translated Page]]
+[[Category:Navigational boxes| ]]
+[[Category:Navigational boxes without horizontal lists]]
+[[Category:Pages using duplicate arguments in template calls]]
+[[Category:Pages with script errors]]
+[[Category:Short description with empty Wikidata description]]
+[[Category:Sidebars with styles needing conversion]]
+[[Category:Template documentation pages|Documentation/doc]]
+[[Category:Templates Translated in Hindi]]
+[[Category:Templates Vigyan Ready]]
+[[Category:Templates generating microformats]]
+[[Category:Templates that add a tracking category]]
+[[Category:Templates that are not mobile friendly]]
+[[Category:Templates that generate short descriptions]]
+[[Category:Templates using TemplateData]]
+[[Category:Wikipedia metatemplates]]
+[[Category:अनुकूलन एल्गोरिदम और तरीके]]

Anonymous

Search

द्विघात प्रोग्रामिंग: Difference between revisions

Namespaces

More

Page actions

Latest revision as of 15:39, 20 October 2023

Contents