凸最適化

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

実ベクトル空間 ${\displaystyle X}$ 上の実数値凸関数 ${\displaystyle f:{\mathcal {X}}\to \mathbb {R} }$ が ${\displaystyle X}$ の凸部分集合 ${\displaystyle {\mathcal {X}}}$ 上で定義される。

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

すなわち、${\displaystyle x^{\ast }}$ は任意の ${\displaystyle x\in {\mathcal {X}}}$ に対して ${\displaystyle f(x^{\ast })\leq f(x)}$ を満たす。

凸最適化問題

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

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

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

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

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

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

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

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

理論

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

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

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

標準形

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

3つの部分で成り立つ。

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

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

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

${\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}}}$

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

例

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

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

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

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

${\displaystyle {\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).

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

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

方法

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

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

その他の手法

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

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

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

凸最適化問題のクラスによっては更新法の効率は悪いものがある。それはクラスには多くの関数と劣勾配を評価しなければ、精確に最小値を得られない問題を含んでいるからである。この問題はアルカディ・ネミロフスキーによって議論されている。

そのため実用上の効率を求めるには問題のクラスにさらに制約を加える必要がある。2つの障壁関数法の方法がある。1つはネストロフとネミロフスキーによる自己整合障壁関数（self-concordant）、もう1つはTerlakyらによる自己正規障壁関数である。

準凸最小化

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

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

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

拡張

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