線形相補性問題

数理最適化理論において、線形相補性問題（LCP）は計算力学で頻繁に発生し、よく知られている二次計画法を特殊なケースとして包含する。これは1968年にコットルとダンツィヒによって提案された。^{[ 1 ] [ 2 ] [ 3 ]} 

実数行列Mとベクトルqが与えられたとき、線形相補性問題 L​​CP( q , M ) は、次の制約を満たすベクトルzとwを求めます。

• ${\displaystyle w,z\geqslant 0,}$（つまり、これら2つのベクトルの各成分は非負である。）
• ${\displaystyle z^{T}w=0}$または同等に${\displaystyle \sum \nolimits _{i}w_{i}z_{i}=0.}$これは相補性条件であり、すべての${\displaystyle i}$最大で1つ${\displaystyle w_{i}}$そして${\displaystyle z_{i}}$プラスに働くこともある。
• ${\displaystyle w=Mz+q}$

この問題の解の存在と一意性の十分条件は、M が対称正定値行列であることです。M が、すべてのqに対してLCP( q , M )が解を持つような行列であれば、MはQ 行列です。Mが、すべてのqに対してLCP( q , M )が一意の解を持つような行列であれば、MはP 行列です。これらの特徴付けはどちらも十分条件かつ必要条件です。^{[ 4 ]}

ベクトルwはスラック変数であり、^{[ 5 ]}通常はzが見つかった後に破棄されます。したがって、この問題は次のように定式化することもできます。

• ${\displaystyle Mz+q\geqslant 0}$
• ${\displaystyle z\geqslant 0}$
• ${\displaystyle z^{\mathrm {T} }(Mz+q)=0}$（相補性条件）

線形相補性問題の解を見つけることは、二次関数を最小化することと関連している。

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

制約条件に従う

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

${\displaystyle z\geqslant 0}$

これらの制約により、f は常に非負であることが保証されます。f の最小値が zで0となるのは、 z が線形相補性問題を解決する場合に限ります。

Mが正定値行列であれば、（厳密に）凸な二次計画問題を解くためのアルゴリズムであればどれでもLCPを解くことができます。レムケのアルゴリズムやダンツィヒの単体法の変種など、特別に設計された基底交換ピボットアルゴリズムは数十年にわたって使用されてきました。内点法は、多項式時間計算量を持つだけでなく、実用上も効果的です。

また、最小化として表される二次計画問題${\displaystyle f(x)=c^{T}x+{\tfrac {1}{2}}x^{T}Qx}$対象${\displaystyle Ax\geqslant b}$同様に${\displaystyle x\geqslant 0}$Q対称性を持つ

LCP を解くのと同じ

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

これは、QP問題のカルーシュ・クーン・タッカー条件が次のように記述できるためである。

${\displaystyle {\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 は非負制約に対するラグランジュ乗数、λ は不等式制約に対する乗数、​​sは不等式制約のスラック変数である。第 4 の条件は、各変数群( x、s )と、その KKT ベクトル (最適ラグランジュ乗数) の集合( v、λ )との相補性から導かれる。この場合、

${\displaystyle z={\begin{bmatrix}x\\\lambda \end{bmatrix}},\qquad w={\begin{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\,}$

2番目のKKT条件により、左辺はsとなる。代入と並べ替えを行うと次のようになる。

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

今すぐお電話ください

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

スラック変数sとそれらのラグランジュ乗数λの間の相補性関係により、LCPが存在します。これを解くと、 最初のKKT条件を通してλからxの値を得ることができます。

最後に、追加の等式制約を処理することも可能である。

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

これにより、ラグランジュ乗数μのベクトルが導入され、その次元は${\displaystyle b_{eq}}$。

LCPシステムのMとQは簡単に検証できます${\displaystyle s=M{\lambda }+Q}$現在は次のように表現されています。

${\displaystyle {\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と等式のラグランジュ乗数μの両方の値を復元できます。

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

実際、ほとんどの QP ソルバーは、内点法、主/相補性ピボット法、アクティブセット法など、LCP 定式化に基づいて動作します。^{[ 1 ] [ 2 ]} LCP 問題は、クロス アルゴリズムによっても解くことができます。[ ^{6 ] [ 7 ] [ 8 ] [ 9 ]逆}に、線形相補性問題の場合、クロス アルゴリズムは、行列が十分行列である場合にのみ有限に終了します。^{[ 8 ] [ 9 ]}十分行列は、正定値行列とP 行列の両方の一般化であり、その主小行列式はそれぞれ正です。^{[ 8 ] [ 9 ] [ 10 ]}このような LCP は、方向付きマトロイド理論 を使用して抽象的に定式化されると解くことができます。^{[ 11 ] [ 12 ] [ 13 ]}

• 相補性理論
• 物理エンジンゲーム用のインパルス/コンストレイント型物理エンジンはこのアプローチを採用しています。
• 接触ダイナミクス非平滑アプローチによる接触ダイナミクス。
• 二行列ゲームはLCPに還元できる。

• アンダース・ビョルナー; Las Vergnas, ミシェル; Sturmfels, ベルント;ニール・ホワイト;ツィーグラー、ギュンター(1999)。 「10 線形計画法」。指向性マトロイド。ケンブリッジ大学出版局。 pp. 417–479。土井：10.1017/CBO9780511586507。ISBN  978-0-521-77750-6MR 1744046 .​ 
• Cottle, RW; Dantzig, GB (1968). "数理計画法の相補的ピボット理論" .線形代数とその応用. 1 : 103– 125. doi : 10.1016/0024-3795(68)90052-9 .
• コトル、リチャード・W.、パン、ジョンシ、ストーン、リチャード・E. (1992).線形相補性問題. コンピュータサイエンスと科学計算. ボストン、マサチューセッツ州: Academic Press, Inc. pp.  xxiv+762 pp. ISBN 978-0-12-192350-1MR 1150683 .​ 
• Cottle, RW ; Pang, J.-S.; Venkateswaran, V. (1989 年 3 月～4 月). "十分行列と線形相補性問題". 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). "十分行列を持つ線形相補性問題のための新しい交差型アルゴリズム" (PDF) . Optimization Methods and Software . 21 (2): 247– 266. doi : 10.1080/10556780500095009 . S2CID 24418835 . 
• 福田 浩明、並木 誠 (1994 年 3 月) 「マーティの最小指数法の極値挙動について」数理計画法64 ( 1): 365–370 . doi : 10.1007/BF01582581 . MR 1286455 . S2CID 21476636 .  
• 福田公明; 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. (1993 年 7 月 1 日). 「線形相補性問題、十分行列、および交差法」(PDF) .線形代数とその応用. 187 : 1– 14. doi : 10.1016/0024-3795(93)90124-7 .
• Murty, Katta G. (1972 年 1 月). 「相補性問題の解の数と相補錐の張る性質について」(PDF) .線形代数とその応用. 5 (1): 65– 108. doi : 10.1016/0024-3795(72)90019-5 . hdl : 2027.42/34188 .
• Murty, KG (1988).線形相補性、線形計画法と非線形計画法. シグマ応用数学シリーズ. 第 3巻. ベルリン: ヘルデルマン出版. ISBN 978-3-88538-403-8MR 0949214。更新された無料のPDF版はKatta G. Murtyのウェブサイトで入手可能です。 2010年4月1日にオリジナルからアーカイブされました。 
• Taylor, Joshua Adam (2015).電力システムの凸最適化. Cambridge University Press. ISBN 9781107076877。
• Terlaky, Tamás; Zhang, Shu Zhong (1993). "線形計画法のピボットルール：最近の理論的発展に関する概観". Annals of Operations Research . 最適化問題における退化. 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). "線形計画法と二次計画法を方向付けられたマトロイドで用いる方法" . 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 . 2015年12月18日取得。 

• LCPSolve — GAUSSにおける線形相補性問題を解くための簡単な手順
• Siconos / Numerics は、LCP および MLCP を解決するための Lemke アルゴリズムおよびその他の手法を C 言語で実装したオープンソースの GPL ライセンスのライブラリです。