凸最適化

最適化問題の分野のひとつで、凸集合上の凸関数の最小化問題

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

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

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

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

すなわち

for all .

である。

凸最適化問題編集

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

 

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


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

 

こういった事情を踏まえて以下のような定義が与えられることもある:

 

ここで、関数 は凸である。

理論編集

凸最適化問題において以下の命題は真である。

  • 極小値が存在すれば大域的最小値である
  • すべての(大域的)最小値の集合は凸である
  • 強凸関数であり関数が最小値を持てば、一意に決まる

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

標準形編集

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

3つの部分で成り立つ。

  • 凸関数    に関して最小化される。
  • 不等式制約  。ここで関数 は凸である。
  • 等式制約   関数 アフィン変換、すなわち線形関数。

実際には線形制約とアフィンな制約はよく使用される。 これらの形式は と表せられる。 ここで、 は列ベクトル、 は実数である。

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

 

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

編集

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

ラグランジュの未定乗数法編集

標準形に表された凸最小化問題を考える。 コスト関数を 、 不等式制約を  とすると、定義域 

 

この問題に対するラグランジュ関数

L(x,λ0,...,λm) = λ0f(x) + λ1g1(x) + ... + λmgm(x).

X上の関数fを最小化するX上の点xに関して 実数値のラグランジュ係数λ0, ..., λmが存在し、 以下を満たす。

  1. X上のすべての変数に関してxL(y, λ0, λ1, ..., λm) を最小化する
  2. λ0 ≥ 0, λ1 ≥ 0, ..., λm ≥ 0, 少なくともひとつは λk>0,
  3. λ1g1(x) = 0, ..., λmgm(x) = 0 (相補スラック性).

方法編集

凸最小化問題は以下の方法を用いて解くことが可能である。

その他の手法

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

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

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

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

準凸最小化編集

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

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

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

拡張編集

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

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

脚注編集

  • Bertsekas, Dimitri (2003). Convex Analysis and Optimization. Athena Scientific. 
  • Boyd, Stephen P.; Vandenberghe, Lieven (2004) (pdf). Convex Optimization. Cambridge University Press. ISBN 978-0-521-83378-3. http://www.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf 2011年10月15日閲覧。. 
  • 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.
  • Hiriart-Urruty, Jean-Baptiste; Lemaréchal, Claude (1993). Convex analysis and minimization algorithms, Volume I: Fundamentals. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]. 305. Berlin: Springer-Verlag. pp. xviii+417. ISBN 3-540-56850-6. 
  • Hiriart-Urruty, Jean-Baptiste; Lemaréchal, Claude (1993). Convex analysis and minimization algorithms, Volume II: Advanced theory and bundle methods. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]. 306. Berlin: Springer-Verlag. pp. xviii+346. ISBN 3-540-56852-2. MR1295240. 
  • Kiwiel, Krzysztof C. (1985). Methods of Descent for Nondifferentiable Optimization. Lecture Notes in Mathematics. New York: Springer-Verlag. ISBN 978-3540156420. 
  • Lemaréchal, Claude (2001). “Lagrangian relaxation”. In Michael Jünger and Denis Naddef. Computational combinatorial optimization: Papers from the Spring School held in Schloß Dagstuhl, May 15–19, 2000. Lecture Notes in Computer Science. 2241. Berlin: Springer-Verlag. pp. 112–156. doi:10.1007/3-540-45586-8_4. ISBN 3-540-42877-1. MR1900016. 
  • 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
  • Rockafellar, R. T. (1970). Convex analysis. Princeton: Princeton University Press. 
  • Ruszczyński, Andrzej (2006). Nonlinear Optimization. Princeton University Press. 

関連項目編集

外部リンク編集