半正定値計画とは? わかりやすく解説

Weblio 辞書 > 学問 > OR事典 > 半正定値計画の意味・解説 

半正定値計画

読み方はんせいていちけいかく
【英】:semidefinite programming

概要

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

\mbox{min.}_X \, \mbox{trace} (CX)\,
\mbox{s.t.} \, \mbox{trace} (A_i X) = b_i, i=1,\ldots,m,\,
X\succeq0,\,


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

詳説

 問題: 半正定値計画は線形計画(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\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))\, は次を満たす.


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)\succ0,\quad Z(\mu)\succ0.\,


ここで 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\, 行列集合を表す.) となり, 普通の意味ニュートン方向を定義できない. この問題克服するためにいろいろな手段考えられ, その結果様々な探索方向提案されている. 以下に, 比較初期提案され探索方向四つ挙げる. (方向の名前は, 提案した論文著者名由来している.)


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.

「OR事典」の他の用語
線形計画:  内点法  凸計画問題  分離問題  半正定値計画  半正定値計画緩和  単体法  双対問題

半正定値計画問題

(半正定値計画 から転送)

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2025/05/17 02:51 UTC 版)

半正定値計画問題(はんせいていちけいかくもんだい、: semidefinite programming)とは、半正定値行列全体によって作られる凸錐体上での凸最適化問題(convex optimization)の一つである。

半正定値計画問題は近年いくつかの理由で成長している最適化の一分野である。その理由として多くの実用例が考えられることがあげられるが、特にオペレーションズ・リサーチ組み合わせ最適化などの分野で広く研究が行われている。自動制御理論の分野では半正定値計画問題が線形不等式制約のもとで行われることが多い。半正定値計画問題は、凸錐体上の凸最適化問題の一種であり、内点法などにより効率よく解を与えることが可能であることも、応用が期待される一要因となっている[1]。また半正定値計画問題の階層化により多項式最適化問題が近似的に解けるほか、複雑系の最適化にも応用が可能である。

定義

線形計画問題はある空間上で多面体に含まれるような実数の組に対して、線形の目的関数を最小化・最大化する問題である。ここで、多面体というのは、より厳密には凸集合であるということを指す。一方で、半正定値計画問題においては、ベクトルの内積を最適化する。特に、一般的な半正定値計画問題は、数理計画問題の形式として、以下のように定義される(ただし、内積を表す)。

さらに、この問題は半正定値行列の作る凸錐体上の問題として書き直すことができる。大きさが の行列 本のベクトル を用いて で表されるとき、行列グラム行列といい、この行列は半正定値となることが知られている。

ここで、 を実対称行列全体の空間とする。この空間では内積を (ただし、 は行列のを表す)と定義することができて、これを用いると、前述のベクトルを用いた半正定値計画問題が次の形で書き直せる。

ただし、 とは行列 が半正定値行列であることを表す。この式において を、 の行列で を成分に持つ。

双対性

双対問題の定義

線形計画問題と同様、半正定値計画問題も双対問題を考えることが可能で、

という半正定値計画問題の双対問題は

という形で与えられる。なお大きさが等しい2つの正方行列 に対して、 とは、 と同義である。

弱双対性

弱双対定理とは、半正定値計画問題の主問題と双対問題の許容解の関係を表す定理であり、主問題の許容解が双対問題の上界となり、双対問題の許容解が主問題の下界となるというものである。 これは、次の式により示される。

最後の不等式が成立するのは、行列の内積を取っている2つの行列が、どちらも半正定値行列であるためである。

強双対性

スレーター条件と呼ばれる条件の下では、主問題と双対問題の最適解が一致することが知られている。これを強双対性という。線形計画問題と違い、半正定値問題は、すべての問題が強双対性を満たすわけではなく、一般には双対問題の最適解は主問題の最適解よりも小さい。強双対性は次の2つの性質により言い表される。

  1. 主問題が下に有界であり、かつ内点許容解をもつとき、双対問題が最適解を持つ。
  2. 双対問題が上に有界であり、かつ内点許容解をもつとき、主問題が最適解を持つ。

この2つの性質から、主問題と双対問題の両方が最適解を持ち、それらが一致することが言える。

脚注

  1. ^ 藤江 2012, p. 832.

参考文献



英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「半正定値計画」の関連用語

半正定値計画のお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



半正定値計画のページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
日本オペレーションズ・リサーチ学会日本オペレーションズ・リサーチ学会
Copyright (C) 2025 (社)日本オペレーションズ・リサーチ学会 All rights reserved.
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアの半正定値計画問題 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。

©2025 GRAS Group, Inc.RSS