凸最適化
X {\displaystyle {\mathcal {X}}} 上の x ∗ {\displaystyle x^{\ast }} を見つける最適化問題である。
f ( x ∗ ) = min { f ( x ) : x ∈ X } , {\displaystyle f(x^{\ast })=\min\{f(x):x\in {\mathcal {X}}\},}
ここで X ⊂ R n {\displaystyle {\mathcal {X}}\subset \mathbb {R} ^{n}} は実現可能集合で、 f ( x ) : R n → R {\displaystyle f(x):\mathbb {R} ^{n}\rightarrow \mathbb {R} } は目的関数である。 X {\displaystyle {\mathcal {X}}} が閉凸集合で、 R n {\displaystyle \mathbb {R} ^{n}} 上で f ( x ) {\displaystyle f(x)} が凸関数であれば、これを凸最適化問題という。
以上は数学的に一般化された定義であるが、この問題が実際に提示される場面において X ⊆ R 2 {\displaystyle {\mathcal {X}}\subseteq \mathbb {R^{2}} } は具体的な形で表現されることが多い。
凸のレベル集合をもつ問題は理論上は効率的に最小化できる。 Yuri Nesterovは準凸最小化問題を効率的に解けることを証明した。 これの結果はKiwielによって拡張された。
計算複雑性の理論の中では、準凸計画問題と凸計画問題は問題の次元に対して 多項式時間で解くことが可能である。 Yuri Nesterovが最初に準凸最小化問題を効率的に解くことが可能であることを示した。 しかし、この理論的に効率的な方法は発散する数列をステップサイズに用いていた。 これは古典的な劣勾配法の開発に使われていた。 発散数列を用いる古典的な劣勾配法は、劣勾配射影法、勾配バンドル法、非平滑フィルタ法など の現代的な凸最小化法よりかなり遅いことが知られている。
凸に近いが非凸の関数の問題は計算困難である。 Ivanovの結果によれば関数が滑らかさあっても単峰の関数を最小化することは難しい。