円錐最適化

Subfield of convex optimization

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

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

定義

実 ベクトル空間 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\ }$

双対性

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

円錐線形計画法

円錐線形計画法の双対

最小化する ${\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-32011年10月15日閲覧
• 円錐最適化問題を解決できるMOSEKソフトウェア。

Retrieved from "https://en.wikipedia.org/w/index.php?title=Conic_optimization&oldid=1279358032"