凸最適化
凸最小化が難しい場合: 自己調和障壁
凸最適化問題にクラスによっては更新法の効率は悪いものがある。
それはクラスには多くの関数と劣勾配を評価しなければ
精確に最小値を得られない問題を含んでいるからである。
この問題はArkadi Nemirovskiiによって議論されている。
そのため実用上の効率を求めるには問題のクラスにさらに制約を加える必要がある。
2つの障壁関数法の方法がある。
1つはNesterovとNemirovskiiによる自己調和(self-concordant)障壁関数、
もう1つはTerlakyらによる自己正規障壁関数である。
準凸最小化
凸のレベル集合をもつ問題は理論上は効率的に最小化できる。
Yuri Nesterovは準凸最小化問題を効率的に解けることを証明した。
これの結果はKiwielによって拡張された。
計算複雑性の理論の中では、準凸計画問題と凸計画問題は問題の次元に対して
多項式時間で解くことが可能である。
Yuri Nesterovが最初に準凸最小化問題を効率的に解くことが可能であることを示した。
しかし、この理論的に効率的な方法は発散する数列をステップサイズに用いていた。
これは古典的な劣勾配法の開発に使われていた。
発散数列を用いる古典的な劣勾配法は、劣勾配射影法、勾配バンドル法、非平滑フィルタ法など
の現代的な凸最小化法よりかなり遅いことが知られている。
凸に近いが非凸の関数の問題は計算困難である。
Ivanovの結果によれば関数が滑らかさあっても単峰の関数を最小化することは難しい。
拡張
正無限を含むように凸関数を拡張できる。たとえば、指標関数はを満たす領域ではをもち、その他は正無限である。
凸関数の拡張には擬似凸関数と準凸関数を含む。
凸解析と更新法の部分的な拡張は
非凸最小化問題に対する近似解法として一般化された凸性の中で考えられている。