二次錐計画問題

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

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

より一般的な形として

${\displaystyle {\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} }$

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

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

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

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

minimize ${\displaystyle 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)}$

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

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

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

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

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