二次錐計画問題

出典: フリー百科事典『ウィキペディア(Wikipedia)』

出典: フリー百科事典『ウィキペディア(Wikipedia)』

二次錐計画問題 (英:Second-order cone programming, SOCP) は次の形をした凸最適化問題を指す。

minimize
subject to

ただし、問題中に現れる, and はパラメータ定数で、が最適化変数である[1]

この式においてである場合には、二次錐計画問題は単なる線形計画問題となる。また、である場合には二次制約の二次計画問題となる。また二次錐計画問題は制約条件を線形行列不等式として書き直すことで半正定値計画問題の一種とみなすこともできる。二次錐計画問題は内点法による効率的な解法が存在することが知られている。

概要[編集]

二次錐計画問題は、名前の通り実行可能領域が二次錐であるような凸最適化問題を指す。もっとも単純な二次錐は n 次元空間上において次のような集合としてあらわされる。

より一般的な形として

と表されることがあるが、これは

と同値な条件であり、錐体を表す集合であることがわかる。この一般的な錐体の定義により、上のような二次錐計画問題が定義される。

二次錐計画問題には一般的な主双対内点法による解法以外にもバリア関数法などの解法が用いられる。バリア関数法では、上記の凸最適化問題を

minimize

という形に書き換え、これをニュートン法などにより最小化することで各繰り返しにおけるステップ幅を求める[1]

例: 二次制約の問題[編集]

次の二次不等式制約を考える。

この不等式は次のように変形することで錐形の実行可能領域を表す二次錐制約とみなすことができる。

例: 確率計画[編集]

確率的線形計画問題とは次のような不等式制約を含む線形核問題を指す。

minimize
subject to

この式においては平均、共分散の正規乱数を要素とするベクトルであり、である。この問題は次の二次錐計画問題と同値とみなすことができる。

minimize
subject to

ただし誤差関数の逆関数を表す[1]

二次錐計画問題のプログラム[編集]

Name License Brief info
Xpress 商用 バージョン7.6より
CPLEX 商用
Gurobi 商用 並列のバリア関数アルゴリズム
JOptimizer ASLライセンス Javaによる凸最適化のライブラリ(オープンソース)
MOSEK 商用
OpenOpt BSDライセンス 複数の言語に対応した最適化フレームワーク。詳しくはSOCP (英語) を参照のこと。内部ではPythonのライブラリであるNumPyおよびSciPyを用いた疎行列計算が用いられている。

参考文献[編集]

  1. ^ a b c Boyd, Stephen; Vandenberghe, Lieven (2004) (pdf). Convex Optimization. Cambridge University Press. ISBN 978-0-521-83378-3. http://www.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf 2011年10月3日閲覧。.