선형보완성문제

수학적 최적화 이론에서 선형 보완성 문제(LCP)는 계산 역학에서 자주 발생하며, 특별한 경우로서 잘 알려진 2차 프로그래밍을 포괄한다.1968년 코틀과 단치히에 의해 제안되었다.^[1][2][3]

공식화

실제 매트릭스 M과 벡터 q가 주어진 경우, 선형 보완성 문제 LCP(q, M)는 다음과 같은 제약을 충족하는 벡터 z와 w를 추구한다.

• ${\displaystyle w}$, ${\displaystyle z}$ ${\displaystyle ⩾}$ ${\displaystyle 0}$, ${\displaystyle w,z\geqslant 0,}($즉, 이 두 벡터의 각 구성 요소는 음이 아님)
• ${\displaystyle$$T}w=0}$ or equivalently ${\displaystyle \sum \nolimits _{i}w_{i}z_{i}=0.}$ This is the complementarity condition, since it implies that, for all ${\displaystyle i}$, at most one of ${\displaystyle w_{i}}$ and ${\displaystyle z_{i}}$ can be positive.
• ${\displaystyle w=Mz+q}$

이 문제에 대한 해결책의 존재와 고유성을 위한 충분한 조건은 M이 대칭적인 양의-적정성이라는 것이다.LCP(q, M)가 매 q에 대한 솔루션을 가지고 있는 M이라면, M은 Q 매트릭스다.만일 M이 모든 q에 대해 LCP(q, M)가 고유한 솔루션을 갖는다면, M은 P-매트릭스다.이 두 가지 특성 모두 충분하고 필요하다.^[4]

벡터 w는 느슨한 변수여서,^[5] 일반적으로 z가 발견된 후 폐기된다.이와 같이 문제를 다음과 같이 공식화할 수도 있다.

• $Mz+q\geqslant 0}$
• ${\displaystyle z\geqslant 0}$
• ${\displaystyle z^{}}$ ${\displaystyle {T(}^{}M}$ ${\displaystyle z}$+ ${\displaystyle q}$)${\displaystyle }$= ${\displaystyle 0}$ ${\displaystyle z^{\mathrm {T}}}(Mz+q)=0}($보완성 조건)

볼록 2차 축소:최소조건

선형 보완성 문제에 대한 해결책을 찾는 것은 2차 함수를 최소화하는 것과 관련이 있다.

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

제약을 받고.

${\displaystyle {Mz}+q\geqslant 0}$

${\displaystyle z\geqslant 0}$

이러한 제약조건은 f가 항상 음성이 아니라는 것을 보장한다.z가 선형 보완성 문제를 해결할 경우에만 f의 최소값은 z에서 0이다.

M이 양수확정일 경우, 볼록 QP를 풀기 위한 알고리즘은 LCP를 해결할 수 있다.렘케의 알고리즘과 단치히의 심플렉스 알고리즘의 변종과 같이 특별히 설계된 베이시스 교환 피벗 알고리즘이 수십 년 동안 사용되어 왔다.다항식 시간 복잡성을 갖는 것 외에도 내부 포인트 방식도 실무에서 효과적이다.

또한 $최소{\displaystyle }$ f${\displaystyle }$( ${\displaystyle x}$)${\displaystyle }$= ${\displaystyle {}^{}}$ ${\displaystyle {}^{}}$+ ${\displaystyle 1\frac{\mathrm{}}{}}$ ${\displaystyle \frac{2}{}}$ ${\displaystyle x^{}}$ ${\displaystyle {}^{}}$ x ${\displaystyle f(x)=c^{$$T}x+{\tfrac {1}{2}}x^{$$T}Qx}$은(는) A ${\displaystyle x}$ ${\displaystyle ⩾}$ b ${\displaystyle Ax\geqslant b}$ 및 Q$$ 대칭인 x $with$${\displaystyle 0}$ ${\displaystyle$ x$\geqslant$ 0$}$의 적용을 받는다.

로 LCP를 해결하는 것과 동일하다.

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

QP 문제의 카루시-쿤-터커 조건은 다음과 같이 쓸 수 있기 때문이다.

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

v 라그랑주 승수는 비부정성 제약조건에 대한 승수, λ 불평등 제약조건에 대한 승수, 그리고 불평등 제약조건에 대한 느슨한 변수들.네 번째 조건은 KKT 벡터 집합(최적 라그랑주 승수)이 (v, λ)인 각 변수 그룹(x, s)의 상호보완성에서 도출된다.그 경우에는

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

x의 비부정성 제약조건이 완화되면 Q가 비성격(양정확한 경우 보장되는)인 한 LCP 문제의 치수성은 불평등 수로 감소될 수 있다.승수 v는 더 이상 존재하지 않으며, 첫 번째 KKT 조건은 다음과 같이 다시 작성할 수 있다.

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

또는:

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

A로 양면을 미리 곱하고 b를 빼면 다음과 같다.

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

두 번째 KKT 조건으로 인해 왼쪽은 s이다.대체 및 재주문:

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

지금 전화 중

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

느슨한 변수 s와 라그랑주 승수 λ 사이의 상호보완성 관계 때문에 우리는 LCP를 가지고 있다.일단 해결하면 첫 번째 KKT 조건을 통해 λ로부터 x의 값을 얻을 수 있을 것이다.

마지막으로, 다음과 같은 추가적인 평등 제약도 처리할 수 있다.

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

이것은 b ${\displaystyle e_{}}$ ${\displaystyle q_{}}$ ${\$와 같은 치수를 갖는 라그랑주 승수 μ의 벡터를 도입한다$.$

LCP 시스템 $s{\displaystyle }$= ${\displaystyle M}$ ${\displaystyle \lambda }$+ Q ${\displaystyle s=M{\lambda }}+Q}$에 대한 M과 Q가 이제$$ 다음과 같이 표현되었음을 쉽게 확인할 수 있다.

${\displaystyle {\reasoned}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{b\ed}}}}}}}$

λ로부터 우리는 이제 x와 라그랑주 승수의 등가 μ 값을 모두 회복할 수 있다.

${\displaystyle {\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}}}$

실제로 대부분의 QP솔러들은 내부 포인트 방식, 원/보완성 피벗 방식, 활성 세트 방식 등 LCP 제형에 대해 작업한다.^[1][2]LCP 문제는 또한 Criss-cross 알고리즘으로 해결할 수 있다.^[6][7][8][9] 반대로, 선형 보완성 문제의 경우, Criss-cross 알고리즘은 매트릭스가 충분한 매트릭스일 경우에만 정밀하게 종료된다.^[8][9]충분한 행렬은 양성-확정성 행렬과 P-매트릭스의 일반화로서, 주요 미성년자는 각각 양성이다.^[8][9][10]그러한 LCP는 지향성-매트로이드 이론을 사용하여 추상적으로 공식화되었을 때 해결될 수 있다.^[11][12][13]

참고 항목

• 상보성 이론
• 게임용 물리 엔진 임펄스/기형 물리 엔진은 이 접근법을 사용한다.
• Contact dynamic(접촉 역학) 매끄럽지 않은 접근 방식으로 다이내믹스에 접촉하십시오.
• 바이마트릭스 게임은 LCP로 줄일 수 있다.

메모들

참조

• 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 — 선형 보완성 문제를 해결하기 위한 GAUSS의 간단한 절차
• Lemke 알고리즘의 C에 있는 Siconos/Numerics 오픈 소스 GPL 구현 및 기타 LCP 및 MLCP 해결 방법