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

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

सूत्रीकरण

एक वास्तविक आव्युह M और सदिश q को देखते हुए, रैखिक संपूरकता समस्या LCP(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 ऐसा है LCP(q, M) के पास प्रत्येक q के लिए समाधान है, तो M q-आव्युह है। यदि M ऐसा है LCP(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}}$

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

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

यदि x पर गैर-ऋणात्मकता बाधा में ढील दी जाती है, तो LCP समस्या की आयामीता को असमानताओं की संख्या तक कम किया जा सकता है, जब तक कि 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 में एक सरल प्रक्रिया
• सिकोनोस/लेम्के के एल्गोरिदम के सी में न्यूमेरिक्स ओपन-सोर्स जीपीएल कार्यान्वयन और एलसीपी और एमएलसीपी को हल करने के अन्य तरीके।