凸最適化

凸最適化（とつさいてきか）とは最適化問題の分野のひとつで、凸集合上の凸関数の最小化問題である。
凸最小化問題は一般的な最適化問題よりも簡単に最適化が可能であり、局所的な最小値が大域的な最小値と一致する性質をもつ。

実ベクトル空間上の実数値凸関数

がの凸部分集合上で定義される。

凸最適化問題とはの最小値となる上の点
を見つけることである。

すなわちは
 for all .
である。

凸最適化問題
上の を見つける最適化問題である。

ここでは実現可能集合で、
は目的関数である。
が閉凸集合で、
上でが凸関数であれば、これを凸最適化問題という。

以上は数学的に一般化された定義であるが、この問題が実際に提示される場面においては具体的な形で表現されることが多い。よくある例として、与えられた凸関数を用いて以下のように連立不等式をみたす集合として定義される：

こういった事情を踏まえて以下のような定義が与えられることもある：
 
ここで、関数は凸である。

理論
凸最適化問題において以下の命題は真である。
 極小値が存在すれば大域的最小値である
 すべての（大域的）最小値の集合は凸である
 強凸関数であり関数が最小値を持てば、一意に決まる

ヒルベルト射影理論、分離超平面理論、Farkasの補題などの関数解析（ヒルベルト空間上の）とも関係している。

標準形
標準形は凸最小化問題をよく使用される直感的な形式で表現する。

3つの部分で成り立つ。

 凸関数 　に関して最小化される。
 不等式制約 。ここで関数は凸である。
 等式制約 　関数はアフィン変換、すなわち線形関数。 
実際には線形制約とアフィンな制約はよく使用される。
これらの形式はと表せられる。
ここで、は列ベクトル、は実数である。

凸最小化問題は以下のように表される

 

等式制約は2つの
不等式制約と を用いて置き換えることができる。
そのため等式制約は理論的には冗長であるが実際上の利点のため使用される。
これらのことから、なぜ
が単に凸であるのではなくアフィンであるのかが容易に理解できる。
を凸とするとは凸であるが
は凹となる。
そのためが凸となるための条件が
がアフィンであることである。

例
以下で示す例はすべて凸最小化問題であるか、変数変換により凸最小化問題にできる問題である。

最小二乗法
線形計画問題
線形制約化 凸 2次計画 
2次制約下2次計画問題
錐線形計画問題
幾何計画問題
二次錐計画問題
半正定値計画問題
エントロピー最大化

ラグランジュの未定乗数法
 
標準形に表された凸最小化問題を考える。
コスト関数を、
不等式制約を
とすると、定義域は

この問題に対するラグランジュ関数は
L(x,λ0,...,λm) = λ0f(x) + λ1g1(x)  + ... + λmgm(x).

X上の関数fを最小化するX上の点xに関して
実数値のラグランジュ係数λ0, ..., λmが存在し、
以下を満たす。
 X上のすべての変数に関してxはL(y, λ0, λ1, ..., λm) を最小化する
 λ0 ≥ 0, λ1 ≥ 0, ..., λm ≥ 0, 少なくともひとつは λk>0,
 λ1g1(x) = 0, ..., λmgm(x) = 0 (相補スラック性).

方法
凸最小化問題は以下の方法を用いて解くことが可能である。
 内点法
 バンドル法
 射影劣勾配法

その他の手法
切断平面法
楕円体法
劣勾配法
ドリフトプラスペナルティー法

劣勾配法は簡単に実装でき多くの適応例がある。
双対劣勾配法は劣勾配法を双対問題に適応した方法である。
ドリフトプラスペナルティー法は双対劣勾配法と類似しているが、
主変数に関して時間平均をとっている点が異なる。

凸最小化が難しい場合: 自己調和障壁

凸最適化問題にクラスによっては更新法の効率は悪いものがある。
それはクラスには多くの関数と劣勾配を評価しなければ
精確に最小値を得られない問題を含んでいるからである。
この問題はArkadi Nemirovskiiによって議論されている。

そのため実用上の効率を求めるには問題のクラスにさらに制約を加える必要がある。
2つの障壁関数法の方法がある。
1つはNesterovとNemirovskiiによる自己調和(self-concordant)障壁関数、
もう1つはTerlakyらによる自己正規障壁関数である。

準凸最小化
凸のレベル集合をもつ問題は理論上は効率的に最小化できる。
Yuri Nesterovは準凸最小化問題を効率的に解けることを証明した。
これの結果はKiwielによって拡張された。

計算複雑性の理論の中では、準凸計画問題と凸計画問題は問題の次元に対して
多項式時間で解くことが可能である。
Yuri Nesterovが最初に準凸最小化問題を効率的に解くことが可能であることを示した。
しかし、この理論的に効率的な方法は発散する数列をステップサイズに用いていた。
これは古典的な劣勾配法の開発に使われていた。
発散数列を用いる古典的な劣勾配法は、劣勾配射影法、勾配バンドル法、非平滑フィルタ法など
の現代的な凸最小化法よりかなり遅いことが知られている。

凸に近いが非凸の関数の問題は計算困難である。
Ivanovの結果によれば関数が滑らかさあっても単峰の関数を最小化することは難しい。

拡張
正無限を含むように凸関数を拡張できる。たとえば、指標関数はを満たす領域ではをもち、その他は正無限である。

凸関数の拡張には擬似凸関数と準凸関数を含む。
凸解析と更新法の部分的な拡張は
非凸最小化問題に対する近似解法として一般化された凸性の中で考えられている。

脚注
 
 
 Borwein, Jonathan, and Lewis, Adrian. (2000). Convex Analysis and Nonlinear Optimization. Springer.
 Hiriart-Urruty, Jean-Baptiste, and Lemaréchal, Claude. (2004). Fundamentals of Convex analysis. Berlin: Springer.
 

 
 
 Nesterov, Y. and Nemirovsky, A. (1994). 'Interior Point Polynomial Methods in Convex Programming. SIAM
 Nesterov, Yurii. (2004). Introductory Lectures on Convex Optimization'',  Kluwer Academic Publishers

関連項目

 最適化問題
 双対問題
 凸解析
 スレーターの条件
 ホアン・トゥイ (数学者)、凸最適化の研究者

外部リンク
 Stephen Boyd and Lieven Vandenberghe, Convex optimization  (book in pdf)
 EE364a: Convex Optimization I and EE364b: Convex Optimization II, Stanford course homepages
6.253: Convex Analysis and Optimization, an MIT OCW course homepage
 Brian Borchers, An overview of software for convex optimization

数学に関する記事
関数
最適化