最適化や凸解析の本のわりと序盤に登場するトピックに 劣微分・劣勾配 と 共役関数 があります。いずれも凸関数にとって特に重要な概念ですが、通常の書籍だと当然動きのない図でしか描かれていないため、イメージしづらい方もいるでしょう。そこで代表的な凸関数について、劣微分・劣勾配および共役関数のアニメーションを作りました（初めて本格的にGoogle Colabを使いました）。本の図よりはもっと鮮やかにイメージでき理解が深まるかと思います。なお、厳密には「閉真凸関数」などと呼ぶべき箇所を簡単のために単に「凸関数」と記述しています。厳密な定義などは専門書（例えば [福島2001,冨岡2015]）を参照ください。
劣微分・劣勾配
多変数関数 $f$ のある一点 $x$ での傾き（昇る方向）を表すベクトルを 勾配 と呼び $\nabla f(x)$ と表しますが、微分不可能な点では勾配を求めることができません。この問題を回避するために、まず関数 $f$ を凸関数に限定した上で、その関数の各点での傾きをただ一つの値に限定せずに「複数の値」として表現し、微分・勾配の概念を一般化したものが劣微分・劣勾配です。この「複数の値」＝集合として表現されるものが劣微分であり、その一要素である元を劣勾配と呼びます。
二次関数 $f(x)=x^2$
最適化において最も基礎的な関数と言えば二次関数でしょう。これはあらゆる点で微分可能ですから、劣微分はあらゆる点で唯一の劣勾配を持ち、そしてそれは勾配と等価です。
絶対値関数 $f(x)=|x|$
微分できない凸関数の代表格と言えば絶対値関数ですね。原点でのみ微分不可ですが、原点での傾きを $[-1,+1]$ という集合＝劣微分として表します。劣勾配としてゼロベクトルを含む位置が極値になります。アニメーションで見れば明らかですね。
指示関数 $f(x)=\delta_{|\cdot| \leq 1}(x)$
制約条件を目的関数に取り込む際に用いられる指示関数の例です。
ロジスティック損失関数 $f(x)=\ln(1+e^{-x})$
その他の例です。これもあらゆる点で微分可能なので導関数と等価です。
共役関数
共役関数 とはざっくり言えば(凸)関数を双対の世界から眺めたものであり、最適化問題の双対問題を考える際に便利な道具です。下図での緑の直線を見てもらえればわかりやすいですが、凸関数 $f(x)$ に下から定規をあてて滑らせるような操作をする際に、その緑の直線の傾き $\alpha$ の変化に応じて切片がどのように変化したかを追跡したものが共役関数 $f^{\ast}(\alpha)$ になります。このアプローチは、いわゆる「点と線の双対性」を使って、左図での緑線の軌跡を右図での緑点の軌跡へ変換したものに相当します。最適化で特に重要な概念である双対性もイメージしづらい代表格のトピックですので、これについてもまた改めて記事にまとめるかもしれません。
二次関数 $f(x)=x^2$
二次関数の共役関数は二次関数です。切片（左図の赤点）を上下ひっくり返した動きが共役関数そのものである点が理解する上で重要です。
絶対値関数 $f(x)=|x|$
絶対値関数の共役関数は$[-1,+1]$をサポートする指示関数になります。
指示関数 $f(x)=\delta_{|\cdot| \leq 1}(x)$
[2019/07/17] 誤解を招く表現があったので修正
先ほどとは逆に、$[-1,+1]$をサポートする指示関数の共役関数は絶対値関数になります。一般に指示関数の共役関数は錐状になります。（確か）$f$ が閉真凸関数の場合、その双共役関数（共役関数の共役関数） $f^{\ast\ast}$ は元の関数 $f$ と一致します。
ロジスティック損失関数 $f(x)=\ln(1+e^{-x})$
その他の例です。
むすび
実際の最適化の局面ではより高次元な関数を扱いますが、それでもこういった一次元での動きを見ておくとずいぶん理解が楽ではないでしょうか。特に書籍上の図には動きがなくイメージしづらいものですが、アニメーションでみると何をしているのか一目瞭然ですね。元々、本記事は今年度の講義資料用に作ったものですが、最適化の本などではこのあたりのトピックはサラッと触れられているだけなので、最適化を学び始めた学生さんなどに広く役立つかと思い公開しました。
なお、本記事は @mathusmassias の以下のツイートに触発されて書いたものです。Matplotlibでのアニメの作り方を教えてもらいました。ありがとうございました。
This article was inspired by @mathusmassias's following tweet with a gif about subdifferential. I appreciate his reply to my question about generating animation using matplotlib.
Other fundamental tool for non-smooth optim: subdifferential of f at x = set of all slopes of affine minorants of f which are exact at x. Coincides with {∇f(x)} if f cvx & differentiable. Leads to 1st order optimality condition for *non-smooth* cvx fcts @fpedregosa @PierreAblin pic.twitter.com/guhtGwe5nT
— Mathurin Massias (@mathusmassias) 2019年3月23日
参考資料
- 福島雅夫: "非線形最適化の基礎", 朝倉書店 (2001).
- 冨岡亮太: "スパース性に基づく機械学習", 講談社 (2015).
- https://twitter.com/mathusmassias/status/1109304558356824064