凸解析 - 初級Mathマニアの寝言

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

●最適化問題とは

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

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

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

f:id:ogyahogya:20160517164152p:plain

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

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$ における支持超平面を考えることができ、その支持超平面を特徴付ける「勾配のようなもの」の集まりを劣微分と言います。