Comments
Description
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˜ が すべて凸集合となる(二つの凸集合の共通部分は凸集合であることに注意).