二次錐計画問題
次の二次不等式制約を考える。
x T A T A x + b T x + c ≤ 0. {\displaystyle x^{T}A^{T}Ax+b^{T}x+c\leq 0.}
この不等式は次のように変形することで錐形の実行可能領域を表す二次錐制約とみなすことができる。
‖ ( 1 + b T x + c ) / 2 A x ‖ 2 ≤ ( 1 − b T x − c ) / 2. {\displaystyle \left\|{\begin{matrix}(1+b^{T}x+c)/2\\Ax\end{matrix}}\right\|_{2}\leq (1-b^{T}x-c)/2.}
[ A c T ] x + [ b d ] ∈ C 0 {\displaystyle {\begin{bmatrix}A\\c^{T}\end{bmatrix}}x+{\begin{bmatrix}b\\d\end{bmatrix}}\in {\mathcal {C}}_{0}}
と同値な条件であり、錐体を表す集合であることがわかる。この一般的な錐体の定義により、上のような二次錐計画問題が定義される。
二次錐計画問題には一般的な主双対内点法による解法以外にもバリア関数法などの解法が用いられる。バリア関数法では、上記の凸最適化問題を
minimize f T x − log  ( − ( F x − g ) ) − ∑ i = 1 m log  ( 1 2 ( ‖ A i x + b i ‖ 2 2 − ( c i T x + d i ) 2 ) ) {\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)}
という形に書き換え、これをニュートン法などにより最小化することで各繰り返しにおけるステップ幅 Δ x {\displaystyle \Delta x} を求める。