रैखिक संपूरकता समस्या

गणितीय अनुकूलन (गणित) में, रैखिक संपूरकता समस्या (एलसीपी) कम्प्यूटेशनल यांत्रिकी में अधिकांशतः उत्पन्न होती है और विशेष स्थितियों के रूप में प्रसिद्ध द्विघात प्रोग्रामिंग को सम्मिलित करती है। इसे सन्न 1968 में कॉटल और जॉर्ज डेंजिग द्वारा प्रस्तावित किया गया था।

सूत्रीकरण

वास्तविक आव्युह M और सदिश q को देखते हुए, रैखिक संपूरकता समस्या एलसीपी(q, M) सदिश z और w की खोज करती है, जो निम्नलिखित बाधाओं को पूर्ण करती हैं।

• $w,z\geqslant 0,$ (अर्थात्, इन दोनों सदिशो का प्रत्येक घटक गैर-ऋणात्मक होता है)
• $z^{T}w=0$ या समकक्ष $\sum \nolimits _{i}w_{i}z_{i}=0.$ यह संपूरकता सिद्धांत की वह स्थिति है, जिससे कि इसका तात्पर्य यह है कि, सभी के लिए $i$, अधिक से अधिक $w_{i}$ और $z_{i}$ धनात्मक हो सकता है।
• $w=Mz+q$

इस समस्या के समाधान के अस्तित्व और विशिष्टता के लिए पर्याप्त शर्त यह होती है कि एम सममित आव्युह धनात्मक-निश्चित होता है। यदि M ऐसा होता है कि एलसीपी(q, M) के पास प्रत्येक q के लिए समाधान होता है, तब M q-आव्युह होता है। यदि M ऐसा है एलसीपी(q, M) प्रत्येक q के लिए अद्वितीय समाधान होता है, तब M पी-आव्युह होता है। यह दोनों लक्षण पर्याप्त एवं आवश्यक होते हैं।

सदिश w असावधान चर है, और इसलिए z पाए जाने के पश्चात् सामान्यतः इसे छोड़ दिया जाता है। इस प्रकार, समस्या को इस प्रकार भी तैयार किया जा सकता है।

• $Mz+q\geqslant 0$
• $z\geqslant 0$
• $z^{\mathrm {T} }(Mz+q)=0$ (पूरक स्थिति)

उत्तल द्विघात-न्यूनीकरण: न्यूनतम शर्तें

रैखिक संपूरकता समस्या का समाधान खोजना द्विघात फलन को न्यूनतम करने से जुड़ा होता है

$f(z)=z^{T}(Mz+q)$

बाधाओं के अधीन

${Mz}+q\geqslant 0$

$z\geqslant 0$

यह बाधाएं सुनिश्चित करती हैं कि f सदैव गैर-ऋणात्मक होता है। इस प्रकार z पर f का न्यूनतम मान 0 होता है और यदि z रैखिक संपूरकता समस्या को हल करता है।

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

इसके अतिरिक्त, द्विघात-प्रोग्रामिंग समस्या को न्यूनतम बताया गया है $f(x)=c^{T}x+{\tfrac {1}{2}}x^{T}Qx$ का विषय होता है $Ax\geqslant b$ साथ ही $x\geqslant 0$ Q सममिति के साथ

एलसीपी को हल करने के समान ही होता है

$q={\begin{bmatrix}c\\-b\end{bmatrix}},\qquad M={\begin{bmatrix}Q&-A^{T}\\A&0\end{bmatrix}}$

ऐसा इसलिए होता है जिससे कि QP समस्या की करुश-कुह्न-टकर स्थितियों को इस प्रकार लिखा जा सकता है।

${\begin{cases}v=Qx-A^{T}{\lambda }+c\\s=Ax-b\\x,{\lambda },v,s\geqslant 0\\x^{T}v+{\lambda }^{T}s=0\end{cases}}$

गैर-ऋणात्मकता बाधाओं पर लैग्रेंज मल्टीप्लायरों के साथ, λ असमानता बाधाओं पर गुणक, और असमानता बाधाओं के लिए असमानता चर चौथी स्थिति चरों के प्रत्येक समूह की संपूरकता असमानता से उत्पन्न होती है। इसके केकेटी सदिश (इष्टतम लैग्रेंज मल्टीप्लायर) के समुच्चय के साथ (v, λ). उस स्थितियों में,

$z={\begin{bmatrix}x\\\lambda \end{bmatrix}},\qquad w={\begin{bmatrix}v\\s\end{bmatrix}}$

यदि x पर गैर-ऋणात्मकता बाधा में ढील दी जाती है, तब एलसीपी समस्या की आयामीता को असमानताओं की संख्या तक कम किया जा सकता है, जब तक कि Q गैर-एकवचन है (जो कि धनात्मक-निश्चित आव्युह होने पर गारंटी है)।इस प्रकार गुणक v अभी उपस्तिथ नहीं हैं, और पहली केकेटी शर्तों को इस प्रकार फिर से लिखा जा सकता है।

$Qx=A^{T}{\lambda }-c$

या

$x=Q^{-1}(A^{T}{\lambda }-c)$

दोनों पक्षों को पहले A से गुणा करने और b घटाने पर हमें प्राप्त होता है।

$Ax-b=AQ^{-1}(A^{T}{\lambda }-c)-b\,$

दूसरी केकेटी स्थिति के कारण बाईं ओर, एस होता है। इस प्रकार प्रतिस्थापित करना और पुनः व्यवस्थित करना

$s=(AQ^{-1}A^{T}){\lambda }+(-AQ^{-1}c-b)\,$

अभी कॉल कर रहा हूँ

${\begin{aligned}M&:=(AQ^{-1}A^{T})\\q&:=(-AQ^{-1}c-b)\end{aligned}}$

असमानता चर और उनके लैग्रेंज गुणक λ के मध्य संपूरकता के संबंध के कारण, हमारे पास एलसीपी होता है। इस प्रकार प्रत्येक बार जब हम इसे हल कर लेते हैं, तब हम पहली केकेटी स्थिति के माध्यम से λ से x का मान प्राप्त कर सकते हैं।

अंत में, अतिरिक्त समानता बाधाओं को संभालना भी संभव होता है।

$A_{eq}x=b_{eq}$

यह लैग्रेंज मल्टीप्लायरों μ के सदिश का परिचय देता है, जिसका आयाम $b_{eq}$ के समान होता है।

यह सत्यापित करना सरल होता है कि एलसीपी प्रणाली के लिए एम और क्यू $s=M{\lambda }+Q$ अभी इन्हें इस प्रकार व्यक्त किया गया है।

${\begin{aligned}M&:={\begin{bmatrix}A&0\end{bmatrix}}{\begin{bmatrix}Q&A_{eq}^{T}\\-A_{eq}&0\end{bmatrix}}^{-1}{\begin{bmatrix}A^{T}\\0\end{bmatrix}}\\q&:=-{\begin{bmatrix}A&0\end{bmatrix}}{\begin{bmatrix}Q&A_{eq}^{T}\\-A_{eq}&0\end{bmatrix}}^{-1}{\begin{bmatrix}c\\b_{eq}\end{bmatrix}}-b\end{aligned}}$

λ से अभी हम x और समानता के लैग्रेंज गुणक दोनों के मान μ पुनर्प्राप्त कर सकते हैं।

${\begin{bmatrix}x\\\mu \end{bmatrix}}={\begin{bmatrix}Q&A_{eq}^{T}\\-A_{eq}&0\end{bmatrix}}^{-1}{\begin{bmatrix}A^{T}\lambda -c\\-b_{eq}\end{bmatrix}}$

वास्तव में, अधिकांश क्यूपी सॉल्वर एलसीपी सूत्रीकरण पर कार्य करते हैं, जिसमें आंतरिक बिंदु विधि, प्रिंसिपल/पूरक पिवोटिंग और सक्रिय समुच्चय विधियां सम्मिलित होती हैं। एलसीपी समस्याओं को क्रिस-क्रॉस एल्गोरिथ्म द्वारा भी हल किया जा सकता है, इसके विपरीत, रैखिक संपूरकता समस्याओं के लिए, क्रिस-क्रॉस एल्गोरिथ्म केवल तभी समाप्त होता है जब आव्युह पर्याप्त आव्युह होता है। इस प्रकार पर्याप्त आव्युह धनात्मक-निश्चित आव्युह और पी-आव्युह दोनों का सामान्यीकरण होता है, जिसके प्रमुख नाबालिग प्रत्येक धनात्मक होते हैं।

ऐसे एलसीपी को तब हल किया जा सकता है जब उन्हें ओरिएंटेड-मैट्रोइड सिद्धांत का उपयोग करके अमूर्त रूप से तैयार किया जाता है।

यह भी देखें

• पूरकता सिद्धांत
• गेम के लिए भौतिकी इंजन आवेग/बाधा प्रकार के भौतिकी इंजन इस दृष्टिकोण का उपयोग करते हैं।
• संपर्क गतिशीलता नॉनस्मूथ दृष्टिकोण के साथ संपर्क गतिशीलता।
• बिआव्युह गेम को एलसीपी तक कम किया जा सकता है।

संदर्भ

• ब्योर्नर, ऐन्डर्स; लास वेर्गनास, मिशेल; स्टर्मफेल्स, बर्न्ड; सफ़ेद, नील; ज़ेग्लर, Günter (1999). "10 रैखिक प्रोग्रामिंग". ओरिएंटेड मैट्रोइड्स. कैम्ब्रिज यूनिवर्सिटी प्रेस. pp. 417–479. doi:10.1017/CBO9780511586507. ISBN 978-0-521-77750-6. MR 1744046.
• कोटले, आर. डब्ल्यू.; डेंटज़िग, जी. बी. (1968). "गणितीय प्रोग्रामिंग का पूरक धुरी सिद्धांत". रेखीय बीजगणित और इसके अनुप्रयोग. 1: 103–125. doi:10.1016/0024-3795(68)90052-9. {{cite journal}}: Invalid |doi-access=मुक्त (help)
• कोटले, रिचर्ड डब्ल्यू.; Pang, Jong-Shi; पत्थर, रिचर्ड ई. (1992). रैखिक संपूरकता समस्या. कंप्यूटर विज्ञान और वैज्ञानिक कंप्यूटिंग. बोस्टन, एमए: अकादमिक प्रेस, इंक. pp. xxiv+762 pp. ISBN 978-0-12-192350-1. MR 1150683.
• कोटले, आर. डब्ल्यू.; Pang, जे.-एस.; वेंकटेश्वरन, वी (मार्च-अप्रैल 1989). "पर्याप्त आव्यूह और रैखिक संपूरकता समस्या". रेखीय बीजगणित और इसके अनुप्रयोग. 114–115: 231–249. doi:10.1016/0024-3795(89)90463-1. MR 0986877. {{cite journal}}: Check date values in: |date= (help)
• Csizmadia, Zsolt; Illés, Tibor (2006). "पर्याप्त मैट्रिक्स के साथ रैखिक संपूरकता समस्याओं के लिए नए क्रिस-क्रॉस प्रकार के एल्गोरिदम" (PDF). अनुकूलन के तरीके और सॉफ्टवेयर. 21 (2): 247–266. doi:10.1080/10556780500095009. S2CID 24418835.
• Fukuda, Komei; Namiki, Makoto (मार्च 1994). "मूर्ति की न्यूनतम सूचकांक पद्धति के चरम व्यवहार पर". गणितीय प्रोग्रामिंग. 64 (1): 365–370. doi:10.1007/BF01582581. MR 1286455. S2CID 21476636. {{cite journal}}: Check date values in: |date= (help)
• Fukuda, Komei; Terlaky, Tamás (1997). थॉमस एम. लिबलिंग; डोमिनिक डे वेरा (eds.). "क्रिस-क्रॉस विधियाँ: पिवट एल्गोरिदम पर एक ताज़ा दृष्टिकोण". गणितीय प्रोग्रामिंग, श्रृंखला बी. 1997 में लॉज़ेन में आयोजित गणितीय प्रोग्रामिंग पर 16वीं अंतर्राष्ट्रीय संगोष्ठी के पेपर. 79 (1–3): 369–395. CiteSeerX 10.1.1.36.9373. doi:10.1007/BF02614325. MR 1464775. S2CID 2794181. Postscript preprint.
• डेन हर्टोग, D.; Roos, C.; टर्लाकी, T. (1 July 1993). "रैखिक संपूरकता समस्या, पर्याप्त मैट्रिक्स और क्रिस-क्रॉस विधि" (PDF). रेखीय बीजगणित और इसके अनुप्रयोग. 187: 1–14. doi:10.1016/0024-3795(93)90124-7.
• Murty, कट्टा जी. (जनवरी 1972). "संपूरकता समस्या के समाधानों की संख्या और पूरक शंकुओं के फैलाव गुणों पर" (PDF). रेखीय बीजगणित और इसके अनुप्रयोग. 5 (1): 65–108. doi:10.1016/0024-3795(72)90019-5. hdl:2027.42/34188. {{cite journal}}: Check date values in: |date= (help)
• मूर्ति, K. G. (1988). रैखिक संपूरकता, रैखिक और अरेखीय प्रोग्रामिंग. अनुप्रयुक्त गणित में सिग्मा श्रृंखला. Vol. 3. बर्लिन: हेल्डरमैन वेरलाग. ISBN 978-3-88538-403-8. MR 0949214. Updated and free PDF version at Katta G. Murty's website. Archived from the original on 2010-04-01.
• टेलर, जोशुआ एडम (2015). विद्युत प्रणालियों का उत्तल अनुकूलन. कैम्ब्रिज यूनिवर्सिटी प्रेस. ISBN 9781107076877.
• टर्लाकी, Tamás; Zhang, Shu Zhong (1993). "रैखिक प्रोग्रामिंग के लिए धुरी नियम: हाल के सैद्धांतिक विकास पर एक सर्वेक्षण". संचालन अनुसंधान के इतिहास. अनुकूलन समस्याओं में गिरावट. 46–47 (1): 203–233. CiteSeerX 10.1.1.36.7658. doi:10.1007/BF02096264. ISSN 0254-5330. MR 1260019. S2CID 6058077.
• टॉड, Michael J. (1985). "ओरिएंटेड मैट्रोइड्स में रैखिक और द्विघात प्रोग्रामिंग". कॉम्बिनेटोरियल थ्योरी का जर्नल. सीरीज बी. 39 (2): 105–133. doi:10.1016/0095-8956(85)90042-5. MR 0811116.

अग्रिम पठन

• आर.चंद्रशेखरन. "बिमैट्रिक्स गेम्स" (PDF). pp. 5–7. Retrieved 18 दिसंबर 2015. {{cite web}}: Check date values in: |accessdate= (help)

बाहरी संबंध

• एलसीपीसोल्व — रैखिक संपूरकता समस्या को हल करने के लिए GAUSS में सरल प्रक्रिया
• सिकोनोस/लेम्के के एल्गोरिदम के सी में न्यूमेरिक्स ओपन-सोर्स जीपीएल कार्यान्वयन और एलसीपी और एमएलसीपी को हल करने के अन्य तरीके।