半正定値計画問題#

  • 読み: はんせいていちけいかくもんだい

  • 英名: 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\) に対する以下の線形計画問題

(92)#\[\begin{split}\begin{array}{ll} \min & c^\top x \\ \mathrm{s.t.} & Ax - b\ge 0 \end{array}\end{split}\]

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

(93)#\[\begin{split}\begin{array}{ll} \min & c^\top x \\ \mathrm{s.t.} & \sum_{i=1}^n A_i x_i - B \succeq 0 \end{array}\end{split}\]

は半正定値計画問題である. ここで,\(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\) がいずれも対角行列である場合,

(94)#\[\begin{split}\begin{array}{rll} A &=& \left( \mathrm{diag}(A_1), \ldots, \mathrm{diag}(A_m) \right) \\ b &=& \mathrm{diag}(B) \end{array}\end{split}\]

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

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

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

(95)#\[\begin{split}\begin{array}{ll} \min & \langle C,X \rangle \\ \mathrm{s.t.} & \langle A_j,X \rangle = b_j, \, j=1,\cdots,m \\ & X \succeq 0 \end{array}\end{split}\]

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

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

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

ところが,この双対問題は

(97)#\[\begin{split}\begin{array}{ll} \min & b^\top y \\ \mathrm{s.t.} & \sum_{j=1}^m A_j y_j \preceq C \end{array}\end{split}\]

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

(98)#\[\begin{split}\begin{array}{rll} \sum_{j=1}^m A_j y_j + Z & = & C \\ Z & \succeq & 0 \end{array}\end{split}\]

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

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

半正定値計画問題を解くアルゴリズム#

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

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

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

半正定値計画問題の応用#

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

  • 制御における安定性条件の記述

  • 0-1 混合整数計画問題における,強力な緩和解の導出

  • 低ランク条件の緩和

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

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

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

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

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

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

参考文献

[1]

Michel X. Goemans and David P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM, 42(6):1115–1145, nov 1995. URL: https://dl.acm.org/doi/10.1145/227683.227684, doi:10.1145/227683.227684.

[2]

M. J. Todd. Semidefinite optimization. Acta Numerica, 10:515–560, may 2001. URL: https://www.cambridge.org/core/product/identifier/S0962492901000071/type/journal_article, doi:10.1017/S0962492901000071.

[3]

Henry Wolkowicz, Romesh Saigal, and Lieven Vandenberghe, editors. Handbook of Semidefinite Programming. Volume 27 of International Series in Operations Research & Management Science. Springer US, Boston, MA, 2000. ISBN 978-1-4613-6970-7. URL: http://link.springer.com/10.1007/978-1-4615-4381-7, doi:10.1007/978-1-4615-4381-7.

[4]

田村明久 and 村松正和. 最適化法 (工系数学講座 17). 共立出版, 2002.

[5]

久保幹夫, 田村明久, and 松井知己. 応用数理計画ハンドブック. 朝倉書店, 2002.

[6]

Katsuki Fujisawa, Masakazu Kojima, and Kazuhide Nakata. Exploiting sparsity in primal-dual interior-point methods for semidefinite programming. Mathematical Programming, 79(1-3):235–253, oct 1997. URL: http://link.springer.com/10.1007/BF02614319, doi:10.1007/BF02614319.

[7]

Michal Kočvara and Michael Stingl. PENNON: A code for convex nonlinear and semidefinite programming. Optimization Methods and Software, 18(3):317–333, jun 2003. URL: http://www.tandfonline.com/doi/abs/10.1080/1055678031000098773, doi:10.1080/1055678031000098773.

[8]

福田光浩. 半正定値計画問題に対するソルバーの紹介 (< 特集> 半正定値計画に対するソルバーと応用例). オペレーションズ・リサーチ: 経営の科学, 55(7):393–399, 2010. URL: https://orsj.org/wp-content/corsj/or55-7/or55_7_393.pdf.

[9]

Hiroshi Yamashita, Hiroshi Yabe, and Kouhei Harada. A primal–dual interior point method for nonlinear semidefinite programming. Mathematical Programming, 135(1-2):89–121, oct 2012. URL: http://link.springer.com/10.1007/s10107-011-0449-z, doi:10.1007/s10107-011-0449-z.

[10]

Aharon Ben-Tal and Arkadi Nemirovski. Lectures on Modern Convex Optimization. Society for Industrial and Applied Mathematics, jan 2001. ISBN 978-0-89871-491-3. URL: http://epubs.siam.org/doi/book/10.1137/1.9780898718829, doi:10.1137/1.9780898718829.

[11]

Zhi-quan Luo, Wing-kin Ma, Anthony So, Yinyu Ye, and Shuzhong Zhang. Semidefinite Relaxation of Quadratic Optimization Problems. IEEE Signal Processing Magazine, 27(3):20–34, may 2010. URL: http://ieeexplore.ieee.org/document/5447068/, doi:10.1109/MSP.2010.936019.

[12]

Jean B. Lasserre. Global Optimization with Polynomials and the Problem of Moments. SIAM Journal on Optimization, 11(3):796–817, jan 2001. URL: http://epubs.siam.org/doi/10.1137/S1052623400366802, doi:10.1137/S1052623400366802.

[13]

Hayato Waki, Sunyoung Kim, Masakazu Kojima, and Masakazu Muramatsu. Sums of Squares and Semidefinite Program Relaxations for Polynomial Optimization Problems with Structured Sparsity. SIAM Journal on Optimization, 17(1):218–242, jan 2006. URL: http://epubs.siam.org/doi/10.1137/050623802, doi:10.1137/050623802.

[14]

M. Fazel, H. Hindi, and S.P. Boyd. A rank minimization heuristic with application to minimum order system approximation. In Proceedings of the 2001 American Control Conference. (Cat. No.01CH37148), 4734–4739 vol.6. IEEE, 2001. URL: http://ieeexplore.ieee.org/document/945730/, doi:10.1109/ACC.2001.945730.