凸最適化

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

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

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

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

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

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

すなわちx^\ast

f(x^\ast) \le 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)が凸関数であれば、これを凸最適化問題という。


他には、以下の形式の最適化問題を凸最適化問題という。

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

ここで、関数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_i(x) = 0 関数h_iアフィン変換

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

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

\begin{align}
&\underset{x}{\operatorname{minimize}}& & f(x) \\
&\operatorname{subject\;to}
& &g_i(x) \leq 0, \quad i = 1,\dots,m \\
&&&h_i(x) = 0, \quad i = 1, \dots,p.
\end{align}

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

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

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

凸最大化問題[編集]

拡張[編集]

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

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

他には[編集]


References[編集]

  • 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. 
  • 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

External links[編集]