二次錐計画問題

二次錐計画問題（にじすいけいかくもんだい、、略称: SOCP）とは、次の形をした凸最適化問題を指す。 minimize subject to

ただし、問題中に現れる、かつ はパラメータ定数で、 が最適化変数である。

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

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

より一般的な形として

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

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

二次錐計画問題には一般的な主双対内点法による解法以外にもバリア関数法などの解法が用いられる。バリア関数法では、上記の凸最適化問題を minimize という形に書き換え、これをニュートン法などにより最小化することで各繰り返しにおけるステップ幅を求める。

例: 二次制約の問題 次の二次不等式制約を考える。

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

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

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

ただしは誤差関数の逆関数を表す。

二次錐計画問題のプログラム NameLicenseBrief infoXpress商用 バージョン7.6よりCPLEX商用Gurobi商用並列のバリア関数アルゴリズムJOptimizerASLライセンス Javaによる凸最適化のライブラリ(オープンソース)MOSEK商用OpenOptBSDライセンス 複数の言語に対応した最適化フレームワーク。詳しくはSOCP (英語) を参照のこと。内部ではPythonのライブラリであるNumPyおよびSciPyを用いた疎行列計算が用いられている。

脚注