凸共役の式（ルジャンドル変換）を導出する。

はじめに

• 凸関数の勉強をしていると「凸共役関数」をつくる「ルジャンドル変換」というものが出てくる。
• ルジャンドル変換の式のお気持ちを理解したい方へ、説明します。
• （注）この記事には「凸関数の説明」や「凸共役関数のうれしさの説明」などは書きません。

ルジャンドル変換の定義式

凸関数$f(x)$のルジャンドル変換は

f^\ast(p) = \sup_x (px-f(x))

で定義される。$f^\ast(p)$は$f(x)$の凸共役関数という。^{1 2}

当初は「この式はどこから出てきたんですか。。。」というお気持ちだった。

事実：凸関数は接線の集合（包絡線）で書ける

下の図のように、凸関数$f$は接線をたくさん集めるとその接線の包絡線として書ける。

すべての接線の情報を記憶しておけば、それは凸関数$f$を再構築できるから、$f$の情報と等価であることがわかる。

ネタバレするとこの「$f$の情報」と等価な「接線の情報たち」が凸共役関数$f^\ast$ である。
つまり、$f$を別の角度から見た、完全に等価な情報が$f^\ast$である。³

（視点を変えると数学的に別の情報が得られることがあるため、こんな情報の変換をしたりする）⁴

接線の情報たち

では接線の情報をすべて抽出してみる。
接線$y=px+c$の情報は 傾き$p$ と 切片$c$ だけである。
これらのペア$(p, c)$をすべての接線において情報として保持すればいいが、もっと簡潔に情報を示すいい方法がある。

凸関数の場合、先に傾き$p$を決めて接線を引こうとすると、切片$c$は自動的に一意に決定される（ちょっと考えてみると何となくわかると思う⁵）。
なので、$c$は傾き$p$の関数$c(p)$とかける。

$p$が決まれば$c(p)$の値は自動的に決まるので、接線の情報としてすべてのペア$(p, c)$を保持しておく必要はなく、関数$c(p)$だけあればすべての接線の情報は一意に復元でき、$f$は復元できることになる。

ネタバレすると この関数$c(p)$ が大体${f^\ast}(p)$である。 厳密には$f^\ast(p) = -c(p)$で定義される。

c(p)の式の導出

では具体的に$c(p)$はどうやって計算するのか？
$f(x)$と$c(p)$の関係式を考えて導出してみよう。

$c(p)$が具体的に得られているとする。
このとき凸関数$y=f(x)$と接線$y=px+c(p)$は一番近いところの距離が0である。
これを数式で書くと

\inf_x \bigl(f(x)-(px+c(p))\bigr) = 0

である。
($\inf$がわからない人はだいたい$\min$と同じなので、置き換えて考えてください)

このとき、$\inf_x$に関係ない項を外に出すと

\inf_x \bigl(f(x)-px\bigr) - c(p) = 0

\Leftrightarrow\quad c(p) = \inf_x (f(x)-px)

最後に、公式 $\inf_x (-g(x)) = -\sup_x (g(x))$ を使えば

c(p) = -\sup_x (px-f(x))

となる。
($\sup$がわからない人はだいたい$\max$と同じなので、置き換えて考えてください)

ルジャンドル変換の式の導出

ここまで来たらもう簡単である。
ルジャンドル変換の式は$f^\ast (p) = -c(p)$で定義され、

f^\ast(p) = \sup_x (px-f(x))

となる。

結局、$f^\ast$は$f$の「接線の情報たち」 であって、$f$を別の視点から見るための変換がルジャンドル変換ということになる。


ただ、気になることが1つある。「なぜに定義のところで$c(p)$にマイナスをつけたのか？」 である。
先に結論だけ書くと $f^\ast$から$f$に戻す逆変換も同じ式にするため である。

記事が長くなったし、だいたい話したいことは終わったので、この逆変換の導出などは補足のところに書いておきます。⁶

おわりに

• この記事のようにルジャンドル変換の導出を詳しく書いている記事や本が案外無い？（私の検索能力が低いだけかも）
• 誰かの助けになれば幸いです。

1. 一般に$f$は凸関数でなくてもルジャンドル変換は上の式で定義されるが、そのお気持ち説明が煩雑になるのでここでは凸関数としておく。 ↩

2. 多変数版のルジャンドル変換$f^\ast(\boldsymbol{p}) = \sup_\boldsymbol{x} (\boldsymbol{p}^T\boldsymbol{x}-f(\boldsymbol{x}))$ もあるけど、1変数版だけ気持ちが理解できれば大体同じ！（接線を接超平面に置き換えればOK）。したがって1変数版だけ説明します。 ↩

3. 実際は$f^\ast$が$f$と完全に等価な情報と言えるのは、$f$がいい感じのクラスの関数（真閉凸関数）だけである。このクラスでないと逆変換しても元に戻らない。 ↩

4. 例えばフーリエ変換が代表的な例である。一方でルジャンドル変換はmax-plus代数(トロピカル代数)におけるフーリエ変換と同等という話を聞いたことがあるが、どこで聞いたんだろう。。忘れました。 ↩

5. 証明はどのようにすればいいのかわかっていない。困った。 ↩

6. ${f^\ast(p)}$から${f(x)}$を導出する逆変換の式を考えてみる。
   $f(x)$と$c(p)$の関係式を考えて導出してみよう。
   $c(p)$が具体的に得られているとする。
   このとき凸関数$y=f(x)$と接線$y=px+c(p)$は傾きが同じところの距離が0である。
   これを数式で書くと $\inf_p \bigl(f(x)-(px+c(p))\bigr) = 0$
   $\inf_p$に依存しない項を外に出すと $f(x) + \inf_p \bigl(-(px+c(p))\bigr) = 0 \Leftrightarrow f(x) = -\inf_p \bigl(-(px+c(p))\bigr)$
   ここで公式 $\inf_x (-g(x)) = -\sup_x (g(x))$ を使えば $f(x) = \sup_p (px+c(p))$
   最後に${f^{\ast}}(p) = -c(p)$を代入すると $f(x) = \sup_p (px-f^\ast(p))$
   よって逆変換は $f(x) = \sup_p (px-f^\ast(p))$
   一方で順変換は $f^\ast(p) = \sup_x (px-f(x))$
   この2つを見比べると文字が違えど、同じ式である（対称な式である）ことがわかる。 ↩