二次錐計画問題

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

minimize $\ f^{T}x\$

subject to

$\lVert A_{i}x+b_{i}\rVert _{2}\leq c_{i}^{T}x+d_{i},\quad i=1,\dots ,m$

$Fx=g\$

ただし、問題中に現れる$f\in \mathbb {R} ^{n},\ A_{i}\in \mathbb {R} ^{{n_{i}}\times n},\ b_{i}\in \mathbb {R} ^{n_{i}},\ c_{i}\in \mathbb {R} ^{n},\ d_{i}\in \mathbb {R} ,\ F\in \mathbb {R} ^{p\times n}$, and $g\in \mathbb {R} ^{p}$はパラメータ定数で、$x\in \mathbb {R} ^{n}$が最適化変数である。

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

概要

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

${\mathcal {C}}_{0}:=\left\{x\in \mathbb {R} ^{n}:{\sqrt {\sum _{i=1}^{n-1}x_{i}^{2}}}\leq x_{n}\right\}.$

より一般的な形として

${\mathcal {C}}:=\left\{x\in \mathbb {R} ^{m}:\|Ax+b\|\leq c^{T}x+d\right\},A\in \mathbb {R} ^{(n-1)\times m},b\in \mathbb {R} ^{n-1},c\in \mathbb {R} ^{m},d\in \mathbb {R}$

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

${\begin{bmatrix}A\\c^{T}\end{bmatrix}}x+{\begin{bmatrix}b\\d\end{bmatrix}}\in {\mathcal {C}}_{0}$

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

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

minimize $f^{T}x-\log \left(-(Fx-g)\right)-\sum _{i=1}^{m}\log \left({\frac {1}{2}}\left(\|A_{i}x+b_{i}\|_{2}^{2}-(c_{i}^{T}x+d_{i})^{2}\right)\right)$

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

例: 二次制約の問題

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

$x^{T}A^{T}Ax+b^{T}x+c\leq 0.$

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

$\left\|{\begin{matrix}(1+b^{T}x+c)/2\\Ax\end{matrix}}\right\|_{2}\leq (1-b^{T}x-c)/2.$

例: 確率計画

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

minimize $\ c^{T}x\$

subject to

$P(a_{i}^{T}(x)\geq b_{i})\geq p,\quad i=1,\dots ,m$

この式において$a_{i}$は平均${\bar {a}}_{i}$、共分散$\Sigma _{i}$の正規乱数を要素とするベクトルであり、$p\geq 0.5$である。この問題は次の二次錐計画問題と同値とみなすことができる。

minimize $\ c^{T}x\$

subject to

${\bar {a}}_{i}^{T}(x)+\Phi ^{-1}(1-p)\lVert \Sigma _{i}^{1/2}x\rVert _{2}\geq b_{i},\quad i=1,\dots ,m$

ただし$\Phi ^{-1}$は誤差関数の逆関数を表す。

二次錐計画問題のプログラム

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