2次錐計画

出典: ORWiki

【にじすいけいかく (second-order cone programming)】

等質自己双対錐上の線形計画問題の1つ. $n+1\,$ 次元空間の2次錐は
$K(n+1)=\left\{ x \in {\mathbf R}^{n+1} : x_0 \geq \sqrt{\sum_{i=1}^n x_i^2} \right\} \,$
で定義される. 2次錐 $K(n+1)\,$ に対して, $-\log(x^2_0 - \sum_{i=1}^n x_i^2)\,$ が $2\,$ --自己整合障壁関数になることが知られている.2次錐計画は
$\mathop{min.}_x \sum_{i=1}^N (c^i)^T x^i \,$ $s.t.\,$ $\sum_{i=1}^N A_i x^i = b, x^i \in K(n_i) \,$

で表される. ここで $A_i\in {\mathbf R}^{m\times n_i}\,$ , $b\in {\mathbf R}^m\,$ , $c^i \in {\mathbf R}^{n_i}\,$ , $i=1,\ldots,N\,$ である.