凸最適化
凸最小化問題は以下の方法を用いて解くことが可能である。
内点法
バンドル法
射影劣勾配法
その他の手法
切断平面法
楕円体法
劣勾配法
ドリフトプラスペナルティー法
劣勾配法は簡単に実装でき多くの適応例がある。 双対劣勾配法は劣勾配法を双対問題に適応した方法である。 ドリフトプラスペナルティー法は双対劣勾配法と類似しているが、 主変数に関して時間平均をとっている点が異なる。
標準形は凸最小化問題をよく使用される直感的な形式で表現する。
3つの部分で成り立つ。
凸関数 f ( x ) : R n → R {\displaystyle f(x):\mathbb {R} ^{n}\to \mathbb {R} } x {\displaystyle x} に関して最小化される。
不等式制約 g i ( x ) ≤ 0 {\displaystyle g_{i}(x)\leq 0} 。ここで関数 g i {\displaystyle g_{i}} は凸である。
等式制約 h j ( x ) = 0 {\displaystyle h_{j}(x)=0} 関数 h j {\displaystyle h_{j}} はアフィン変換、すなわち線形関数。
実際には線形制約とアフィンな制約はよく使用される。 これらの形式は h j ( x ) = a j T x + b j {\displaystyle h_{j}(x)=a_{j}^{T}x+b_{j}} と表せられる。 ここで、 a j {\displaystyle a_{j}} は列ベクトル、 b j {\displaystyle b_{j}} は実数である。
凸最小化問題は以下のように表される
minimize x f ( x ) s u b j e c t t o g i ( x ) ≤ 0 , i = 1 , ... , m h j ( x ) = 0 , j = 1 , ... , p .
凸最適化問題にクラスによっては更新法の効率は悪いものがある。 それはクラスには多くの関数と劣勾配を評価しなければ 精確に最小値を得られない問題を含んでいるからである。 この問題はArkadi Nemirovskiiによって議論されている。
そのため実用上の効率を求めるには問題のクラスにさらに制約を加える必要がある。 2つの障壁関数法の方法がある。 1つはNesterovとNemirovskiiによる自己調和(self-concordant)障壁関数、 もう1つはTerlakyらによる自己正規障壁関数である。