凸関数 - ややプログラム紀行

<a href="https://blankbanshee.bandcamp.com/album/4d">4D Blank Banshee</a>

昔からなんとなく凸解析や双対全般に対して苦手意識みたいなものがあって、おそらく一番の理由は僕自身が凸関数のことを舐めているからだと思う

と言うのも、"凸"関数や"線形"計画法みたいなものは使える状況が限られるような印象が名前から感じられて、今までちゃんと授業なりで勉強をしたことがなかったから*1

ただ、厄介なことにこいつらはたまに必要になる瞬間があって、しかも凸関数/線形計画法は考える問題を限定しているがゆえとても歴史が深く、知識が必要な時にその分野を知っている人と知らない人だとかなり差がつくことになる

例えば、最適輸送の勉強中に次の定理を見かけたことがある*2

(Fenchel-Rockafellar) Let $X$ be a normed space and let $\Theta, \Sigma: X \to (-\infty, \infty$ ] be convex and lower semicontinuous. If there exists $x_0 \in \mathrm{Dom}(\Theta) \bigcap \mathrm{Dom}(\Sigma)$ such that $\Theta$ is continuous in $x_0$ , then
$\displaystyle \inf_{x \in X} \left\{ \Theta(x) + \Sigma(x)\right\} = \sup_{x^* \in X^*} \left\{-\Theta^*(-x^*) - \Sigma^*(x^*) \right\}.$

Convex Optimization – Boyd and Vandenbergheを読んだことはあるけど、なんか自分が知ってるのと違うぞ！！

この定理は最適輸送におけるKantorovich-Rubinstein双対を示すために使われていて、この双対は確率分布が離散的ならよくあるLagrange双対から示されることを踏まえると、↑の定理は自分の知っているLagrange双対より一般的な形なんだろなという気はしてくる

当時これを読んだ時はよく分からないけど成り立つんだろう、とスルーしてたけど、最近研究でまた凸関数を見かけることがあって、いい加減このモヤモヤを解消したくなり少し詳し目の凸解析の本を参照してみた
link.springer.com

自分は勉強しててすぐ脇道に外れちゃう癖があるので今回も↑の定理についてだけ調べようと思っていたのだけど、本の書き方が複雑すぎて結局結構読んでしまった気がする...

以降はこの本を読んで分かったことをめちゃくちゃフィーリングで書こうと思う

まず、考える空間は基本的に実ヒルベルト空間 $\mathcal{H}$ で、主な対象はproper lower semicontinuous convexな関数 $f: \mathcal{H} \to (-\infty, \infty$ ]となる
properとは値域に $-\infty$ を含まないこと、lower semicontinuousは任意の点 $x \in \mathcal{H}$ で $f(x) \leq \varliminf_{y \to x} f(x)$ が成り立つことを意味するのだけど、「lower semicontinuous convexである」とは「エピグラフが凸かつ閉である」と言い換えられる

proper lower semicontinuous convexな関数 $f$ はとても良い性質を持っていて、 $f$ はaffine minorants、すなわち $f$ を下から抑えるような一次関数によって特徴づけられる
幾何的なイメージとしては、凸関数に接する一次関数を考えて、傾きを徐々に大きくしていくことで一次関数が凸関数の下を滑っていくような感じ

このことから、 $f$ の双対として任意の $u \in \mathcal{H}$ に対する「傾き $u$ の最大のaffine minorants $f \geq \langle \cdot \mid u\rangle - \mu$ 」が分かればよく、これが所謂Legendre変換、もしくはFenchel共役につながる

$\displaystyle f^*: \mathcal{H} \to [-\infty,\infty]: u \mapsto \sup_{x \in \mathcal{H}} \left(\langle x \mid u \rangle - f(x) \right)$

$f^*$ を使うことで「傾き $u$ の最大のaffine minorants」は $\langle \cdot \mid u \rangle - f^*(u)$ として表せる

面白いことに、convexとは限らない任意の関数 $f: \mathcal{H} \to [-\infty, \infty$ ]に対して $f^*$ は必ずlower semicontinuous convexになり、特に $f$ がproper lower semicontinuous convexならば $f^{**} = f$ が成り立つ:*3

(Fenchel-Moreau) properな $f: \mathcal{H} \to (-\infty, +\infty$ ]に対して、 $f$ がlower semicontinuous convexであることと $f = f^{**}$ は同値

ちなみに、このFenchel-Moreau定理を少し発展させることで、convexとは限らない任意*4のproperな関数 $f: \mathcal{H} \to (-\infty, +\infty$ ]について $f^{**}$ は $f$ のlower semicontinuous convex envelopeになることがわかる:

$\displaystyle f^{**} = \breve{f} = \sup \left\{ g: \text{lower semicontinuous convex} \mid g \leq f \right\}$

ここからは今回本を読んで初めて知った

convexと限らない任意の関数 $f,g: \mathcal{H} \to (-\infty, \infty$ ]について、素直に $(f + g)^* = f^* + g^*$ とすることはできない
では $(f + g)^*$ は何に対応するのだろう？

唐突だがinfimal convolutionと言う概念を導入する: $f,g$ のinfimal convolutionは

$\displaystyle f\ \Box\ g: \mathcal{H} \to [-\infty, \infty]: x \mapsto \inf_{y \in \mathcal{H}} \left(f(y) + g(x-y) \right)$

として定義され、全ての $x \in \mathcal{H}$ について上式のinfがminになる時に $f\ \Box\ g$ はexactであるといい $f \boxdot g$ と書く

infimal convolution自体とても奥が深いものなのだけど、Legendre共役との関連で言うと次の特筆すべき性質を持つ:

任意の $f,g$ について $(f\ \Box\ g)^* = f^* + g^*$

proper lower semicontinuous convexな $f,g$ が $\mathrm{dom} f \bigcap \mathrm{dom} g \neq \varnothing$ を満たすなら、 $f^*\ \Box\ g^*$ はconvexであり $(f+g)^* = (f^*\ \Box\ g^*)\breve{}$ が成り立つ

ここで $(f^*\ \Box\ g^*)\breve{}$ は先ほどチラッと出てきたlower semicontinuous convex envelope

前者の性質については、 $f,g$ がproper lower semicontinuous convexなら $f = f^{**}, g = g^{**}$ であることから $(f^*\ \Box\ g^*)^* = f^{**} + g^{**} = f + g$ となる
かなり惜しいところまで来ているが絶妙に非対称な関係になっており、これが綺麗に $(f+g)^* = f^*\ \Box\ g^*$ の関係で結ばれるためには $f^*\ \Box\ g^*$ がlower semicontinuousである必要がある

残念なことに(?)、 $f^*\ \Box\ g^*$ がlower semicontinuousとなるためにはさらに条件が必要となる:

(Attouch-Brezis) proper lower semicontinuous convexな $f,g$ が
$\displaystyle 0 \in \mathrm{sri}\left(\mathrm{dom} f - \mathrm{dom} g\right)$

を満たすなら $(f+g)^* = f^* \boxdot g^*$

sriはstrong relative interiorの略だが、謎の条件 $0 \in \mathrm{sri}\left(\mathrm{dom} f - \mathrm{dom} g\right)$ は「 $\mathrm{dom} f - \mathrm{dom} g$ のconical hullが閉な線形部分空間である」と言い換えることができる

「 $(f+g)^*$ の正体が分かったところで何が言えるんだよ！？」となるかもしれないが、この定理から次のように冒頭で述べたFenchel-Rockafellar双対につながっていく

$\inf_{x \in \mathcal{H}} f(x) + g(x)$ を解きたい主問題とすると、Legendre変換の定義よりこれは $-(f+g)^*(0)$ を求めるのと同じであることがわかる
すると先ほどのAttouch-Brezis定理より、 $0 \in \mathrm{sri}\left(\mathrm{dom} f - \mathrm{dom} g\right)$ が満たされるのであれば $-(f+g)^*(0) = -(f^* \boxdot g^*)(0)$ が成り立ち、この右辺はinfimal convolutionの定義より $-\min_{x \in \mathcal{H}} f^*(-x) + g^*(x)$ という双対問題を解こうとしているのに等しい、となるわけである
特に $\mathrm{cont} f \bigcap \mathrm{dom} g \neq \varnothing$ が成り立てば $0 \in \mathrm{sri}\left(\mathrm{dom} f - \mathrm{dom} g\right)$ となることが知られているので、ここまで来てようやく冒頭の定理を復元することができた

主問題/双対問題と聞くと次のような感じのLagrange双対問題を思い浮かべることが多いと思う
関数 $f_0,f_1,\dots,f_m$ に対して主問題が

$\displaystyle \min_{x \in \mathcal{H}, f_1(x)\leq 0,\dots,f_m(x)\leq 0} f_0(x)$

であるとき、Lagrangianを $L(x,\lambda) = f_0(x) + \sum_{i = 1}^m \lambda_i f_i(x)$ として定め、

$\displaystyle g(\lambda) = \inf_{x \in \mathcal{H}} L(x, \lambda)$

をLagrange双対問題と呼ぶ
すると、Lagrange双対問題の解は常に主問題の解以下となり(弱双対)、適切な条件、例えば $f_0,f_1,\dots,f_m$ がconvexでSlater条件が成り立つときに両者は一致する(強双対)

実はこのLagrange双対問題の強双対性に関してもAttouch-Brezis定理から示すことができる
具体的な話は長くなってしまうので端折るが、方針としては次のような感じだ:
まず制約を満たす集合を $C = \{ x \in \mathcal{H} \mid g_1(x) \leq 0, \dots, g_m(x) \leq 0\}$ と置き、関数 $f,g$ を

$\displaystyle f(x) = \begin{cases} 0 & \text{if $x \in C$} \\ +\infty & \text{otherwise} \end{cases}$

かつ $g = f_0$ としてみる
すると主問題は $\min_{x \in \mathcal{H}} f(x) + g(x)$ とお馴染みの形になり、Slater条件から

$\displaystyle 0 \in \mathrm{int}\left(C - \mathrm{dom}f_0\right) \subset \mathrm{sri}\left(C - \mathrm{dom}f_0\right) = \mathrm{sri}\left(\mathrm{dom} f - \mathrm{dom} g\right)$

が満たされるので、無事Attouch-Brezis定理より強双対性が成り立つという感じになる

最後が少しぼかし気味になったのはLagrange双対問題の形にたどり着くにはsubdifferentialの説明も必要だからで、今回本を読んでその辺りの知識も結構ためになったからいつか機会があればメモしときたい

*1:もっと言うなら線形代数も最初は軽視してた気がする

*2:Lectures on Optimal Transport | SpringerLink

*3:凸関数がその傾きによって特徴づけられることは確かにわかるけれど、2回同じ操作(Legendre変換)をすることで元の関数に戻ると言うのはいつ聞いても不思議に感じる、どういう歴史的経緯でこの事実が見つかったのか知りたい

*4:正確にはさらに $\mathrm{dom}f^* \neq \varnothing$ なら