凸最適化のソースを表示

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

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

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

すなわち<math>x^\ast</math>は
:<math>f(x^\ast) \le f(x)</math> for all <math>x \in \mathcal{X}</math>.
である。

== 凸最適化問題 ==
<math>\mathcal{X}</math>上の<math>x^\ast</math> を見つける最適化問題である。
:<math>f(x^\ast) = \min \{f(x):x \in \mathcal{X}\},</math>
ここで<math>\mathcal{X} \subset \mathbb{R}^n</math>は実行可能集合で、
<math>f(x):\mathbb{R}^n \rightarrow \mathbb{R}</math>は目的関数である。
<math>\mathcal{X}</math>が閉凸集合で、
<math>\mathbb{R}^n</math>上で<math>f(x)</math>が凸関数であれば、これを凸最適化問題という。

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

<math>\mathcal{X}:=\{x\in\mathbb{R^n}:g_i(x)\leq0,i = 1,\dots,m\}</math>

こういった事情を踏まえて以下のような定義が与えられることもある：
: <math>\begin{align}
&\operatorname{minimize}& & f(x) \\
&\operatorname{subject\;to}
& &g_i(x) \leq 0, \quad i = 1,\dots,m
\end{align}</math>
ここで、関数<math>f, g_1 \ldots g_m : \mathbb{R}^n \rightarrow \mathbb{R}</math>は凸である。

== 理論 ==
凸最適化問題において以下の命題は真である。
* 極小値が存在すれば大域的最小値である
* すべての（大域的）最小値の集合は凸である
* 強凸関数であり関数が最小値を持てば、一意に決まる

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

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

3つの部分で成り立つ。

* '''凸関数''' <math>f(x): \mathbb{R}^n \to \mathbb{R}</math>　<math>x</math>に関して最小化される。
* '''不等式制約''' <math>g_i(x) \leq 0</math>。ここで関数<math>g_i</math>は凸である。
* '''等式制約''' <math>h_j(x) = 0</math>　関数<math>h_j</math>は[[アフィン変換]]、すなわち線形関数。 
実際には線形制約とアフィンな制約はよく使用される。
これらの形式は<math>h_j(x) = a_j^T x + b_j</math>と表せられる。
ここで、<math>a_j</math>は列ベクトル、<math>b_j</math>は実数である。

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

: <math>\begin{align}
&\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{align}</math>

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

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

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

== ラグランジュの未定乗数法 ==
標準形に表された凸最小化問題を考える。
コスト関数を<math>f(x)</math>、
不等式制約を<math>g_i(x)\leq 0 (i=1\ldots m) </math>
とすると、定義域<math>\mathcal{X}</math>は

:<math>\mathcal{X} = \left\lbrace{x\in X \vert g_1(x)\le0, \ldots, g_m(x)\le0}\right\rbrace.</math>

この問題に対する[[ラグランジュ関数]]は
:''L''(''x'',''&lambda;''<sub>0</sub>,...,''&lambda;''<sub>''m''</sub>) = ''&lambda;''<sub>0</sub>''f''(''x'') + ''&lambda;''<sub>1</sub>''g''<sub>1</sub>(''x'')  + ... + ''&lambda;''<sub>''m''</sub>''g''<sub>''m''</sub>(''x'').

''X''上の関数''f''を最小化する''X''上の点''x''に関して
実数値のラグランジュ係数''λ''<sub>0</sub>, ..., ''λ''<sub>m</sub>が存在し、
以下を満たす。
# ''X''上のすべての変数に関して''x''は''L''(''y'', λ<sub>0</sub>, λ<sub>1</sub>, ..., λ<sub>m</sub>) を最小化する
# λ<sub>0</sub> ≥ 0, λ<sub>1</sub> ≥ 0, ..., λ<sub>''m''</sub> ≥ 0, 少なくともひとつは λ<sub>''k''</sub>&gt;0,
# ''&lambda;''<sub>1</sub>''g''<sub>1</sub>(''x'') = 0, ..., ''λ''<sub>''m''</sub>''g''<sub>''m''</sub>(''x'') = 0 (相補スラック性).

== 方法 ==
凸最小化問題は以下の方法を用いて解くことが可能である。
* [[内点法]]
* [[バンドル法]]
* [[射影劣勾配法]]

その他の手法
*[[切除平面法]]
*[[楕円体法]]
*[[劣勾配法]]
*[[ドリフトプラスペナルティー法]]

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

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

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

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

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

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

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

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

== 脚注 ==
{{脚注ヘルプ}}
* {{cite book |last=Bertsekas |first=Dimitri |authorlink=Dimitri Bertsekas |title=Convex Analysis and Optimization |publisher=Athena Scientific |year=2003 }}
* {{cite book|title=Convex Optimization|first1=Stephen P.|last1=Boyd|first2=Lieven|last2=Vandenberghe|year=2004|publisher=Cambridge University Press|isbn=978-0-521-83378-3|url=http://www.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf|format=pdf|accessdate=October 15, 2011}}
* [[Jonathan M. Borwein|Borwein, Jonathan]], and Lewis, Adrian. (2000). ''Convex Analysis and Nonlinear Optimization''. Springer.
* Hiriart-Urruty, Jean-Baptiste, and [[Claude Lemaréchal|Lemaréchal, Claude]]. (2004). ''Fundamentals of Convex analysis''. Berlin: Springer.
* {{cite book|last1=Hiriart-Urruty|first1=Jean-Baptiste|last2=Lemaréchal|first2=Claude|title=Convex analysis and minimization algorithms, Volume&nbsp;I: Fundamentals|series=Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]|volume=305|publisher=Springer-Verlag|location=Berlin|year=1993|pages=xviii+417|isbn=3-540-56850-6|{{MR|1261420}}||unused_data=<!-- authorlink2=Claude Lemaréchal -->}}
* {{cite book|last1=Hiriart-Urruty|first1=Jean-Baptiste|last2=Lemaréchal|first2=Claude|title=Convex analysis and minimization algorithms, Volume&nbsp;II: Advanced theory and bundle methods|series=Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]|volume=306|publisher=Springer-Verlag|location=Berlin|year=1993|pages=xviii+346|isbn=3-540-56852-2|ref=harv|mr=1295240|unused_data=<!-- authorlink2=Claude Lemaréchal -->}}
* {{cite book|first=Krzysztof C.|last=Kiwiel|title=Methods of Descent for Nondifferentiable Optimization|year=1985|publisher=Springer-Verlag|location= New York|series=Lecture Notes in Mathematics|isbn=978-3540156420|ref=harv}}
* {{cite book|last=Lemaréchal|first=Claude|chapter=Lagrangian relaxation|pages=112–156|title=Computational combinatorial optimization: Papers from the Spring School held in Schloß Dagstuhl, May&nbsp;15–19,&nbsp;2000|editor=Michael Jünger and Denis Naddef|series=Lecture Notes in Computer Science|volume=2241|publisher=Springer-Verlag|location=Berlin|year=2001|isbn=3-540-42877-1|mr=1900016|doi=10.1007/3-540-45586-8_4|unused_data=<!-- authorlink=Claude Lemaréchal -->}}
* 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
* {{cite book |last=Rockafellar |first=R. T. |authorlink=R. Tyrrell Rockafellar |title=Convex analysis |publisher=Princeton University Press  |year=1970 |location=Princeton }}
* {{cite book |last=Ruszczyński |first=Andrzej |authorlink=Andrzej Piotr Ruszczyński |title=Nonlinear Optimization |publisher=Princeton University Press |year=2006 }}

== 関連項目 ==
* [[カルーシュ・クーン・タッカー条件]]
* [[最適化問題]]
* [[双対問題]]
* [[凸解析]]
* [[スレーターの条件]]
* [[ホアン・トゥイ (数学者)|ホアン・トゥイ]]、凸最適化の研究者

== 外部リンク ==
* Stephen Boyd and Lieven Vandenberghe, [http://www.stanford.edu/~boyd/cvxbook/ ''Convex optimization'']  (book in pdf)
* [http://www.stanford.edu/class/ee364a/ EE364a: Convex Optimization I] and [http://www.stanford.edu/class/ee364b/ EE364b: Convex Optimization II], Stanford course homepages
* [https://web.archive.org/web/20111102231047/http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-253-convex-analysis-and-optimization-spring-2010/ 6.253: Convex Analysis and Optimization], an MIT OCW course homepage
* Brian Borchers, [http://infohost.nmt.edu/~borchers/presentation.pdf An overview of software for convex optimization]

{{主要な最適化問題の分類}}
{{最適化アルゴリズム}}

{{デフォルトソート:とつさいてきか}}
[[Category:数学に関する記事]]
[[Category:関数]]
[[Category:最適化]]
[[Category:凸最適化|*]]