準凸最小化
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2019/08/28 14:27 UTC 版)
凸のレベル集合をもつ問題は理論上は効率的に最小化できる。Yuri Nesterovは準凸最小化問題を効率的に解けることを証明した。これの結果はKiwielによって拡張された。 計算複雑性の理論の中では、準凸計画問題と凸計画問題は問題の次元に対して多項式時間で解くことが可能である。Yuri Nesterovが最初に準凸最小化問題を効率的に解くことが可能であることを示した。しかし、この理論的に効率的な方法は発散する数列をステップサイズに用いていた。これは古典的な劣勾配法の開発に使われていた。発散数列を用いる古典的な劣勾配法は、劣勾配射影法、勾配バンドル法、非平滑フィルタ法などの現代的な凸最小化法よりかなり遅いことが知られている。 凸に近いが非凸の関数の問題は計算困難である。Ivanovの結果によれば関数が滑らかさあっても単峰の関数を最小化することは難しい。
※この「準凸最小化」の解説は、「凸最適化」の解説の一部です。
「準凸最小化」を含む「凸最適化」の記事については、「凸最適化」の概要を参照ください。
ウィキペディア小見出し辞書の「準凸最小化」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。 お問い合わせ。
- 準凸最小化のページへのリンク
