凸最適化

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

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

$f:{\mathcal {X}}\to \mathbb {R}$

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

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

すなわち$x^{\ast }$は

$f(x^{\ast })\leq f(x)$ for all $x\in {\mathcal {X}}$.

である。

凸最適化問題

${\mathcal {X}}$上の$x^{\ast }$ を見つける最適化問題である。

$f(x^{\ast })=\min\{f(x):x\in {\mathcal {X}}\},$

ここで${\mathcal {X}}\subset \mathbb {R} ^{n}$は実現可能集合で、 $f(x):\mathbb {R} ^{n}\rightarrow \mathbb {R}$は目的関数である。 ${\mathcal {X}}$が閉凸集合で、 $\mathbb {R} ^{n}$上で$f(x)$が凸関数であれば、これを凸最適化問題という。

以上は数学的に一般化された定義であるが、この問題が実際に提示される場面において${\mathcal {X}}\subseteq \mathbb {R^{2}}$は具体的な形で表現されることが多い。よくある例として、与えられた凸関数$g_{i}(x):i=1,\dots ,m$を用いて以下のように連立不等式をみたす集合として定義される：

${\mathcal {X}}:=\{x\in \mathbb {R^{n}} :g_{i}(x)\leq 0,i=1,\dots ,m\}$

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

${\begin{aligned}&\operatorname {minimize} &&f(x)\\&\operatorname {subject\;to} &&g_{i}(x)\leq 0,\quad i=1,\dots ,m\end{aligned}}$

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

理論

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

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

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

標準形

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

3つの部分で成り立つ。

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

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

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

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

例

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

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

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

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

${\mathcal {X}}=\left\lbrace {x\in X\vert g_{1}(x)\leq 0,\ldots ,g_{m}(x)\leq 0}\right\rbrace .$

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

L(x,λ₀,...,λ_m) = λ₀f(x) + λ₁g₁(x) + ... + λ_mg_m(x).

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

1. X上のすべての変数に関してxはL(y, λ₀, λ₁, ..., λ_m) を最小化する
2. λ₀ ≥ 0, λ₁ ≥ 0, ..., λ_m ≥ 0, 少なくともひとつは λ_k>0,
3. λ₁g₁(x) = 0, ..., λ_mg_m(x) = 0 (相補スラック性).

方法

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

• 内点法
• バンドル法
• 射影劣勾配法

その他の手法

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

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

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

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

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

準凸最小化

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

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

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

拡張

正無限を含むように凸関数を拡張できる。たとえば、指標関数は$x\in {\mathcal {X}}$を満たす領域では$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