トップ > 数理計画用語集 > 半正定値計画問題

数理計画用語集

半正定値計画問題

読み:はんせいていちけいかくもんだい
英名:Semidefinite Programming Problem
別名:SDP

半正定値計画問題は線形計画問題の拡張であり,英語の頭文字から SDP(SemiDefinite Programming) とも呼ばれる.

端的には,線形計画問題における線形の不等式制約を線形対称行列に関する半正定値の制約に拡張した問題が半正定値計画問題である.以下,$m$ 次対称行列全体の集合を $\mathbb{S}^m$ とし,それが半正定値である事を $\succeq 0$ あるいは $\succeq O$ にて表現する.

例えば,定数 $A \in \mathbb{R}^{m \times n}, b \in \mathbb{R}^m, c \in \mathbb{R}^n$,変数 $x \in \mathbb{R}^n$ に対する以下の線形計画問題

\[\begin{array}{ll} \mbox{minimize} & c^\top x \\ \mbox{subject to} & Ax - b\ge 0 \end{array}\]

において,不等式制約を半正定値制約に置き換えた

\[\begin{array}{ll} \mbox{minimize} & c^\top x \\ \mbox{subject to} & \sum_{i=1}^n A_i x_i - B \succeq 0 \end{array}\]

は半正定値計画問題である.ここで,$A_1, \cdots, A_n, B \in \mathbb{S}^m$ である.

一般に,対称行列 $X,Y \in \mathbb{S}^m$ に対して $X - Y \succeq 0$ は $X \succeq Y$ あるいは $Y \preceq X$ とも記述される事に注意する.

線形計画問題は半正定値計画問題の特殊な場合とみなせる.具体的に上述の例では $m$ 次対称行列 $A_i, B$ がいずれも対角行列である場合,

\[\begin{align} A &= \left( \mbox{diag}(A_1), \cdots, \mbox{diag}(A_m) \right) \\ b &= \mbox{diag}(B) \end{align}\]

とすることにより線形計画問題に帰着される.

半正定値計画問題には,しばしば行列変数が出現する.しかしながら,全ての半正定値計画問題に必ずしも行列変数が陽に含まれる訳ではない事に注意する.

例えば,標準的な半正定値計画問題は定数 $A_1, \cdots, A_m , C \in \mathbb{R}^{n \times n}, b \in \mathbb{R}^m$, 対称行列変数 $X \in \mathbb{R}^{n \times n}$ に対して

\[\begin{array}{ll} \mbox{minimize} & \langle C,X \rangle \\ \mbox{subject to} & \langle A_j,X \rangle = b_j, \, j=1,\cdots,m \\ & X \succeq 0 \end{array}\]

という形で記述される.ここで

\[ \langle C,X \rangle = \sum_{i=1}^n \sum_{j=1}^n C_{ij} X_{ij} \]

である.$\langle C,X \rangle$ のかわりに $C \bullet X$ と記述される事も多い.

ところが,この双対問題

\[\begin{array}{ll} \mbox{minimize} & b^\top y \\ \mbox{subject to} & \sum_{j=1}^m A_j y_j \preceq C \end{array}\]

で与えられ,変数は $y \in \mathbb{R}^m$ しか出現しない.もっとも,半正定値制約に対してスラック行列変数を導入する事で隠れた行列変数を陽に出現させることはできる.例えば,上述の双対問題に対する制約はスラック行列変数 $Z \in \mathbb{R}^{n \times n}$ を導入することで

\[\begin{align} \sum_{j=1}^m A_j y_j + Z &= C \\ Z &\succeq 0 \end{align}\]

という等価な制約に変形できる.

半正定値計画問題は線形計画問題の拡張とみなせるが,線形計画問題と異なり半正定値計画問題の場合は実行可能領域に相対的内点が存在しない場合がある.この場合,強双対定理が成立しない事に注意する.

半正定値計画問題の研究は膨大である.全てをサーベイする事は不可能に近いが,より詳しい内容は [9,13] などを参照されたい.和書では半正定値計画問題を詳しく取り扱っている文献は少ないが [8,11] には一定の記述が存在する.

半正定値計画問題は凸計画問題に属する問題であり,幾つかの効率的なアルゴリズムの存在が知られている.代表的な方法は主双対内点法であるが様々な派生系が存在する.これらは線形計画問題に対する主双対内点法の拡張とみなせるが,線形計画問題の場合と異なり,アルゴリズム内部で計算する Newton 探索方向に関して面倒な議論が存在する.加えて,線形計画問題の場合は問題とならないステップ幅計算のコストも半正定値計画問題では固有値計算が必要になるため無視できない.また,半正定値計画問題ならではの疎性を利用した特殊な高速化技法も研究されており [3],線形計画問題に対する主双対内点法と比べて工夫の余地は大きい.他にも,拡張ラグランジュ関数法を利用したアルゴリズムなどが存在する [10].

半正定値計画問題の研究は現在も進んでおり,このクラスの問題を取り扱えるソフトウェアも多数存在する [4].弊社の Numerical Optimizer では,半正定値計画問題のみならず非線形半正定値計画問題にも対応し,モデリング言語を介する事により通常の等式・不等式制約を含めた取り扱いが容易な点が特色である. Numerical Optimizer にて実装されているアルゴリズムの理論的背景は [14] を参照されたい.

半正定値計画問題の応用例としては,以下が良く知られている.

制御において半正定値計画問題が適用され得る理由は,制御システムの安定性を示すリアプノフ条件が行列の半正定値制約で表現される事による.通常この半正定値制約は非線形となるが特殊な場合は線形の半正定値制約でも記述することができる [1].

0-1 混合整数計画問題の緩和に半正定値計画問題を利用する方法は近年盛んに研究されており,緩和により単に下界を得るだけでなく,良質な実行可能解を得る巧妙な解法がいくつか提案されている.著名な結果は [5] であるが,最近の結果は [7] によくまとめられている.

半正定値計画問題による緩和の適用対象は 0-1 混合整数計画問題に限らない.理論的には,一般の多項式計画問題に対して半正定値計画問題による緩和が適用できる.最初のアイデアは [6] によるが当初の結果では実用レベルの問題に適用するには難しい状況であった.以後 [12] 等の研究により計算量を削減する試みがなされている.

所与の行列に近い半正定値行列を求める問題も半正定値計画問題として記述が可能である.特に求める行列の対角成分が 1 となる場合は相関行列取得問題と呼ばれる.これらの問題はソルバーを利用して解くことも出来るが,特殊な構造を持つ問題が多く,その構造を生かした様々な解法が提案されている.

行列の低ランク条件も半正定値計画問題としてある程度考慮する事ができる.行列のランクに関する制約は凸制約にはならないものの,その最小な凸緩和は半正定値計画問題となる [2].回帰において,L1 ノルム最小化( ridge 回帰)によりスパース解が実現出来る事はよく知られているが,上記の結果はこの事実の行列版への拡張ともみなせる.

他にも,金融の分野においてロバストポートフォリオ最適化などの応用例が存在する.

[参考]
[1] Ben-Tal, Aharon, and Arkadi Nemirovski. "Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering Applications, vol. 2 of MPS/SIAM Series on Optimization." Society of Industrial and Applied Mathematics, Philadelphia (2001).
[2] Fazel, Maryam, Haitham Hindi, and Stephen P. Boyd. "A rank minimization heuristic with application to minimum order system approximation." American Control Conference, 2001. Proceedings of the 2001. Vol. 6. IEEE, 2001.
[3] Fujisawa, Katsuki, Masakazu Kojima, and Kazuhide Nakata. "Exploiting sparsity in primal-dual interior-point methods for semidefinite programming." Mathematical Programming 79.1-3 (1997): 235-253.
[4] 福田光浩. "半正定値計画問題に対するソルバーの紹介 (< 特集> 半正定値計画に対するソルバーと応用例)." オペレーションズ・リサーチ: 経営の科学 55.7 (2010): 393-399.
[5] Goemans, Michel X., and David P. Williamson. "Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming." Journal of the ACM (JACM) 42.6 (1995): 1115-1145.
[6] Lasserre, Jean B. "Global optimization with polynomials and the problem of moments." SIAM Journal on Optimization 11.3 (2001): 796-817.
[7] Luo, Zhi-quan, et al. "Semidefinite relaxation of quadratic optimization problems." Signal Processing Magazine, IEEE 27.3 (2010): 20-34.
[8] 田村明久・村松正和:最適化法, 共立出版 (2002)
[9] Todd, Michael J. "Semidefinite optimization." Acta Numerica 2001 10 (2001): 515-560.
[10] Kocvara, Michal, and Michael Stingl. "PENNON: A code for convex nonlinear and semidefinite programming." Optimization methods and software 18.3 (2003): 317-333.
[11] 久保幹雄,松井知己,田村明久:応用数理計画ハンドブック,朝倉書店,2002.
[12] Waki, Hayato, et al. "Sums of squares and semidefinite program relaxations for polynomial optimization problems with structured sparsity." SIAM Journal on Optimization 17.1 (2006): 218-242.
[13] Wolkowicz, Henry, ed. Handbook of Semidefinite Programming: theory, algorithms, and applications. Kluwer Academic Publishers, 2000.
[14] Yamashita, Hiroshi, Hiroshi Yabe, and Kouhei Harada. "A primal-dual interior point method for nonlinear semidefinite programming." Mathematical programming 135.1-2 (2012): 89-121.