円錐最適化

円錐最適化は、凸最適化のサブフィールドであり、アフィン部分空間と凸円錐の交差上の凸関数を最小化する問題を研究します。

円錐最適化問題のクラスには、線形計画法と半正定値計画法など、最もよく知られている凸最適化問題のクラスがいくつか含まれています。

意味

実ベクトル空間Xが与えられたとき、凸実数値関数

${\displaystyle f:C\to \mathbb {R} }$

凸錐 上に定義される、および一連のアフィン制約によって定義されるアフィン部分空間において、円錐最適化問題は、数が最小となる内の点を見つけることです。 ${\displaystyle C\subset X}$ ${\displaystyle {\mathcal {H}}}$ ${\displaystyle h_{i}(x)=0\ }$ ${\displaystyle x}$ ${\displaystyle C\cap {\mathcal {H}}}$ ${\displaystyle f(x)}$

の例としては、正の直交行列、半正定値行列、2次錐などが挙げられます。 は多くの場合線形関数であり、その場合、錐最適化問題はそれぞれ線形計画問題、半正定値計画問題、2次錐計画問題に帰着します。 ${\displaystyle C}$ ${\displaystyle \mathbb {R} _{+}^{n}=\left\{x\in \mathbb {R} ^{n}:\,x\geq \mathbf {0} \right\}}$ ${\displaystyle \mathbb {S} _{+}^{n}}$ ${\displaystyle \left\{(x,t)\in \mathbb {R} ^{n}\times \mathbb {R} :\lVert x\rVert \leq t\right\}}$ ${\displaystyle f\}$

二重性

円錐最適化問題の特定の特殊なケースには、その双対問題の注目すべき閉じた形式の表現があります。

コニックLP

双対線形計画法の双対

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

対象となる${\displaystyle Ax=b,x\in C\ }$

は

最大化する${\displaystyle b^{T}y\ }$

対象となる${\displaystyle A^{T}y+s=c,s\in C^{*}\ }$

ここで はの双対円錐を表します。 ${\displaystyle C^{*}}$ ${\displaystyle C\}$

円錐線形計画法では弱い双対性が成り立つが、強い双対性は必ずしも成り立たない。^{[ 1 ]}

半正定値プログラム

不等式形式の半正定値計画の双対

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

対象となる${\displaystyle x_{1}F_{1}+\cdots +x_{n}F_{n}+G\leq 0}$

は次のように与えられる。

最大化する${\displaystyle \mathrm {tr} \ (GZ)\ }$

対象となる${\displaystyle \mathrm {tr} \ (F_{i}Z)+c_{i}=0,\quad i=1,\dots ,n}$

${\displaystyle Z\geq 0}$

参考文献

1. 「双対計画法における双対性」（PDF）。

外部リンク

• Boyd, Stephen P.; Vandenberghe, Lieven (2004).凸最適化(PDF) . Cambridge University Press. ISBN 978-0-521-83378-3. 2011年10月15日閲覧。
• 円錐最適化問題を解決できるMOSEKソフトウェア。