凸最適化

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

実ベクトル空間 X {\displaystyle X} 上の実数値凸関数

f : X → R {\displaystyle f:{\mathcal {X}}\to \mathbb {R} }

が X {\displaystyle X} の凸部分集合 X {\displaystyle {\mathcal {X}}} 上で定義される。

凸最適化問題とは f ( x ) {\displaystyle f(x)} の最小値となる X {\displaystyle {\mathcal {X}}} 上の点 x ∗ {\displaystyle x^{\ast }} を見つけることである。

すなわち x ∗ {\displaystyle x^{\ast }} は

f ( x ∗ ) ≤ f ( x ) {\displaystyle f(x^{\ast })\leq f(x)} for all x ∈ X {\displaystyle x\in {\mathcal {X}}} .

である。

凸最適化問題

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}} } は具体的な形で表現されることが多い。よくある例として、与えられた凸関数 g i ( x ) : i = 1 , … , m {\displaystyle g_{i}(x):i=1,\dots ,m} を用いて以下のように連立不等式をみたす集合として定義される：

X := { x ∈ R n : g i ( x ) ≤ 0 , i = 1 , … , m } {\displaystyle {\mathcal {X}}:=\{x\in \mathbb {R^{n}} :g_{i}(x)\leq 0,i=1,\dots ,m\}}

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

minimize f ( x ) s u b j e c t t o g i ( x ) ≤ 0 , i = 1 , … , m {\displaystyle {\begin{aligned}&\operatorname {minimize} &&f(x)\\&\operatorname {subject\;to} &&g_{i}(x)\leq 0,\quad i=1,\dots ,m\end{aligned}}}

ここで、関数 f , g 1 … g m : R n → R {\displaystyle f,g_{1}\ldots g_{m}:\mathbb {R} ^{n}\rightarrow \mathbb {R} } は凸である。

理論

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

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

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

標準形

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

3つの部分で成り立つ。

  • 凸関数 f ( x ) : R n → R {\displaystyle f(x):\mathbb {R} ^{n}\to \mathbb {R} } 　 x {\displaystyle x} に関して最小化される。
  • 不等式制約 g i ( x ) ≤ 0 {\displaystyle g_{i}(x)\leq 0} 。ここで関数 g i {\displaystyle g_{i}} は凸である。
  • 等式制約 h j ( x ) = 0 {\displaystyle h_{j}(x)=0} 　関数 h j {\displaystyle h_{j}} はアフィン変換、すなわち線形関数。

実際には線形制約とアフィンな制約はよく使用される。 これらの形式は h j ( x ) = a j T x + b j {\displaystyle h_{j}(x)=a_{j}^{T}x+b_{j}} と表せられる。 ここで、 a j {\displaystyle a_{j}} は列ベクトル、 b j {\displaystyle b_{j}} は実数である。

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

minimize x f ( x ) s u b j e c t t o g i ( x ) ≤ 0 , i = 1 , … , m h j ( x ) = 0 , j = 1 , … , p . {\displaystyle {\begin{aligned}&{\underset {x}{\operatorname {minimize} }}&&f(x)\\&\operatorname {subject\;to} &&g_{i}(x)\leq 0,\quad i=1,\dots ,m\\&&&h_{j}(x)=0,\quad j=1,\dots ,p.\end{aligned}}}

等式制約 h ( x ) = 0 {\displaystyle h(x)=0} は2つの 不等式制約 h ( x ) ≤ 0 {\displaystyle h(x)\leq 0} と − h ( x ) ≤ 0 {\displaystyle -h(x)\leq 0} を用いて置き換えることができる。 そのため等式制約は理論的には冗長であるが実際上の利点のため使用される。 これらのことから、なぜ h j ( x ) = 0 {\displaystyle h_{j}(x)=0} が単に凸であるのではなくアフィンであるのかが容易に理解できる。 h j ( x ) {\displaystyle h_{j}(x)} を凸とすると h j ( x ) ≤ 0 {\displaystyle h_{j}(x)\leq 0} は凸であるが − h j ( x ) ≤ 0 {\displaystyle -h_{j}(x)\leq 0} は凹となる。 そのため h j ( x ) = 0 {\displaystyle h_{j}(x)=0} が凸となるための条件が h j ( x ) {\displaystyle h_{j}(x)} がアフィンであることである。

例

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

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

標準形に表された凸最小化問題を考える。 コスト関数を f ( x ) {\displaystyle f(x)} 、 不等式制約を g i ( x ) ≤ 0 ( i = 1 … m ) {\displaystyle g_{i}(x)\leq 0(i=1\ldots m)} とすると、定義域 X {\displaystyle {\mathcal {X}}} は

X = { x ∈ X | g 1 ( x ) ≤ 0 , … , g m ( x ) ≤ 0 } . {\displaystyle {\mathcal {X}}=\left\lbrace {x\in X\vert g_{1}(x)\leq 0,\ldots ,g_{m}(x)\leq 0}\right\rbrace .}

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

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

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

  1. X上のすべての変数に関してxはL(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の結果によれば関数が滑らかさあっても単峰の関数を最小化することは難しい。

拡張

正無限を含むように凸関数を拡張できる。たとえば、指標関数は x ∈ X {\displaystyle x\in {\mathcal {X}}} を満たす領域では 0 {\displaystyle 0} をもち、その他は正無限である。

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

脚注

  • 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 

関連項目

外部リンク

  • 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
  • 表
  • 話
  • 編
  • 歴
非線形(無制約)
… 関数　
勾配法
収束性
準ニュートン法
その他の求解法
… ヘッセ行列
  • 最適化におけるニュートン法（英語版）
The graph of a strictly concave quadratic function is shown in blue, with its unique maximum shown as a red dot. Below the graph appears the contours of the function: The level sets are nested ellipses.
Optimization computes maxima and minima.
非線形(制約付き)
一般
微分可能
凸最適化
凸縮小化
  • 切除平面法（英語版、デンマーク語版、ドイツ語版、スペイン語版）
  • 簡約勾配法
  • 劣勾配法（英語版）
線型 および
二次
内点法
ベイズ-交換
  • 単体法
  • 改訂シンプレックス法（英語版）
  • 十字法（英語版）
  • レムケの主ピボット操作法（英語版）
組合せ最適化
系列範例
(Paradigms)
グラフ理論
最小全域木
最大フロー問題
メタヒューリスティクス
  • カテゴリ（最適化 • アルゴリズム） • ソフトウェア（英語版）