凸最適化

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

実ベクトル空間 $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)$ がアフィンであることである。

例

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

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

標準形に表された凸最小化問題を考える。コスト関数を $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が存在し、以下を満たす。

X上のすべての変数に関してxはL(y, λ₀, λ₁, ..., λ_m) を最小化する
λ₀ ≥ 0, λ₁ ≥ 0, ..., λ_m ≥ 0, 少なくともひとつは λ_k>0,
λ₁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 October 15, 2011閲覧。
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