...

第2章 凸関数と凸集合

by user

on
Category: Documents
19

views

Report

Comments

Transcript

第2章 凸関数と凸集合
1
2014-12-17 最適化手法
第2章
凸関数と凸集合
最適化の観点から,連続世界の凸関数と凸集合について,基本的な事柄を説明する1 .
2.1
極小と最小
簡単な最小化問題を例に,極小 (minimal) と最小 (minimum) の関係を説明する.多くの読者に
とっては,復習ということになるであろう.
まず,4 次関数
f (x) = x4 + 2x2 − 8x − 12
(2.1)
の最小値を求める問題を考える(変数 x の動く範囲は実数全体とする).とりあえず f (x) の微分
を計算してみると,
f ′ (x) = 4x3 + 4x − 8 = 4(x − 1)(x2 + x + 2)
となる.x = 1 で f ′ (x) = 0 であり,x < 1 で f ′ (x) < 0,x > 1 で f ′ (x) > 0 なので,f (1) = −17
が最小値であると分かる(図 2.1).
1
1
では,別の 4 次関数
f (x) = 3x4 − 4x3 − 12x2 + 3
(2.2)
の場合はどうだろうか(図 2.2).同様に微分すると,
f ′ (x) = 12x3 − 12x2 − 24x = 12x(x + 1)(x − 2)
となる.f ′ (x) = 0 を満たす点は x = 0, −1, 2 の 3 個あり,f ′ (x) から得られる情報だけではどの点
が最小値を与えるのか分らない.関数値 f (0) = 3,f (−1) = −2,f (2) = −29 を計算して比べる
と f (2) = −29 が最小値と判明する.x = 2 が最小点(大域最適)であり,x = −1 は極小点(局所
最適)であるが最小点(大域最適)ではない.また,x = 0 は極大点であって,局所最適ですらな
い.最初の関数 (2.1) とは随分違って,面倒である.
f
-2
-1
-2
30
f
30
20
20
10
10
-1
f
20
10
-2
1
12
x 23
x
3
-1
-2
f
20
10
-1
1
-10
-10
-10
-10
-20
-20
-20
-20
-30
-30
12
23
3
x
x
図 1: 図
4 次関数
1: 4 次関数
(??) のグラフ
(??) のグラフ 図 2: 図
4 次関数
2: 4 次関数
(??) のグラフ
(??) のグラフ
図 2.1: 4 次関数 (2.1) のグラフ
図 2.2: 4 次関数 (2.2) のグラフ
1 本資料は,室田一雄「離散凸解析の考えかた」,
第2章, 共立出版, 2007 を講義資料用に改変したものである.
1
第 2 章 凸関数と凸集合
2
f ✻
f ✻
f ✻
f ✻
f ✻
f ✻
✲
✲x
✲
✲x
x
✲
✲x
x
x
図 1: 凸関数
図2.3:
1: 凸関数
凸関数
図
f ✻
f ✻
f ✻
f ✻
✲
✲x
✲
✲x
x
f ✻
f ✻
x
f ✻
f ✻
✲
✲x
x
f ✻
f ✻
✲
✲x
x
✲
✲x
x
図 2: 凸でない関数
図 2: 凸でない関数
図 2.4: 凸でない関数
2.2
2.2.1
凸関数
1 変数の場合
前節で見たように,関数 (2.1) と関数 (2.2) で状況は大きく異なっていた.関数 (2.1) では,幸い
なことに,局所最適(極小)が大域最適(最小)であった.
このような都合のよい状況を一般的に考察するのに便利なのが「凸関数」という概念である.図
2.3 のようなものが凸関数であり,図 2.4 の関数は凸でない.
次の段落に進んで定義を読む前に,図 2.3 と図 2.4 を眺めて,凸関数の概念を感じ取ってほしい.
日常生活では,辞典を見て厳密な定義を勉強する前に,実例をたくさん見て,概念を会得するのが
普通である.犬をたくさん見ていれば,犬の定義は言えなくても,犬と猫の区別がつくようにな
る.数学でも似たようなことがある.
さて,凸関数の定義である.図 2.5 のように,関数 f (x) のグラフ上の任意の 2 点 P = (x, f (x)),
Q = (y, f (y)) を考える.この 2 点に挟まれた範囲で f (x) のグラフが線分 PQ より下にあるとき,
関数 f (x) は凸 (convex) であるという.より丁寧に下に凸 (convex downwards) ということもある.
このことを式を使って書けば,任意の x,y ,および 0 ≤ t ≤ 1 を満たす任意の実数 t に対して
2.2. 凸関数
3
f
✻
S
P
Q
R
✲
x
z
y
k
tx + (1 − t)y
図 1: 凸関数の定義
図 2.5: 凸関数の定義
不等式
tf (x) + (1 − t)f (y) ≥ f (tx + (1 − t)y)
(2.3)
が成り立つような関数 f を凸関数 と呼ぶということである.z = tx + (1 − t)y とおくと,図 2.5 に
おいて,
R = (z, f (z)),
S = (z, tf (x) + (1 − t)f (y))
であり,不等式 (2.3) は S が R より上にあることを表している.
関数 f (x) が 2 階微分可能のとき,f (x) が凸関数であるための必要十分条件は,任意の x で
′′
f (x) ≥ 0 となることである.例えば,関数 (2.1) では,f ′′ (x) = 12x2 + 4 であり,これは常に正
だから,凸関数である.一方,関数 (2.2) では f ′′ (x) = 12(3x2 − 2x − 2) であり,これは x = 0 に
対して負になるので,凸関数ではない.任意の x で f ′′ (x) ≥ 0 となることは,導関数 f ′ (x) が単調
増加(非減少)であることと同じである.
上に述べた凸関数の定義では,暗黙のうちに,関数 f は任意の実数 x に対して定義された実数値
関数と仮定していた.定義域も値域も実数全体ということである.これを記号で書けば,f : R → R
となる2 .しかし,例えば x > 0 に対して定義された関数 f (x) = 1/x のような場合には,形式的に
{
1/x (x > 0)
f (x) =
+∞ (x ≤ 0)
と再定義して,これを凸関数と考えると便利なことが多い.実数全体 R に無限大 (+∞) を付け加
えた集合を R と表せば,このとき,再定義された関数は f : R → R ということになる.
凸関数の定義式 (2.3) は,このような関数 f : R → R に対しても意味をもつ.すなわち,もし
f (x) と f (y) の一方でも +∞ のときには,不等式 (2.3) は自動的に成立すると考えるのである.こ
のように解釈して,値域に +∞ を許す関数 f : R → R に対して凸関数の概念を定義するのが普通
である.
なお,関数値の符号を変えると凸になる関数を,凹関数という.すなわち,関数 f が凹関数
(concave function) とは,−f が凸関数であることと定義する.例えば,図 2.4 の右下の関数は凹
関数である.凹であることを上に凸 (convex upwards) ということもある.
2 数学では,実数全体を R,整数全体を Z という記号で表す.Z はドイツ語の Zahl(数)に由来する.R は英語の real
number(実数)あるいはドイツ語の reelle Zahl である.
第 2 章 凸関数と凸集合
4
2.2.2
極小と最小の一致
凸関数のいいところは,最小化問題において局所最適性 (local optimality) と大域最適性 (global
optimality) が一致することである.すなわち,次の定理が成り立つ.
定理 2.1 凸関数では,極小点と最小点は一致する.
(証明) 極小点が最小点であることを示せばよい.図を見て考えれば明らかであるが,定義式 (2.3)
を使って証明するのも簡単で,次のようになる.
点 x を凸関数 f の極小点とし,任意の点 y を考える.不等式 (2.3) において t < 1 を 1 に近づけ
ると z = tx + (1 − t)y は x の近くにくるが,そのとき,f (z) ≥ f (x) が成り立つ(x が極小点だか
ら).したがって,
tf (x) + (1 − t)f (y) ≥ f (tx + (1 − t)y) = f (z) ≥ f (x)
が成り立つ.これを移項して整理すると,f (y) ≥ f (x) が導かれる.点 x における関数値が任意の
点 y における関数値以下であるから,x は最小点である.
定理の正しさは証明されたから,次に,その意義を考察しよう.工学などの応用の立場からみる
と,数学の定理は正しいから有り難いのではなくて,使えるから有り難いのである.だから,どう
使えるのかが分って初めて定理を理解したことになる.
さて,上の定理の意義であるが,この定理は,凸関数に対して,与えられた点 x が最適解である
ことを確認する方法を与えていると解釈できる.例えば,f が微分可能な凸関数のとき,ある点 x
で f ′ (x) = 0 であれば,x は最小点であると結論できる.つまり「f ′ (x) = 0」は最適性の証拠とな
る.関数 (2.1) は凸関数であり f ′ (1) = 0 だから,x = 1 はこの関数の最小点である.
ここで,定理 2.1 は最適解の求め方を与えてはいないことに注意してほしい.この定理は(誰か
が見つけてくれた)最適解の候補 x が本当に最適解であることを(十分条件として)確認する方
法を与えている.しかし,最適解の候補 x をどうやって見つけるかは何も教えていない.一般に,
最適化問題の解法を考えるとき,
(i) 最適解を求めるアルゴリズムと
(ii) 最適性の証明・証拠
を区別して考えることが大切である.
2.2.3
多変数の場合
多変数の関数 f ,すなわち,n 次元実数ベクトルを変数とする関数 f : Rn → R を考えよう(Rn
は n 次元実数ベクトルの全体を表す).このときも不等式 (2.3) と同じ形の不等式
tf (x) + (1 − t)f (y) ≥ f (tx + (1 − t)y)
(2.4)
によって凸関数の概念が定義できる.そして,このときにも,極小=最小の定理(定理 2.1)がそ
のままの形で成立する.
関数 f が滑らかな場合には,2 階偏導関数によって f が凸関数かどうかを判定できる.2 階偏導
関数を並べた n 次行列
[
H=
∂2f
∂xi ∂xj
]


=

∂2f
∂x1 ∂x1
..
.
∂2f
∂xn ∂x1
···
..
.
∂2f
∂x1 ∂xn
···
∂2f
∂xn ∂xn
..
.




(2.5)
2.3. 凸集合
5
を考え,これを f のヘッセ行列 (Hessian matrix) という.一般に
(
)
(
)
∂
∂f
∂
∂f
=
∂xi ∂xj
∂xj ∂xi
が成り立つので,ヘッセ行列は対称行列である.
1 変数の場合には,f が凸関数であることは f ′′ (x) ≥ 0 と同値であった.このことの一般化とし
て,多変数の場合には,次の定理が成り立つ.
定理 2.2 滑らかな関数 f が凸であるためには,そのヘッセ行列が各点 x で半正定値となることが
必要十分である.
なお,一般に,対称行列 A が半正定値 (positive semidefinite) であるとは,
任意のベクトル x に対して x⊤ Ax ≥ 0
という条件を満たすことを言う.この条件は A のすべての固有値が非負であることと等価である.
また,上の不等号で等号を除外した条件
任意のベクトル x ̸= 0 に対して x⊤ Ax > 0
を満たすとき,A は正定値 (positive definite) であると言う.正定値であることはすべての固有値
が正であることと等価である.
例 2.3 2 次の対称行列
[
A=
a c
c
]
b
が半正定値であるための必要十分条件は,a ≥ 0,b ≥ 0,ab ≥ c2 である.したがって,c ≤ 0,
a + c ≥ 0,b + c ≥ 0 ならば A は半正定値である(この種の行列は第 4.4 節で登場する).
2.3
凸集合
関数に対して凸関数の概念を定義したが,集合に対しても凸集合という概念を定義できる.本節
では凸集合を定義し,凸集合と凸関数の関係を説明する.
最適化問題は,通常
Minimize f (x) subject to x ∈ S
(2.6)
の形に書かれる.これは変数 x を x ∈ S という条件を満たす範囲で動かして関数 f (x) を最小にせ
よという問題を表している.ここで,関数 f を目的関数 (objective function), 集合 S を実行可能
領域 (feasible region),条件 x ∈ S を制約条件 (constraint) と呼ぶ. 例えば,第 2.1 節の 4 次関数
の最小化問題では,変数 x の動く範囲が実数全体だったから,S = R である.
扱い易い最適化問題とは,どのような形の問題であろうか.既に述べたように,目的関数につい
ては,f が凸関数ならばよい.それでは,実行可能領域についてはどうだろうか.実は,S が凸集
合であればよいのである.最適化の分野では,S が凸集合で f が凸関数であるような最小化問題
を凸計画問題 (convex program) と呼ぶ.凸計画問題は,理論的にも実際的にも扱い易い問題であ
る3 .
3 本書では扱わないが,線形計画問題,半正定値計画問題は凸計画問題の代表例である.
第 2 章 凸関数と凸集合
6
y
x
x
y
図 1: 凸集合と凸でない集合
図 2.6: 凸集合と凸でない集合
それでは,凸集合の定義に入ろう.n 次元空間の部分集合 S (すなわち S ⊆ Rn )が凸集合
(convex set) であるとは,S に含まれる任意の 2 点 x,y に対して,x と y を結ぶ線分が S に含ま
れることと定義される(図 2.6).式で書けば,S が凸集合とは,条件
x, y ∈ S, 0 ≤ t ≤ 1 =⇒ tx + (1 − t)y ∈ S
(2.7)
を満たすことである.有限個の点 x1 , . . . , xm に対し,
t1 x1 + · · · + tm xm
(ただし
m
∑
ti = 1, ti ≥ 0 (1 ≤ i ≤ m))
(2.8)
i=1
の形の表現をこれらの点の凸結合 (convex combination) と呼ぶが,S が凸集合ならば,S に属す
る任意の有限個の点の凸結合は S に属する.直感的には,くびれや穴のない集合が凸集合である.
集合 S に対して,S を含むすべての凸集合の共通部分は,S を含む最小の凸集合である.これを
S の凸包 (convex hull) と呼び,S と表す.S は,S の有限個の点の凸結合 (2.8) の全体に等しい.
凸集合と凸関数の間には密接な関係がある.集合 S に対して,その標示関数 (indicator function)
δS : R n → R を
{
δS (x) =
0
(x ∈ S)
+∞ (x ̸∈ S)
(2.9)
と定義すると,
S が凸集合 ⇐⇒ δS が凸関数
(2.10)
が成り立つ4 .
この関係 (2.10) を確かめるのは簡単である.凸関数の定義式 (2.4) で f = δS とすると,この不等
式は δS (x) と δS (y) の少なくとも一方が +∞ のときには自動的に成立するので,δS (x) = δS (y) = 0
の場合に δS (tx + (1 − t)y) = 0 になることと等価である.これを言い換えると,x, y ∈ S ならば
tx + (1 − t)y ∈ S が成り立つという条件(すなわち式 (2.7))になる.
逆に,凸集合を用いて凸関数を定義することもできる.グラフ y = f (x) の上側の集合をエピグ
ラフ (epigraph) と呼び,記号
epi f = {(x, y) ∈ Rn+1 | y ≥ f (x)}
(2.11)
で表す(図 2.7 参照).このとき,
f が凸関数 ⇐⇒ epi f が凸集合
4 凸関数を定義するときに
+∞ の値を許したお蔭で,対応関係 (2.10) が得られる.
(2.12)
2.3. 凸集合
7
f ✻
✲
x
図図1:2.7:エピグラフ
エピグラフ
が成り立つ.これを納得するには,凸関数の定義(図 2.5)に登場した 2 点 P = (x, f (x)),Q
= (y, f (y)) を,凸集合の定義(図 2.6)の 2 点 x,y に対応させて考えればよい.
凸関数 f : Rn → R が与えられたとき,そのエピグラフは凸集合であるが,この他にも,f に付
随して凸集合が二つ考えられる.実効定義域と最小化集合である.これを説明しよう.
関数値 f (x) が有限の値であるような点 x の全体を f の実効定義域 (effective domain) と呼び,
dom f という記号で表す.すなわち
dom f = {x ∈ Rn | f (x) は有限値 }
(2.13)
である.また,関数 f の最小値を与える点 x の集合を最小化集合5 (set of minimizers) と呼び,
argmin f という記号で表す.すなわち,
argmin f = {x ∈ Rn | f (x) ≤ f (y) (∀y ∈ Rn )}
(2.14)
である.
凸関数の定義式 (2.4) から容易に分かるように,凸関数の実効定義域と最小化集合は凸集合にな
る.これを定理の形で述べておく.
定理 2.4 凸関数 f の実効定義域 dom f は凸集合である.
(証明) S = dom f とおき,式 (2.4) から式 (2.7) を導けばよい.x, y ∈ S とすると,式 (2.4) より
f (tx + (1 − t)y) は有限である.したがって tx + (1 − t)y ∈ S である.
定理 2.5 凸関数 f の最小化集合 argmin f は凸集合である.
(証明) S = argmin f とおき,式 (2.4) から式 (2.7) を導けばよい.α = min f とおき,x, y ∈ S と
すると,式 (2.4) と α の定義により
α = tf (x) + (1 − t)f (y) ≥ f (tx + (1 − t)y) ≥ α
となり,f (tx + (1 − t)y) = α である.したがって tx + (1 − t)y ∈ S である.
5 [2]
では最小値集合 と呼ばれている.式 (2.14) の記号 ∀ は「任意の」,
「すべての」の意味である.
8
第 2 章 凸関数と凸集合
補足 2.6 制約条件をもつ最適化問題 (2.6) に対して,目的関数 f と実行可能領域 S の標示関数
δS の和 f + δS を f˜ とおくことにすれば,もとの問題は関数 f˜ を最小化する問題となり,制約条
件のことは表に出さないで話ができる.ただし,f˜ の値は無限大 (+∞) になる可能性があるので,
f˜ : Rn → R である.このとき,dom f˜ = S ∩ dom f である.凸計画問題では S, dom f , dom f˜ が
すべて凸集合となる(二つの凸集合の共通部分は凸集合であることに注意).
Fly UP