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

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