相補性問題とは - OR事典 Weblio辞書

Weblio 辞書 > 学問 > OR事典 > 相補性問題の意味・解説

OR事典

相補性問題

読み方：そうほせいもんだい
【英】：complementarity problem

概要

変数 $x=(x_1,\dots,x_n) \,$ と同じ次元をもつベクトル値関数 $F(x)=(F_1(x),\dots,F_n(x)) \,$ に対して,

$x_i \ge 0, \ F_i(x) \ge 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 \ge 0, \ F_i(x) \ge 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.

「OR事典」の他の用語

非線形計画：

準ニュートン法目的関数直線探索相補性問題組合せ最適化問題行列分割法近接点法

索引トップ用語の索引ランキングカテゴリー

相補性問題に関係した商品

【送料無料】内点法楽天ブックス
【送料無料】線形計画法楽天ブックス
【送料無料】内点法経営科学のニューフロンティア / 小島政和【全集・双書】HMV ローソンホットステーション R

>> 「相補性問題」を解説文に含む用語の一覧

>> 「相補性問題」を含む用語の索引

相補性問題のページへのリンク

相補性問題のページの著作権
Weblio 辞書情報提供元は参加元一覧にて確認できます。

1		井上和子
2		シグナルペプチド
3		クルーゾン症候群
4		井上和子 (女優)
5		沓名環希
6		TPP
7		先負
8		出不精
9		自由民主党幹事長
10		捗る

11		石松千恵美
12		被用者
13		福利厚生
14		アセスメント
15		ハクビシン
16		タカラダニ
17		未満
18		ご指導ご鞭撻
19		井上和子_(女優)
20		後醍醐天皇

21		イノウエカズコ
22		ダイバーシティ
23		言葉
24		注意喚起
25		遡及
26		クールビズ
27		壮行会
28		赤口
29		こざとへん
30		聖武天皇


	Copyright (C) 2012 （社）日本オペレーションズ・リサーチ学会 All rights reserved.

相補性問題とは？

OR事典

相補性問題

概要

詳説