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

Weblio 辞書 > 学問 > OR事典 > 半正定値計画の意味・解説 
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), X は n\times n 実対称行列,\mbox{trace}(\cdot) は行列のトレース,X\succeq0 は 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\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/03/12 03:47 UTC 版)

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

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

定義

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


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

辞書ショートカット

カテゴリ一覧

全て

＋ ビジネス

＋ 業界用語

＋ コンピュータ

＋ 電車

＋ 自動車・バイク

＋ 船

＋ 工学

＋ 建築・不動産

＋ 学問

＋ 文化

＋ 生活

＋ ヘルスケア

＋ 趣味

＋ スポーツ

＋ 生物

＋ 食品

＋ 人名

＋ 方言

＋ 辞書・百科事典

すべての辞書の索引

あいうえお
かきくけこ
さしすせそ
たちつてと
なにぬねの
はひふへほ
まみむめも
やゆよ
らりるれろ
わをん
がぎぐげご
ざじずぜぞ
だぢづでど
ばびぶべぼ
ぱぴぷぺぽ
ＡＢＣＤＥ
ＦＧＨＩＪ
ＫＬＭＮＯ
ＰＱＲＳＴ
ＵＶＷＸＹ
Ｚ
１２３４５
６７８９０
記号

Weblioのサービス

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

1
半正定値計画緩和
OR事典
100% |||||

2
線形行列不等式
OR事典
100% |||||

3
半正定値計画問題
OR事典
78% |||||

4
対称錐計画問題
OR事典
78% |||||

5
多項式時間
ウィキペディア小見出し辞書
70% |||||

6
SDP
百科事典
52% |||||

7
内点法
OR事典
38% |||||

8
パーフェクトグラフ
OR事典
34% |||||

9
カット (グラフ理論)
百科事典
32% |||||

10
二次錐計画問題
百科事典
16% |||||

半正定値計画のお隣キーワード

半棒術

半棘筋

半次元

半次郎

半正多胞体

半正多面体

半正定値計画

半正定値計画問題

半正定値計画緩和

半母音

半沢

半沢あい

半沢ありさ

検索ランキング

   

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


半正定値計画のページの著作権
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