初級Mathマニアの寝言

数学は色々なところで応用可能であり、多くの人が数学の抽象的な概念の意味や意義を鮮明に知ることができれば今まで以上に面白い物や仕組みが生まれるかもしれません。このブログは数学を専門にしない人のために抽象的な概念の意味や意義を分かりやすく説明することを目的としています。数学を使って何かしたい人のお役に立てたら幸いです。

凸解析

この記事では最適化理論の基盤となる凸解析の理論を解説します。

最適化問題とは

目的関数と呼ばれる関数  f:{\bf R}^n\rightarrow {\bf R} を制約条件  x\in S \subset {\bf R}^n のもとで最小化する問題を最適化問題と呼びます。特に、 f が凸関数で、 S が凸集合である時、凸最適化問題呼びます。凸最適化問題は効率的に解く方法がたくさん研究されています。

●凸集合と凸関数と凹関数

 次の性質を満たす集合を凸集合と呼びます。

f:id:ogyahogya:20160517164152p:plain

つまり、ある集合の任意の2点を結んだ線分がその集合に含まれるなら、その集合は凸集合です。凸集合と非凸集合のイメージ図は次のような感じになります。

f:id:ogyahogya:20160517164353p:plain

次の性質を満たす関数を凸関数と呼びます。

f:id:ogyahogya:20160517164505p:plain

凸関数と非凸関数のイメージ図は次のような感じになります。

f:id:ogyahogya:20160517173323p:plain

凸集合と凸関数はエピグラフという概念を通じて関係付けることができます。

f:id:ogyahogya:20160517173418p:plain

例えば、次のようにエピグラフを図示することができます。

f:id:ogyahogya:20160517173512p:plain

 凸集合と凸関数は次の関係があります。

f:id:ogyahogya:20160517173611p:plain

凸関数は最小化のしやすい関数ですが、最大化のしやすい関数としては次の凹関数があります。

f:id:ogyahogya:20160518161105p:plain

●狭義凸関数

凸関数は最小化しやすい関数ですが、最小値を与える点は一つとは限りません。最小値を与える点が存在すれば一つである凸関数を狭義凸関数と言います。

f:id:ogyahogya:20160519093017p:plain

f:id:ogyahogya:20160519093049p:plain

f:id:ogyahogya:20160519093101p:plain

狭義凸関数だからといって、最小値が必ず存在するとは限りません。最小値の存在しない狭義凸関数の例としては  x e^x があります。

 ●凸集合と凸関数の性質(極一部)

任意の数の凸集合の共通部分は凸集合になります。

f:id:ogyahogya:20160518163118p:plain

ある集合上の点によってパラメトライズされた凸関数は、そのパラメータについての上限を取っても凸関数となります。つまり、以下が成り立ちます。

f:id:ogyahogya:20160518163936p:plainこれにより、凸関数の共役関数が凸関数になることが保障されます(共役関数は今度紹介します)。また、これが、こちらの大偏差原理に関する記事で紹介したレート関数が凸関数になる理由です。これが成り立つことは次の関係式より分かります。

f:id:ogyahogya:20160518171916p:plain

実際に、 f(x,y) x について凸関数なので、 {\rm epi}\, f(\cdot,y) は凸集合となり、凸集合の共通部分は凸集合であることから  {\rm epi}\, g も凸集合となる事が分かり、その結果  g は凸関数となることが分かります。上の関係式は以下のように証明できます。

f:id:ogyahogya:20160518172255p:plain

凹関数に関しても次のように同様の関係が成り立ちます。

f:id:ogyahogya:20160518172353p:plainこれにより、ラグランジアンから双対関数を定義したときに、双対関数が凹関数になることが保障されます(ラグランジアンと双対関数は今度紹介します)。

微分可能な凸関数

微分可能な凸関数は次のように特徴付けられます。

f:id:ogyahogya:20160519094417p:plain

これは

f:id:ogyahogya:20160519094446p:plain

を意味していて、

f:id:ogyahogya:20160519094509p:plain

というような関係にあるということです。

また、微分可能な凸関数の最小値を与える点は勾配がゼロになる点です。

f:id:ogyahogya:20160519094910p:plain

●勾配情報の重要性

微分可能な関数  f(x) は勾配  \nabla f(x) を求めることができます。勾配の情報は関数の最小化を考えるにあたって便利です。このことを実感するために、次のようなユークリッド空間上の制約なしの最小化問題を考えましょう。

f:id:ogyahogya:20160519110919p:plain

ただし、目的関数 f微分可能な凸関数であるとします。この問題を解くためには、現在の点を x_k としたときに f が減少する方向に進んでいけば良いです。つまり、

f:id:ogyahogya:20160519111247p:plain

 \eta_k f の減少する方向であれば良いわけです。目的関数  f が減少する方向を調べるには点  x_k から微小に動いたときの  f の関数値がどのように変化するかを調べれば良いわけで、そのようなことを調べるためには

f:id:ogyahogya:20160519112446p:plain

 t=0微分すれば良いです (  g_{\eta_k} t=0 での微分 f の点  x_k での  \eta_k 方向の微分を意味しているので)。 そこで、関数  g_{\eta_k} t=0 での微分を計算してみると

f:id:ogyahogya:20160519112808p:plain

となります。よって、現在の点  x_k から  \nabla f(x_k) の逆方向に進むと目的関数  f は減少するということが分かります。このことをもとに、進行方向を表す  \eta_k

f:id:ogyahogya:20160519122030p:plain

とした最適化アルゴリズム最急降下法と呼びます。目的関数  f微分可能な凸関数であれば  \nabla f(x_k)=0 が点  x_k で最小値を取っている証となるので最急降下法のようなアルゴリズム \nabla f(x_k)\approx 0 となるまで単純に反復すれば良いということになります。このように勾配情報は凸関数の最小化を実行するにあたって重要な情報となります。

●劣微分と劣勾配

上で勾配情報は凸関数の最小化を実行するにあたって重要だと述べましたが、凸関数は必ずしも微分可能であるとは限りません。例えば、 |x| は凸関数ですが、 x=0微分可能ではありません。しかし、勾配のようなものを微分可能でない凸関数に対しても定義することができます。まず、微分可能な凸関数  f の点  x での勾配  \nabla f(x)エピグラフ  {\rm epi}\, f の点 x における支持超平面を特徴付けたことを思い出しましょう。この支持超平面は  \alpha= f(x)+\nabla f(x)^T (y-x) を満たす点  (y,\alpha) から形成されていました。微分可能でない凸関数  fに対しても、エピグラフ  {\rm epi}\, f の点 x における支持超平面を考えることができ、その支持超平面を特徴付ける「勾配のようなもの」の集まりを微分と言います。

f:id:ogyahogya:20160519125824p:plain

そして、劣微分の要素である「勾配のようなもの」を劣勾配と言います。

f:id:ogyahogya:20160519130224p:plain

劣勾配は通常の勾配の一般化になっていることが次の性質が成り立つことから分かります。

f:id:ogyahogya:20160519130326p:plain

つまり、凸関数が微分可能だったら劣勾配は勾配と一致するというわけです。また、ある点における劣微分がゼロを含んでいたら(劣勾配にゼロのものがあったら)、その点で関数は最小値をとります。

f:id:ogyahogya:20160519130354p:plain

微分の計算方法を具体例で示しておきます。

f:id:ogyahogya:20160519130944p:plain

上の |x| という微分可能でない凸関数は、スパースな解が期待できるような最適化問題(最適解の成分はたくさんゼロになると期待できるような問題)によく利用されています。

●参考文献

(1) もっと数学的に細かいことが書いています。

非線形最適化の基礎

非線形最適化の基礎

 

 (2) スパースな解が期待できるような最適化問題について解説しています。

スパース性に基づく機械学習 (機械学習プロフェッショナルシリーズ)

スパース性に基づく機械学習 (機械学習プロフェッショナルシリーズ)