凸最適化

凸最適化（とつさいてきか、英: 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 f(x^{\ast })\leq f(x)}$ for all ${\displaystyle x\in {\mathcal {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} }$は凸である。

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

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

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

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

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次制約下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).

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

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

表 話 編 歴 数理最適化 • 最適化問題 : メソッド • ヒューリスティック
非線形(無制約)	… 関数　 黄金分割探索 直線探索 ネルダー–ミード法 連続放物線補間（英語版） 勾配法 収束性 信頼領域 ウルフ条件 準ニュートン法 BFGS法 ブロイデン法 L-BFGS（英語版） DFP法 対称ランク1法（英語版） その他の求解法 ガウス・ニュートン法 最急降下法 レーベンバーグ・マルカート法 共役勾配法（非線形共役勾配法） 切り捨てニュートン法（英語版） ドッグレッグ法 … ヘッセ行列 最適化におけるニュートン法（英語版）
非線形(制約付き)	一般 バリア関数 ペナルティ関数法（英語版） 微分可能 ラグランジュの未定乗数法 逐次二次計画法 連続線形計画（英語版）
凸最適化	凸縮小化 切除平面法（英語版、デンマーク語版、ドイツ語版、スペイン語版） 簡約勾配法 劣勾配法（英語版） 線型 および 二次 内点法 カチヤンの楕円体法 カーマーカーの投影アルゴリズム ベイズ-交換 単体法 改訂単体法（英語版） 十文字法（英語版） レムケの主ピボット操作法（英語版） 有効制約法（英語版）
組合せ最適化	系列範例 (Paradigms) 近似アルゴリズム 動的計画法 貪欲法 整数計画問題(分枝限定法 若しくは 分枝カット法) グラフ理論 最小全域木 ベルマン–フォード法 ブルーフカ法 ダイクストラ法 ワーシャル–フロイド法 ジョンソン法（英語版） クラスカル法 最大フロー問題 Dinic法（英語版） エドモンズ・カープ フォード・ファルカーソン プッシュリラベル最大流アルゴリズム（英語版）
メタヒューリスティクス	進化的アルゴリズム（進化戦略） 山登り法 局所探索法 焼きなまし法 タブーサーチ ベイスンホッピング法
カテゴリ（最適化 • アルゴリズム） • ソフトウェア（英語版）