相補性問題

【そうほせいもんだい (complementarity problem)】

概要

変数 $x=(x_{1},\dots ,x_{n})\,$ と同じ次元をもつベクトル値関数 $F(x)=(F_{1}(x),\dots ,F_{n}(x))\,$ に対して,

$x_{i}\geq 0,\ F_{i}(x)\geq 0,\ x_{i}F_{i}(x)=0\quad (i=1,\dots ,n)\,$

を満たす $x\,$ を求める問題. 特に$F_{i}\,$がすべて1次関数のとき線形相補性問題, そうでないとき非線形相補性問題と呼ぶ.

詳説

　相補性問題(complementarity problem)[1] とは，連続変数 $x=(x_{1},\dots ,x_{n})\,$ と同じ次元をもつベクトル値関数 $F(x)=(F_{1}(x),\dots ,F_{n}(x))\,$ に対して，次式を満たす $x\,$ を求める問題である．

$x_{i}\geq 0,\ F_{i}(x)\geq 0,\ x_{i}F_{i}(x)=0\quad (i=1,\dots ,n)$

この問題において，すべての$i\,$に対して$x_{i}\geq 0\,$かつ$F_{i}(x)\geq 0\,$となる点$x\,$の集合を実行可能集合と呼ぶ．とくに，すべての$i\,$に対して狭義の不等式を満たす点$x\,$を狭義実行可能点と呼ぶ．また，すべての$i\,$に対して，$x_{i}=0\,$または$F_{i}(x)=0\,$が成り立つことを，相補条件と呼ぶ．相補性問題は，実行可能集合の中から相補条件が成り立つ点を求める問題と考えることができる．相補性問題の中で，$F\,$ がアフィン関数，つまり$n\times n\,$行列$M\,$と$n\,$次元ベクトル$q\,$を用いて$F(x)=Mx+q\,$と表されるものを，線形相補性問題(linear complementarity problem)と呼ぶ．また，それ以外の問題を非線形相補性問題(nonlinear complementarity problem)という．相補性問題を含むより広いクラスの問題として，変分不等式問題(variational inequality problem)がある．変分不等式問題は，与えられた閉凸集合$S\subseteq \mathbf {R} ^{n}$に対して， 次の不等式を満たす点$x\in S\,$を求める問題である．

$\langle F(x),y-x\rangle \geq 0,\;\;\;\forall y\in S$

ここで，$\langle \cdot ,\cdot \rangle \,$はベクトルの内積をあらわす．特に$S=\mathbf {R} _{+}^{n}:=\{x\in \mathbf {R} ^{n}\;|\;x_{i}\geq 0\quad (i=1,\dots ,n)\}\,$で与えられた変分不等式問題は相補性問題に帰着できる．また，$\mathbf {R} _{+}^{n}\,$を一般の凸錘に拡張した一般相補性問題，対称半正定値行列空間に拡張した半正定値相補性問題と呼ばれる問題もある．

　2次計画問題(quadratic programming problem)のカルーシュ・キューン・タッカー条件は，線形相補性問題としてあらわされる．また，非線形計画問題のカルーシュ・キューン・タッカー条件は，非線形相補性問題としてあらわされる．このため，相補性問題に対する効率的な方法を考えることは数理計画において重要な役割をはたす．また，経済均衡問題や交通流均衡問題などの多くの均衡問題(equilibrium problem)が，相補性問題として定式化できることが知られている．最近では，オプション価格の算出，摩擦を有する物理現象のモデル化などにも有用であることが報告されている．

　このように相補性問題は，オペレーションズリサーチにおいて重要な問題であるが，その解の計算は必ずしも容易ではない．このことは，一般の線形相補性問題がNP完全問題であることからもわかる．そのため，相補性問題に対しては，解きやすい問題のクラスの解明とそれらに対する解法の研究が進められている．関数$F\,$が，凸性と密接な関係のある単調関数であるとき，相補性問題は比較的容易な問題となる．ここで，$F\,$が単調であるとは，

$\langle F(x)-F(y),x-y\rangle \geq 0,\;\;\forall x,y\in \mathbf {R} ^{n}$

が成り立つことである．制約が1次関数で与えられた凸計画問題のカルーシュ・キューン・タッカー条件は，単調関数で定義された非線形相補性問題であらわされる．また，$F\,$が単調関数で相補性問題が狭義実行可能点を持つとき，相補性問題の解集合は空でない有界凸集合になることが知られている．これまでに，$F\,$が単調な相補性問題に対して，様々な解法が提案されている．初期には，線形相補性問題に対して，不動点アルゴリズム(fixed point algorithm)の一種であるレムケ法が提案され，そのアルゴリズムが実用化されてきた [2]．近年では，相補性問題を等価な方程式系や最適化問題などに再定式化して解くアルゴリズムの有効性が示されている．特に，等価な方程式系を近似した方程式をニュートン法で逐次的に解く内点法タイプのアルゴリズム [3] が理論的にも実用的にも速く解に収束することが報告されている．

　相補性問題や変分不等式問題を制約条件に含む数理計画問題を均衡制約計画問題(mathematical program with equilibrium constraints)[4] と呼ぶ．スタッケルベルグ・ゲームや2レベル計画問題(bilevel programming problem)は，下位レベルの問題をそのカルーシュ・キューン・タッカー条件に置き換えることによって，均衡制約計画問題に帰着することができる．均衡制約計画問題では，通常の制約想定が成り立たないことが知られている．このため，均衡制約計画問題は，一般の非線形計画問題に対するアルゴリズムで解が得られる保証がない困難な問題である．これまでに，均衡制約計画問題に対して内点法や逐次2次計画法を拡張する試みがなされている．

---

参考文献

[1] F.Facchinei and J.-S. Pang, Finite-Dimensional Variational Inequalities and Complementarity Problems Volumes Ⅰ and Ⅱ, Springer-Verlag, 2003.

[2] 小島政和, 『相補性と不動点』, 産業図書, 1981.

[3] M. Kojima, N. Megiddo, T. Noma and A. Yoshise, A Unified Approach to Interior Point Algorithms for Linear Complementarity Problems, Springer-Verlag, 1991.

[4] Z.-Q. Luo, J.-S. Pang and D. Ralph, Mathematical Programs with Equilibrium Constraints, Cambridge University Press, 1996.

[5] 福島雅夫,『非線形最適化の基礎』, 朝倉書店, 2001.