二次錐計画問題のソースを表示

'''二次錐計画問題'''（にじすいけいかくもんだい、{{Lang-en-short|Second-order cone programming}}、略称: SOCP）とは、次の形をした[[凸最適化]]問題を指す。
:minimize <math>\ f^T x \ </math> 
:subject to
::<math>\lVert A_i x + b_i \rVert_2 \leq c_i^T x + d_i,\quad i = 1,\dots,m</math>
::<math>Fx = g \ </math>
ただし、問題中に現れる<math>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}</math>、かつ <math>g \in \mathbb{R}^p</math> はパラメータ定数で、<math>x\in\mathbb{R}^n</math> が最適化変数である<ref name="boyd">{{cite book |last1=Boyd |first1=Stephen |last2=Vandenberghe |first2=Lieven |title=Convex Optimization |publisher=Cambridge University Press |year=2004 |isbn=978-0-521-83378-3 |url=http://www.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf |format=pdf |accessdate=2011-10-03}}</ref>。

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

== 概要 == 
二次錐計画問題は、名前の通り実行可能領域が二次錐であるような凸最適化問題を指す。もっとも単純な二次錐は ''n'' 次元空間上において次のような集合としてあらわされる。 
:<math> \mathcal{C}_0 := \left\{ x \in \mathbb{R}^{n} : \sqrt{\sum_{i=1}^{n-1} x_i^2} \leq x_n  \right\} .</math>
より一般的な形として
:<math> \mathcal{C} := \left\{ x \in \mathbb{R}^m : \|A x + 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}</math>
と表されることがあるが、これは
:<math> \begin{bmatrix} A \\ c^T \end{bmatrix} x + \begin{bmatrix} b \\ d \end{bmatrix} \in \mathcal{C}_0 </math>
と同値な条件であり、錐体を表す集合であることがわかる。この一般的な錐体の定義により、上のような二次錐計画問題が定義される。

二次錐計画問題には一般的な主双対内点法による解法以外にもバリア関数法などの解法が用いられる。バリア関数法では、上記の凸最適化問題を
: minimize <math> f^T x - \log \left(- (F x - 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) </math>
という形に書き換え、これをニュートン法などにより最小化することで各繰り返しにおけるステップ幅<math>\Delta x</math>を求める<ref name="boyd" />。

== 例: 二次制約の問題 ==
次の二次不等式制約を考える。
:<math> x^T A^T A x + b^T x + c \leq 0. </math>
この不等式は次のように変形することで錐形の実行可能領域を表す二次錐制約とみなすことができる。
:<math> \left\|
\begin{matrix}
(1 + b^T x +c)/2\\
Ax
\end{matrix} \right\|_2

\leq (1 - b^T x -c)/2.</math>

== 例: 確率計画 ==
確率的線形計画問題とは次のような不等式制約を含む線形核問題を指す。
:minimize <math>\ c^T x \ </math> 
:subject to
:: <math>P(a_i^T(x) \geq b_i) \geq p, \quad i = 1,\dots,m </math>
この式において<math>a_i</math>は平均<math>\bar{a}_i</math>、共分散<math>\Sigma_i</math>の正規乱数を要素とするベクトルであり、<math>p\geq 0.5</math>である。この問題は次の二次錐計画問題と同値とみなすことができる。
:minimize <math>\ c^T x \ </math> 
:subject to
:: <math>\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 </math>
ただし<math>\Phi^{-1}</math>は[[誤差関数]]の逆関数を表す<ref name="boyd"/>。

== 二次錐計画問題のプログラム ==
{| class="wikitable"
|-
!Name
!License
!Brief info
|-
|Xpress||商用|| バージョン7.6より
|-
|[[CPLEX]]||商用||
|-
|[[Gurobi]]||商用||並列のバリア関数アルゴリズム
|-
|[[JOptimizer]]||ASLライセンス|| [[Java]]による凸最適化のライブラリ(オープンソース)
|-
|[[MOSEK]]||商用||
|-
|[[OpenOpt]]||[[BSDライセンス]]|| 複数の言語に対応した最適化フレームワーク。詳しくは[http://openopt.org/SOCP SOCP] (英語) を参照のこと。内部ではPythonのライブラリである[[NumPy]]および[[SciPy]]を用いた疎行列計算が用いられている。
|}

== 脚注 ==
{{脚注ヘルプ}}
{{Reflist}}

{{主要な最適化問題の分類}}

{{デフォルトソート:にしすいけいかくもんたい}}
[[Category:最適化]]
[[Category:数学に関する記事]]