凸最適化

凸最適化（とつさいてきか）とは最適化問題の分野のひとつで、凸集合上の凸関数の最小化問題である。
凸最小化問題は一般的な最適化問題よりも簡単に最適化が可能であり、局所的な最小値が大域的な最小値と一致する性質をもつ。
実ベクトル空間formula_1上の実数値凸関数
がformula_1の凸部分集合formula_4上で定義される。
凸最適化問題とはformula_5の最小値となるformula_4上の点formula_7
を見つけることである。
すなわちformula_7は
である。
凸最適化問題.
formula_4上のformula_7 を見つける最適化問題である。
ここでformula_14は実現可能集合で、
formula_15は目的関数である。
formula_4が閉凸集合で、
formula_17上でformula_5が凸関数であれば、これを凸最適化問題という。
以上は数学的に一般化された定義であるが、この問題が実際に提示される場面においてformula_19は具体的な形で表現されることが多い。よくある例として、与えられた凸関数formula_20を用いて以下のように連立不等式をみたす集合として定義される：
formula_21
こういった事情を踏まえて以下のような定義が与えられることもある：
ここで、関数formula_23は凸である。
理論.
凸最適化問題において以下の命題は真である。
ヒルベルト射影理論、分離超平面理論、Farkasの補題などの関数解析（ヒルベルト空間上の）とも関係している。
標準形.
"標準形"は凸最小化問題をよく使用される直感的な形式で表現する。
3つの部分で成り立つ。
実際には線形制約とアフィンな制約はよく使用される。
これらの形式はformula_30と表せられる。
ここで、formula_31は列ベクトル、formula_32は実数である。
凸最小化問題は以下のように表される
等式制約formula_34は2つの
不等式制約formula_35とformula_36 を用いて置き換えることができる。
そのため等式制約は理論的には冗長であるが実際上の利点のため使用される。
これらのことから、なぜ
formula_28が単に凸であるのではなくアフィンであるのかが容易に理解できる。
formula_38を凸とするとformula_39は凸であるが
formula_40は凹となる。
そのためformula_28が凸となるための条件が
formula_38がアフィンであることである。
例.
以下で示す例はすべて凸最小化問題であるか、変数変換により凸最小化問題にできる問題である。
ラグランジュの未定乗数法.
標準形に表された凸最小化問題を考える。
コスト関数をformula_5、
不等式制約をformula_44
とすると、定義域formula_4は
この問題に対するラグランジュ関数は
"X"上の関数"f"を最小化する"X"上の点"x"に関して
実数値のラグランジュ係数"λ"0, ..., "λ"mが存在し、
以下を満たす。
方法.
凸最小化問題は以下の方法を用いて解くことが可能である。
その他の手法
劣勾配法は簡単に実装でき多くの適応例がある。
双対劣勾配法は劣勾配法を双対問題に適応した方法である。
ドリフトプラスペナルティー法は双対劣勾配法と類似しているが、
主変数に関して時間平均をとっている点が異なる。
凸最小化が難しい場合: 自己調和障壁.
凸最適化問題にクラスによっては更新法の効率は悪いものがある。
それはクラスには多くの関数と劣勾配を評価しなければ
精確に最小値を得られない問題を含んでいるからである。
この問題はArkadi Nemirovskiiによって議論されている。
そのため実用上の効率を求めるには問題のクラスにさらに制約を加える必要がある。
2つの障壁関数法の方法がある。
1つはNesterovとNemirovskiiによる"自己調和"(self-concordant)障壁関数、
もう1つはTerlakyらによる"自己正規"障壁関数である。
準凸最小化.
凸のレベル集合をもつ問題は理論上は効率的に最小化できる。
Yuri Nesterovは準凸最小化問題を効率的に解けることを証明した。
これの結果はKiwielによって拡張された。
計算複雑性の理論の中では、準凸計画問題と凸計画問題は問題の次元に対して
多項式時間で解くことが可能である。
Yuri Nesterovが最初に準凸最小化問題を効率的に解くことが可能であることを示した。
しかし、この理論的に効率的な方法は発散する数列をステップサイズに用いていた。
これは古典的な劣勾配法の開発に使われていた。
発散数列を用いる古典的な劣勾配法は、劣勾配射影法、勾配バンドル法、非平滑フィルタ法など
の現代的な凸最小化法よりかなり遅いことが知られている。
凸に近いが非凸の関数の問題は計算困難である。
Ivanovの結果によれば関数が滑らかさあっても単峰の関数を最小化することは難しい。
拡張.
正無限を含むように凸関数を拡張できる。たとえば、指標関数はformula_47を満たす領域ではformula_48をもち、その他は正無限である。
凸関数の拡張には擬似凸関数と準凸関数を含む。
凸解析と更新法の部分的な拡張は
非凸最小化問題に対する近似解法として一般化された凸性の中で考えられている。