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

गणितीय अनुकूलन (गणित) में, रैखिक संपूरकता समस्या (एलसीपी) कम्प्यूटेशनल यांत्रिकी में अक्सर उत्पन्न होती है और एक विशेष मामले के रूप में प्रसिद्ध द्विघात प्रोग्रामिंग को शामिल करती है। इसे 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}}$

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

यह भी देखें

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

संदर्भ

• Björner, Anders; Las Vergnas, Michel; Sturmfels, Bernd; White, Neil; Ziegler, Günter (1999). "10 Linear programming". Oriented Matroids. Cambridge University Press. pp. 417–479. doi:10.1017/CBO9780511586507. ISBN 978-0-521-77750-6. MR 1744046.
• Cottle, R. W.; Dantzig, G. B. (1968). "Complementary pivot theory of mathematical programming". Linear Algebra and Its Applications. 1: 103–125. doi:10.1016/0024-3795(68)90052-9.
• 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.
• Cottle, R. W.; Pang, J.-S.; Venkateswaran, V. (March–April 1989). "Sufficient matrices and the linear complementarity problem". Linear Algebra and Its Applications. 114–115: 231–249. doi:10.1016/0024-3795(89)90463-1. MR 0986877.
• Csizmadia, Zsolt; Illés, Tibor (2006). "New criss-cross type algorithms for linear complementarity problems with sufficient matrices" (PDF). Optimization Methods and Software. 21 (2): 247–266. doi:10.1080/10556780500095009. S2CID 24418835.
• Fukuda, Komei; Namiki, Makoto (March 1994). "On extremal behaviors of Murty's least index method". Mathematical Programming. 64 (1): 365–370. doi:10.1007/BF01582581. MR 1286455. S2CID 21476636.
• Fukuda, Komei; Terlaky, Tamás (1997). Thomas M. Liebling; Dominique de Werra (eds.). "Criss-cross methods: A fresh view on pivot algorithms". Mathematical Programming, Series B. Papers from the 16th International Symposium on Mathematical Programming held in Lausanne, 1997. 79 (1–3): 369–395. CiteSeerX 10.1.1.36.9373. doi:10.1007/BF02614325. MR 1464775. S2CID 2794181. Postscript preprint.
• den Hertog, D.; Roos, C.; Terlaky, T. (1 July 1993). "The linear complementarity problem, sufficient matrices, and the criss-cross method" (PDF). Linear Algebra and Its Applications. 187: 1–14. doi:10.1016/0024-3795(93)90124-7.
• Murty, Katta G. (January 1972). "On the number of solutions to the complementarity problem and spanning properties of complementary cones" (PDF). Linear Algebra and Its Applications. 5 (1): 65–108. doi:10.1016/0024-3795(72)90019-5. hdl:2027.42/34188.
• Murty, K. G. (1988). Linear complementarity, linear and nonlinear programming. Sigma Series in Applied Mathematics. Vol. 3. Berlin: Heldermann Verlag. 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.
• Taylor, Joshua Adam (2015). Convex Optimization of Power Systems. Cambridge University Press. ISBN 9781107076877.
• Terlaky, Tamás; Zhang, Shu Zhong (1993). "Pivot rules for linear programming: A Survey on recent theoretical developments". Annals of Operations Research. Degeneracy in optimization problems. 46–47 (1): 203–233. CiteSeerX 10.1.1.36.7658. doi:10.1007/BF02096264. ISSN 0254-5330. MR 1260019. S2CID 6058077.
• Todd, Michael J. (1985). "Linear and quadratic programming in oriented matroids". Journal of Combinatorial Theory. Series B. 39 (2): 105–133. doi:10.1016/0095-8956(85)90042-5. MR 0811116.

अग्रिम पठन

• R. Chandrasekaran. "Bimatrix games" (PDF). pp. 5–7. Retrieved 18 December 2015.

बाहरी संबंध

• LCPSolve — A simple procedure in GAUSS to solve a linear complementarity problem
• Siconos/Numerics open-source GPL implementation in C of Lemke's algorithm and other methods to solve LCPs and MLCPs