凸最適化 （とつさいてきか、英 : Convex optimization ）とは最適化問題 の分野のひとつで、凸集合 上の凸関数 の最小化問題である。
凸最小化問題は一般的な最適化問題よりも簡単に最適化が可能であり、局所的な最小値が大域的な最小値と一致する性質をもつ。
実ベクトル空間
X
{\displaystyle X}
f
:
X
→ → -->
R
{\displaystyle f:{\mathcal {X}}\to \mathbb {R} }
が
X
{\displaystyle X}
X
{\displaystyle {\mathcal {X}}}
凸最適化問題とは
f
(
x
)
{\displaystyle f(x)}
X
{\displaystyle {\mathcal {X}}}
x
∗ ∗ -->
{\displaystyle x^{\ast }}
すなわち
x
∗ ∗ -->
{\displaystyle x^{\ast }}
f
(
x
∗ ∗ -->
)
≤ ≤ -->
f
(
x
)
{\displaystyle f(x^{\ast })\leq f(x)}
x
∈ ∈ -->
X
{\displaystyle x\in {\mathcal {X}}}
である。
X
{\displaystyle {\mathcal {X}}}
x
∗ ∗ -->
{\displaystyle x^{\ast }}
f
(
x
∗ ∗ -->
)
=
min
{
f
(
x
)
:
x
∈ ∈ -->
X
}
,
{\displaystyle f(x^{\ast })=\min\{f(x):x\in {\mathcal {X}}\},}
ここで
X
⊂ ⊂ -->
R
n
{\displaystyle {\mathcal {X}}\subset \mathbb {R} ^{n}}
実現可能 集合で、
f
(
x
)
:
R
n
→ → -->
R
{\displaystyle f(x):\mathbb {R} ^{n}\rightarrow \mathbb {R} }
X
{\displaystyle {\mathcal {X}}}
R
n
{\displaystyle \mathbb {R} ^{n}}
f
(
x
)
{\displaystyle f(x)}
以上は数学的に一般化された定義であるが、この問題が実際に提示される場面において
X
⊆ ⊆ -->
R
2
{\displaystyle {\mathcal {X}}\subseteq \mathbb {R^{2}} }
g
i
(
x
)
:
i
=
1
,
… … -->
,
m
{\displaystyle g_{i}(x):i=1,\dots ,m}
X
:=
{
x
∈ ∈ -->
R
n
:
g
i
(
x
)
≤ ≤ -->
0
,
i
=
1
,
… … -->
,
m
}
{\displaystyle {\mathcal {X}}:=\{x\in \mathbb {R^{n}} :g_{i}(x)\leq 0,i=1,\dots ,m\}}
こういった事情を踏まえて以下のような定義が与えられることもある：
minimize
f
(
x
)
s
u
b
j
e
c
t
t
o
g
i
(
x
)
≤ ≤ -->
0
,
i
=
1
,
… … -->
,
m
{\displaystyle {\begin{aligned}&\operatorname {minimize} &&f(x)\\&\operatorname {subject\;to} &&g_{i}(x)\leq 0,\quad i=1,\dots ,m\end{aligned}}}
ここで、関数
f
,
g
1
… … -->
g
m
:
R
n
→ → -->
R
{\displaystyle f,g_{1}\ldots g_{m}:\mathbb {R} ^{n}\rightarrow \mathbb {R} }
凸最適化問題において以下の命題は真である。
極小値が存在すれば大域的最小値である
すべての（大域的）最小値の集合は凸である
強凸関数であり関数が最小値を持てば、一意に決まる ヒルベルト射影理論 、分離超平面理論 、Farkasの補題 などの関数解析 （ヒルベルト空間 上の）とも関係している。
標準形 は凸最小化問題をよく使用される直感的な形式で表現する。
3つの部分で成り立つ。
凸関数
f
(
x
)
:
R
n
→ → -->
R
{\displaystyle f(x):\mathbb {R} ^{n}\to \mathbb {R} }
x
{\displaystyle x}
不等式制約
g
i
(
x
)
≤ ≤ -->
0
{\displaystyle g_{i}(x)\leq 0}
g
i
{\displaystyle g_{i}}
等式制約
h
j
(
x
)
=
0
{\displaystyle h_{j}(x)=0}
h
j
{\displaystyle h_{j}}
アフィン変換 、すなわち線形関数。実際には線形制約とアフィンな制約はよく使用される。
これらの形式は
h
j
(
x
)
=
a
j
T
x
+
b
j
{\displaystyle h_{j}(x)=a_{j}^{T}x+b_{j}}
a
j
{\displaystyle a_{j}}
b
j
{\displaystyle b_{j}}
凸最小化問題は以下のように表される
minimize
x
f
(
x
)
s
u
b
j
e
c
t
t
o
g
i
(
x
)
≤ ≤ -->
0
,
i
=
1
,
… … -->
,
m
h
j
(
x
)
=
0
,
j
=
1
,
… … -->
,
p
.
{\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}}}
等式制約
h
(
x
)
=
0
{\displaystyle h(x)=0}
h
(
x
)
≤ ≤ -->
0
{\displaystyle h(x)\leq 0}
− − -->
h
(
x
)
≤ ≤ -->
0
{\displaystyle -h(x)\leq 0}
h
j
(
x
)
=
0
{\displaystyle h_{j}(x)=0}
h
j
(
x
)
{\displaystyle h_{j}(x)}
h
j
(
x
)
≤ ≤ -->
0
{\displaystyle h_{j}(x)\leq 0}
− − -->
h
j
(
x
)
≤ ≤ -->
0
{\displaystyle -h_{j}(x)\leq 0}
h
j
(
x
)
=
0
{\displaystyle h_{j}(x)=0}
h
j
(
x
)
{\displaystyle h_{j}(x)}
以下で示す例はすべて凸最小化問題であるか、変数変換により凸最小化問題にできる問題である。
標準形に表された凸最小化問題を考える。
コスト関数を
f
(
x
)
{\displaystyle f(x)}
g
i
(
x
)
≤ ≤ -->
0
(
i
=
1
… … -->
m
)
{\displaystyle g_{i}(x)\leq 0(i=1\ldots m)}
X
{\displaystyle {\mathcal {X}}}
X
=
{
x
∈ ∈ -->
X
|
g
1
(
x
)
≤ ≤ -->
0
,
… … -->
,
g
m
(
x
)
≤ ≤ -->
0
}
.
{\displaystyle {\mathcal {X}}=\left\lbrace {x\in X\vert g_{1}(x)\leq 0,\ldots ,g_{m}(x)\leq 0}\right\rbrace .}
この問題に対するラグランジュ関数 は
L (x ,λ 0 ,...,λ m λ 0 f (x ) + λ 1 g 1 (x ) + ... + λ m g m x ).X 上の関数f を最小化するX 上の点x に関して
実数値のラグランジュ係数λ 0 , ..., λ m が存在し、
以下を満たす。
X 上のすべての変数に関してx はL (y , λ0 , λ1 , ..., λm ) を最小化するλ0 ≥ 0, λ1 ≥ 0, ..., λm k
λ 1 g 1 (x ) = 0, ..., λ m g m x ) = 0 (相補スラック性).
凸最小化問題は以下の方法を用いて解くことが可能である。
その他の手法
劣勾配法は簡単に実装でき多くの適応例がある。
双対劣勾配法 は劣勾配法 を双対問題 に適応した方法である。
ドリフトプラスペナルティー法 は双対劣勾配法と類似しているが、
主変数に関して時間平均をとっている点が異なる。
凸最適化問題にクラスによっては更新法の効率は悪いものがある。
それはクラスには多くの関数と劣勾配 を評価しなければ
精確に最小値を得られない問題を含んでいるからである。
この問題はArkadi Nemirovskiiによって議論されている。
そのため実用上の効率を求めるには問題のクラスにさらに制約を加える必要がある。
2つの障壁関数法 の方法がある。
1つはNesterovとNemirovskiiによる自己調和 (self-concordant) 障壁関数、
もう1つはTerlakyらによる自己正規障壁関数である。
凸のレベル集合をもつ問題は理論上は効率的に最小化できる。
Yuri Nesterovは準凸最小化問題を効率的に解けることを証明した。
これの結果はKiwielによって拡張された。
計算複雑性の理論の中では、準凸計画問題 と凸計画問題は問題の次元に対して
多項式時間で解くことが可能である。
Yuri Nesterovが最初に準凸最小化問題を効率的に解くことが可能であることを示した。
しかし、この理論的に効率的な方法は発散する数列をステップサイズに用いていた。
これは古典的な劣勾配法の開発に使われていた。
発散数列を用いる古典的な劣勾配法は、劣勾配射影法 、勾配バンドル法 、非平滑フィルタ法 など
の現代的な凸最小化法よりかなり遅いことが知られている。
凸に近いが非凸の関数の問題は計算困難である。
Ivanovの結果によれば関数が滑らかさあっても単峰の関数を最小化することは難しい。
正無限を含むように凸関数を拡張できる。たとえば、指標関数は
x
∈ ∈ -->
X
{\displaystyle x\in {\mathcal {X}}}
0
{\displaystyle 0}
凸関数の拡張には擬似凸関数 と準凸関数 を含む。
凸解析と更新法の部分的な拡張は
非凸最小化問題に対する近似解法として一般化された凸性の中で考えられている。
Bertsekas, Dimitri (2003). Convex Analysis and Optimization . Athena Scientific Boyd, Stephen P.; Vandenberghe, Lieven (2004) (pdf). Convex Optimization 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 . MR 1295240 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 . MR 1900016 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
