半正定値計画

【はんせいていちけいかく (semidefinite programming)】

概要

線形計画を実対称行列の空間に拡張したもの.等質自己双対錐上の線形計画問題の1つでもある.半正定値計画は

${\mbox{min.}}_{X}\,$	${\mbox{trace}}(CX)\,$
${\mbox{s.t.}}\,$	${\mbox{trace}}(A_{i}X)=b_{i},i=1,\ldots ,m,\,$
	$X\succeq 0,\,$

で表される.ただし, $C,A_{i}\ (i=1,\ldots ,m),X$ は $n\times n$ 実対称行列,${\mbox{trace}}(\cdot )$ は行列のトレース,$X\succeq 0$ は $X$ が半正定値であることを表す.

詳説

　問題: 半正定値計画は線形計画(linear programming)を実対称行列の空間に拡張したものである. 次のような定式化が一般的である.

${\mbox{(P)}}\quad \mathop {\mbox{min.}} C\bullet X{\mbox{s. t.}}\ A_{i}\bullet X=b_{i}\;\;(i=1,2,\ldots ,m),X\succeq 0.\,$

ただし, $C,A_{i}\ (i=1,2,\ldots ,m),X\,$ は $n\times n\,$ 実対称行列, $\textstyle C\bullet X={\mbox{trace}}(CX)=\sum _{i,j}C_{ij}X_{ij},X\succeq (\succ )0\,$は $X\,$が半正定値(正定値)であることを表す. 半正定値計画${\mbox{(P)}}\,$ は凸計画問題(convex programming)であり, 双対問題は次のようになる.

${\mbox{(D)}}\quad \mathop {\mbox{max.}} \ b^{\top }y{\mbox{s. t.}}\ Z+\sum _{i=1}^{m}y_{i}A_{i}=C,Z\succeq 0.\,$

　双対性: ${\mbox{(P)}}\,$ と${\mbox{(D)}}\,$ の間に次の弱双対定理が成り立つことは容易に分かる.

　弱双対定理. $X\,$を${\mbox{(P)}}\,$ の許容解, $(y,Z)\,$ を${\mbox{(D)}}\,$ の許容解とすると, $C\bullet X\geq b^{\top }y\,$.

半正定値計画では線形計画とは異なり, 一般に強双対定理は成り立たない. 主問題または双対問題に最適解が存在しないことや, 両者の最適値が一致しないことがある. 強双対定理が成り立つためには何らかの条件が必要である. よく使われる条件は次のようなものである.

　強双対定理.　もし $X\succ 0\,$, $Z\succ 0\,$ なる許容解 $X\,$ および $(y,Z)\,$ が存在すれば, ${\mbox{(P)}}\,$ と ${\mbox{(D)}}\,$ の最適値は一致し, 両者に最適解が存在する.

最適解があっても強相補性を持つ解が存在しない場合があり, また, 退化に関しても特有の定義が使われることが多い. 半正定値計画における退化および強相補性に関しては [1] を参照せよ.

　解法: 半正定値計画 ${\mbox{(P)}}\,$ には, $-\log \det X\,$が$n\,$-自己整合障壁関数(self-concordant barrier function)となることが知られており, 主内点法(interior point method)を使って効率良く解くことができる [3]. また半正定値計画は, 等質自己双対錐(homogeneous self-dualcone, symmetric cone, self-scaled cone)上の線形計画問題とも見ることができ, 主双対内点法で効率良く解くことができる[4]. 以下, 現在最も有力な解法とみられている主双対パス追跡法について説明する.

　半正定値計画 ${\mbox{(P)}}\,$ および${\mbox{(D)}}\,$ の中心パス(path of centers)上のパラメタ $\mu >0\,$ に対応する点$(X(\mu ),y(\mu ),Z(\mu ))\,$は次を満たす.

$A_{i}\bullet X(\mu )=b_{i}\quad (i=1,2,\ldots ,m),$	$(1)\,$
$Z(\mu )+\sum _{i=1}^{m}y_{i}(\mu )A_{i}=C,$	$(2)\,$
$X(\mu )Z(\mu )=\mu I$	$(3)\,$
$X(\mu )\succ 0,\quad Z(\mu )\succ 0.\,$

ここで $I\,$ は恒等行列である. 主双対パス追跡法では $X\succ 0\,$, $Z\succ 0\,$ なる現在点が与えられたとして, 適当な $\mu \,$ を定めて(1), (2), (3)に対するニュートン方向を探索方向とする. ところが一般に $XZ\,$ は対称行列ではないので, 式 (1), (2), (3) の左辺$-\,$右辺を一つの関数と見た場合, その関数は$({\mathbf {S} }^{n},{\mathbf {R} }^{m},{\mathbf {S} }^{n})\rightarrow ({\mathbf {R} }^{m},{\mathbf {S} }^{n},{\mathbf {M} }_{n})\,$(ここで${\mathbf {S} }^{n}\,$は$n\times n\,$対称行列の集合, ${\mathbf {M} }_{n}\,$は$n\times n\,$ 行列の集合を表す.) となり, 普通の意味でニュートン方向を定義できない. この問題を克服するためにいろいろな手段が考えられ, その結果様々な探索方向が提案されている. 以下に, 比較的初期に提案された探索方向を四つ挙げる. (方向の名前は, 提案した論文の著者名に由来している.)

NT 方向: (より大きなクラスである)等質自己双対錐上の線形計画問題に対するある意味で自然な探索方向として定義されるもの.

AHO 方向: (3) を $ZX+XZ=2\mu I\,$ と対称化してニュートン方向を探索方向とする.

KSH/HRVW/M 方向 (KHM方向): $X\in {\mathcal {M}}_{n}\,$としてニュートン方向 ${\tilde {\Delta X}}\,$ を計算し, それを$({\tilde {\Delta X}}+{\tilde {\Delta X}}^{\top })/2\,$ と対称化して$X\,$成分の探索方向とする.

MT 方向: (3) を $X^{1/2}ZX^{1/2}=\mu I\,$ と対称化してニュートン方向を探索方向とする.

理論的には, これらの探索方向を使うと, 許容解 $(X^{0},y^{0},Z^{0})\,$ から出発した場合, $O({\sqrt {n}}\log(X^{0}\bullet Z^{0}/\epsilon ))\,$回の反復で双対ギャップを $\epsilon \,$ 以下に減らすことができることが知られている. 詳しくは [6] 参照.

　半正定値計画の解法としては, 単体法はあまり研究されていない. 係数行列に構造のある問題に対しては, 固有値に関する最適化問題に直して微分不可能最適化に対する手法を適用することも試みられている.

　応用: 半正定値計画の応用で最もORと関係が深いのは組合せ最適化問題(combinatorial optimization)および多項式最適化問題の半正定値計画緩和(semidefinite programming relaxzation)であろう. NP困難(NP-hard)な組合せ最適化問題または多項式最適化問題(polynomial optimization problem)の緩和問題として半正定値計画を使うと, 元問題の最適値の良い近似値を多項式時間で求められる. 行列の固有値に関する最適化問題, 例えば固有値の和の最小化なども半正定値計画で表現できる. また, 制御理論における線形行列不等式(linear matrix inequality)は${\mbox{(D)}}\,$ と等価である. 半正定値計画の応用については [2], [5], [6] を参照されたい.

---

参考文献

[1] F. Alizadeh, J. P. A. Haeberly and M. L. Overton, "Complementarity and nondegeneracy in semidefinite programming," Mathematical Programming, 77 (1997) 111-128.

[2] M. X. Goemans, "Semidefinite programming in combinatorial optimization," Mathematical Programming, 79 (1997) 143-161.

[3] Y. E. Nesterov and A. S. Nemirovskii Interior Point Polynomial Methods in Convex Programming : Theory and Algorithms, SIAM Publications, Philadelphia, 1993.

[4] Y. E. Nesterov and M. J. Todd, "Primal-dual interior-point methods for self-scaled cones," SIAM Journal on Optimization, 8 (1998) 324-364.

[5] L. Vandenberghe and S. Boyd, "Semidefinite programming," SIAM review, 38 (1996) 49-95.

[6] 小島政和, 土谷隆, 水野眞治, 矢部博, 『内点法』, 朝倉書店, 2001.