半正定値計画とは何？わかりやすく解説 Weblio辞書

半正定値計画

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

$\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\succ0\,$ , $Z\succ0\,$ なる許容解 $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))\,$ は次を満たす.

ここで $I\,$ は恒等行列である. 主双対パス追跡法では $X\succ 0\,$ , $Z\succ0\,$ なる現在点が与えられたとして, 適当な $\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\,$ 行列の集合を表す.) となり, 普通の意味でニュートン方向を定義できない. この問題を克服するためにいろいろな手段が考えられ, その結果様々な探索方向が提案されている. 以下に, 比較的初期に提案された探索方向を四つ挙げる. (方向の名前は, 提案した論文の著者名に由来している.)

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] 参照.

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