2次錐体計画法

2次錐計画（SOCP）は、次の形式の 凸最適化問題である。

最小化する${\displaystyle \f^{T}x\}$

対象となる

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

${\displaystyle Fx=g\}$

ここで、問題のパラメータは、、およびです。は最適化変数です。 はユークリッドノルムであり、転置を示します。^[1] SOCP の「2 次円錐」は、制約から生じます。これは、アフィン関数がの 2 次円錐内にあることを要求するのと同等です。^[1]${\displaystyle 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}}$${\displaystyle g\in \mathbb {R} ^{p}}$${\displaystyle x\in \mathbb {R} ^{n}}$${\displaystyle \lVert x\rVert _{2}}$${\displaystyle ^{T}}$${\displaystyle (Ax+b,c^{T}x+d)}$${\displaystyle \mathbb {R} ^{n_{i}+1}}$

SOCPは内点法^[2]で解くことができ、一般に半正定値計画法（SDP）問題よりも効率的に解くことができます。^[3] SOCPの工学的応用には、フィルタ設計、アンテナアレイの重量設計、トラス設計、ロボット工学における把持力の最適化などがあります。^[4]定量的金融における応用にはポートフォリオ最適化があります。市場インパクト制約の中には線形ではないため2次計画法では解けないものもありますが、SOCP問題として定式化できます。^{[5] [6] [7]}

標準または単位2次円錐は次のように定義されます。 ${\displaystyle n+1}$

${\displaystyle {\mathcal {C}}_{n+1}=\left\{{\begin{bmatrix}x\t\end{bmatrix}}{\Bigg |}x\in \mathbb {R} ^{n},t\in \mathbb {R} ,\|x\|_{2}\leq t\right\}}$。

2 次円錐は、2 次円錐、アイスクリーム円錐、ローレンツ円錐とも呼ばれます。 における標準的な 2 次円錐は です。 ${\displaystyle \mathbb {R} ^{3}}$${\displaystyle \left\{(x,y,z){\Big |}{\sqrt {x^{2}+y^{2}}}\leq z\right\}}$

2 次円錐制約を満たす点の集合は、アフィン写像の下での単位 2 次円錐の逆像です。

${\displaystyle \lVert A_{i}x+b_{i}\rVert _{2}\leq c_{i}^{T}x+d_{i}\Leftrightarrow {\begin{bmatrix}A_{i}\\c_{i}^{T}\end{bmatrix}}x+{\begin{bmatrix}b_{i}\\d_{i}\end{bmatrix}}\in {\mathcal {C}}_{n_{i}+1}}$

したがって凸状です。

2次の錐は半正定値行列の錐に埋め込むことができる。

${\displaystyle ||x||\leq t\Leftrightarrow {\begin{bmatrix}tI&x\\x^{T}&t\end{bmatrix}}\succcurlyeq 0,}$

つまり、2次の円錐制約は線形行列不等式と同等です（ここで は半正定値行列を意味します）。同様に、 ${\displaystyle M\succcurlyeq 0}$${\displaystyle M}$

${\displaystyle \lVert A_{i}x+b_{i}\rVert _{2}\leq c_{i}^{T}x+d_{i}\Leftrightarrow {\begin{bmatrix}(c_{i}^{T}x+d_{i})I&A_{i}x+b_{i}\\(A_{i}x+b_{i})^{T}&c_{i}^{T}x+d_{i}\end{bmatrix}}\succcurlyeq 0}$。

の場合、SOCP は線形計画に簡約されます。の場合、SOCP は凸二次制約線形計画 に等しくなります。 ${\displaystyle A_{i}=0}$${\displaystyle i=1,\dots ,m}$${\displaystyle c_{i}=0}$${\displaystyle i=1,\dots ,m}$

凸二次制約二次計画法も、目的関数を制約として再定式化することで SOCP として定式化できます。^[4] 半正定値計画法はSOCP を包含します。SOCP 制約は線形行列不等式(LMI)として記述でき、半正定値計画法のインスタンスとして再定式化できるためです。^[4]ただし、その逆は有効ではありません。つまり、2 次錐表現を許容しない正半正定値錐が存在します。^[3]実際、平面上の任意の閉じた凸半代数集合はSOCP の実行可能領域として記述できますが、 ^[8] SDP で表現できない凸半代数集合、つまり SDP の実行可能領域として記述できない凸半代数集合が存在することが知られています。^[9]

次の ような凸二次制約を考える。

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

これはSOCP制約と同等である。

${\displaystyle \lVert A^{1/2}x+{\frac {1}{2}}A^{-1/2}b\rVert \leq \left({\frac {1}{4}}b^{T}A^{-1}bc\right)^{\frac {1}{2}}}$

不等式形式の 確率線形計画法を考える

最小化する${\displaystyle \c^{T}x\}$

対象となる

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

ここで、パラメータは平均と共分散を持つ独立したガウス乱数ベクトルであり、この問題はSOCPとして表現できる。 ${\displaystyle a_{i}\ }$${\displaystyle {\bar {a}}_{i}}$${\displaystyle \Sigma _{i}\ }$${\displaystyle p\geq 0.5}$

最小化する${\displaystyle \ c^{T}x\ }$

対象となる

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

ここで、逆正規累積分布関数である。^[1]${\displaystyle \Phi ^{-1}(\cdot )\ }$

2次錐プログラムは、定義するデータが決定論的であるため、決定論的2次錐プログラムと呼ばれます。確率的2次錐プログラムは、決定論的2次錐プログラムを定義するデータの不確実性を処理するために定義された最適化問題の一種です。^[10]

その他のモデリング例はMOSEKモデリングクックブックで参照できます。^[11]

• べき乗円錐は2次円錐を2以外のべき乗に一般化したものである。^[14]