二次錐計画問題#
読み: にじすいけいかくもんだい
英名: Second Order Cone Programming Problem
別名: SOCP
二次錐計画問題は凸計画問題の一種であり,主双対内点法による解法が知られている.なお,英語の頭文字から SOCP(問題)と呼ぶことがある.
二次錐計画問題を式で表すと次のようになる.ただし,\(A \in \mathbb{R}^{m \times n}, \ b \in \mathbb{R}^m, \ c \in \mathbb{R}^n\) は定数,\(x \in \mathbb{R}^n\) は変数,\(\kappa\) は二次錐(の直積)を表している.
(91)#\[\begin{split}\begin{array}{ll}
\min & c^\top x \\
\mathrm{s.t.} & Ax = b \\
& x \in \kappa
\end{array}\end{split}\]
線形計画問題や凸二次制約付き凸二次計画問題など様々な種類の問題が二次錐計画問題として定式化することが可能であることが知られている.
関連