凸共役性

数学において凸共役（とつきょうやく、英: convex conjugation）とは、ルジャンドル変換の一般化である。ルジャンドル＝フェンシェル変換あるいはフェンシェル変換としても知られる（アドリアン＝マリ・ルジャンドルとウェルナー・フェンシェル（英語版）の名にちなむ）。

定義

以下、特に断りがなければ、ベクトル空間はすべて実係数のものを考える。

定義 (凸共役性) ― $X$ を局所凸位相ベクトル空間（例えば有限次元のベクトル空間）とし、 $X^{*}$ を $X$ の双対空間とし、 $\langle \cdot ,\cdot \rangle :X^{*}\times X\to \mathbb {R} .$ を双対組とする。

このとき拡大実数に値を取る函数 $f:X\to \mathbb {R} \cup \{\pm \infty \}$ の凸共役（英: convex conjugate） $f^{*}:X^{*}\to \mathbb {R} \cup \{\pm \infty \}$ は、上限を用いて次のように定義される^[1]。

f^{*}\left(x^{*}\right):=\sup _{x\in X}\left\{\langle x^{*},x\rangle -f(x)\right\}.

直観的意味

上記の定義の直観的な意味を説明するため、ベクトル空間 $V$ の図形の支持超平面（英語版）を定義する。超平面 $\Pi \in V$ が集合 $S\in V$ の支持超平面（英: supporting hyperplane） $Π$ とは、 $Π$ は $S$ の閉包の点を少なくとも１つ含み、しかも $V$ を $Π$ で２つ切ったときに片方には $S$ の点が入っていない事をいう^[2]。

凸共役の直観的な意味を考えるため、 $f$ のエピグラフ

\mathrm {epi} f=\{(x_{0},y_{0})\in X\times \mathbb {R} \mid y_{0}\geq f(x_{0})\}

を考える。

定理 (凸共役の直観的意味^[3]) ― エピグラフ $\mathrm {epi} f\in X\times \mathbb {R}$ の「傾き」 $a^{*}$ の支持超平面

y=\langle a^{*},x\rangle +b

を考えると、

-b=f^{*}(a^{*})

証明

$(x_{0},y_{0})\in \mathrm {epi} f$ に対し $(x_{0},y_{0})\in X\times \mathbb {R}$ を通るアフィン写像

y=\langle a^{*},x-x_{0}\rangle +y_{0}=\langle a^{*},x\rangle +y_{0}-\langle a^{*},x_{0}\rangle

を考えると、支持超平面の定義から、 $b$ は上式の「 $y$ 切片」 $\langle a^{*},x\rangle +y_{0}-\langle a^{*},x_{0}\rangle$ の下限になるはずである。したがって

b=\inf _{(x_{0},y_{0})\in \mathrm {epi} f}\{y_{0}-\langle a^{*},x_{0}\rangle \}=\inf _{x_{0}\in X}\{f(x_{0})-\langle a^{*},x_{0}\rangle \}=-f^{*}(a^{*})

が成立する。ここで2つ目の等号はエピグラフの定義から従う。

すなわち、 $a^{*}\in X^{*}$ における $f$ の凸共役 $f^{*}(a^{*})$ は「傾き」 $a^{*}$ の支持超平面の「 $y$ 切片」 $b$ にマイナスをつけたものと解釈できる。

滑らかな場合

$X$ が有限次元のベクトル空間で、 $f$ が滑らかな凸関数であるとき、傾き $x^{*}$ の支持超平面を接平面として持つ点を $x$ とすると、すなわち

x^{*}=\mathrm {grad} f(x)

となる点を $x$ とすると、 $f$ の凸性からその $x$ において $\sup$ が達成されるので、

f^{*}\left(x^{*}\right)=\langle x^{*},x\rangle -f(x)

が成立する。よってこの場合には、凸共役は通常のルジャンドル変換に一致する。

基本的性質

本節では $X$ をノルム空間（例えば有限次元の計量ベクトル空間）とし、 $f,g~:~X\to \mathbb {R} \cup \{\pm \infty \}$ を関数とする。

前述のように凸共役は直観的には支持超平面によって特徴づけられるが、集合 $S$ の支持超平面は、 $S$ の閉包の支持超平面や $S$ の凸包の支持超平面と一致するので、以下が成立する：

定理 ―

f^{*}=({\bar {f}})^{*}=({\overline {\mathrm {conv} }}f)^{*}

が成立する^[4]。ここで

${\bar {f}}$ はエピグラフ $\mathrm {epi} {\bar {f}}$ が $f$ のエピグラフの閉包 ${\overline {(\mathrm {epi} f)}}$ に一致する関数。
${\overline {\mathrm {conv} }}f$ はエピグラフ $\mathrm {epi} ({\overline {\mathrm {conv} }}f)$ が $f$ エピグラフの凸包の閉包 ${\overline {\mathrm {conv} (\mathrm {epi} f)}}$ に一致する関数。

${\bar {f}}$ 、 ${\overline {\mathrm {conv} }}f$ は一意にwell-definedされる。

また凸共役の定義から明らかに次が従う：

定理 (フェンシェル・ヤングの不等式) ― 任意の $x\in \mathrm {dom} f$ 、 $x^{*}\in X^{*}$ に対し、

f(x)+f^{*}(x^{*})\geq \langle x^{*},x\rangle

。

が成立する^[4]。等号成立の必要十分条件は $x^{*}\in \partial f$ である^[4]。ここで、

$\mathrm {dom} f:=\{x\in X\mid f(x)\neq \pm \infty \}$
$\partial f:=\{v\in X\mid \forall y\in X~:~f(y)\geq f(x)+\langle v,y-x\rangle \}$

上記の不等式を用いると、次が成立する事を簡単に示せる：

定理 ― 任意の $x\in X$ に対し、以下が成立する^[4]：

f^{**}(x)\leq f(x)

一般には $f^{**}(x)=f(x)$ は成立しないが、次節で $f^{**}(x)=f(x)$ が成立する条件を説明する。さらに以下が成立する：

定理 ―

f>g\Rightarrow f^{*}<g^{*}

が成立する^[4]。ここで

$f>g:\!\!\iff \forall x\in X~:~f(x)>g(x)$

二重共役

本節でも $X$ をノルム空間とする。凸共役を二度取った $f^{**}(x)$ は元の $f(x)$ に一致する事は保証されない（なお、 $f^{**}(x)=f(x)$ と違い、 $f^{***}(x^{*})=f^{*}(x^{*})$ は無条件に成立する^[5]）。しかし以下が成立する事を示せる：

定理 ― ${\overline {\mathrm {conv} }}f$ がプロパーなら、任意の $x\in X$ に対し、以下が成立する^[4]：

f^{**}(x)={\overline {\mathrm {conv} }}f(x)

ここで関数 $g~:~X\to \mathbb {R} \cup \{\pm \infty \}$ がプロパーであるとは、 $g$ が恒等的に $\infty$ を取らない事を指す。

${\overline {\mathrm {conv} }}f$ は凸関数なので、プロパーな関数 $f$ が $f^{**}(x)=f(x)$ を満たすのは $f$ が凸な場合に限られる。そのような関数に対して ${\overline {\mathrm {conv} }}f(x)=f(x)$ が成立する条件を具体的に書き表す事で以下が成立する事がわかる：

定理 (フェンシェル＝モローの定理) ― プロパーな凸関数 $f$ が任意の $x\in X$ において $f^{**}(x)=f(x)$ を満たす必要十分条件は、 $f$ が下半連続な事である^[4]。

上記の定理は各点毎に成立する。すなわち、プロパーな凸関数 $f$ が点 $x\in X$ において $f^{**}(x)=f(x)$ を満たす必要十分条件は、 $f$ が $x$ において下半連続な事である^[4]。

なお、 $X$ がバナッハ空間であれば凸関数 $f$ が下半連続であれば $\mathrm {dom} f$ の内点で連続である^[6]。とくに有限次元のベクトル空間であれば、（下半連続性の仮定がなくとも） $\mathrm {dom} f$ の内点で連続である事が示せる^[7]。よってこの場合、下半連続性を問われるのは境界点のみである。

また、（バナッハ空間とは限らない）ノルム空間の凸部分集合上定義された凸関数は一点で連続であればその凸部分集合上の全点で連続である事も知られている^[6]。

フェンシェルの双対性

本節では、凸共役を最適化問題に応用するうえで鍵となるフェンシェルの双対性について説明する。

定理のステートメント

まずは応用について考えず、天下り的に定理を与える。

$X$ 、 $Y$ をノルム空間とし、 $T~:~X\to Y$ を有界線形作用素（例えば $X$ 、 $Y$ が有限次元の計量ベクトル空間で $T$ が線形写像）とし、さらに $f~:~X\to \mathbb {R} \cup \{\pm \infty \}$ 、 $g~:~Y\to \mathbb {R} \cup \{\pm \infty \}$ を２つの関数とする。さらに下限 $p$ を求める問題と上限 $d$ を求める問題

p=\inf _{x\in X}(f(x)+g(Tx))

d=\sup _{y^{*}\in Y^{*}}(-f^{*}(T^{*}y)-g^{*}(-y^{*}))

を考える。これらの問題をフェンシェル問題（英: Fenchel problem）^[8]といい、後者を前者の（そして前者を後者の）双対問題という。このとき前述したフェンシェル・ヤングの不等式から次が成立する。

定理 (弱双対性) ― 記号を上述のように定義するとき、

p\geq d

が成立する^[9]。

さらに次が成立する：

定理 (フェンシェルの双対性定理) ― 記号を上述のように定義するとき、特に $X$ 、 $Y$ がバナッハ空間（例えば有限次元の計量ベクトル空間）で、 $f$ 、 $g$ が凸関数で、しかも以下の1, 2のいずれかが成立すれば上式で等号が成立する^[10]：

$f$ 、 $g$ がいずれも下半連続で、しかも $0\in \mathrm {core} (\mathrm {dom} g-T\mathrm {dom} f)$ が成立する。
$T\mathrm {dom} f\cap \mathrm {cont} g\neq \emptyset$

さらに上述の等号成立条件を満たし、しかも $d$ が有限であれば、上限 $d=\sup _{y^{*}\in Y^{*}}(-f^{*}(T^{*}y)-g^{*}(-y^{*}))$ を達成する $y^{*}$ が存在する^[10]。

ここで集合 $F\subset X$ に対し、

\mathrm {core} F:=\{x\in X\mid \forall h\mathrm {s.t.} \|h\|=1\exists \delta >0\forall t\in [0,\delta ]~:~x+th\in F\}

であり^[11]、 $\mathrm {cont} g$ は $g$ の連続な点全体の集合である^[11]。

応用

$C\subset X$ 、 $D\subset Y$ を閉凸集合とし、以下の問題を考える：

${\begin{array}{ll}{\underset {x\in C}{\text{minimize}}}&F(x)\\{\text{subject to }}&Tx\in D\end{array}}$ …問題1

すなわち、 $x\in C$ 、 $Tx\in D$ という条件下 $F(x)$ の最小値 $p$ を求めよ、という問題である。

上記の問題はフェンチェル問題の特殊な場合とみなす事ができる。実際、集合 $A$ に対し、その指示関数（英: indicator function）を

\iota _{A}(x):={\begin{cases}0&{\text{if }}x\in A\\\infty &{\text{otherwise}}\end{cases}}

と定義し、

f(x)=F(x)+\iota _{C}(x)

g(x)=\iota _{D}(x)

とすると、問題1はフェンチェル問題 $p=\inf _{x\in X}(f(x)+g(Tx))$ に一致する^[11]。

したがって $p$ をその双対問題 $d=\sup _{y^{*}\in Y^{*}}(-f^{*}(T^{*}y)-g^{*}(-y^{*}))$ の $d$ で下から抑えたり、等号成立条件が成り立っていれば双対問題の方を具体的に調べる事で $p=d$ を求めたりする事が可能になる。

凸共役の例

アフィン函数

f(x)=\left\langle a,x\right\rangle -b,\,a\in \mathbb {R} ^{n},b\in \mathbb {R}

の凸共役は

f^{\star }\left(x^{*}\right)={\begin{cases}b,&x^{*}=a\\+\infty ,&x^{*}\neq a.\end{cases}}

である。冪函数

f(x)={\frac {1}{p}}|x|^{p},\,1<p<\infty

の凸共役は

f^{\star }\left(x^{*}\right)={\frac {1}{q}}|x^{*}|^{q},\,1<q<\infty

である。ここで ${\tfrac {1}{p}}+{\tfrac {1}{q}}=1$ である。

絶対値函数

f(x)=\left|x\right|

の凸共役は

f^{\star }\left(x^{*}\right)={\begin{cases}0,&\left|x^{*}\right|\leq 1\\\infty ,&\left|x^{*}\right|>1\end{cases}}

である。指数函数 $f(x)=\,\!e^{x}$ の凸共役は

f^{\star }\left(x^{*}\right)={\begin{cases}x^{*}\ln x^{*}-x^{*},&x^{*}>0\\0,&x^{*}=0\\\infty ,&x^{*}<0\end{cases}}

である。指数函数の凸共役とルジャンドル変換は、凸共役の定義域が厳密に大きいことを除いて一致する。ルジャンドル変換は正の実数に対してのみ定義されるためである。

期待ショートフォール（リスク平均値）との関係

F を確率変数 X の累積分布函数とする。このとき、部分積分により

f(x):=\int _{-\infty }^{x}F(u)\,du=\operatorname {E} \left[\max(0,x-X)\right]=x-\operatorname {E} \left[\min(x,X)\right]

は次の凸共役を持つ。

f^{\star }(p)=\int _{0}^{p}F^{-1}(q)\,dq=(p-1)F^{-1}(p)+\operatorname {E} \left[\min(F^{-1}(p),X)\right]=pF^{-1}(p)-\operatorname {E} \left[\max(0,F^{-1}(p)-X)\right].

順序

特別な解釈により次の変換が考えられる。

f^{\text{inc}}(x):=\arg \sup _{t}\,t\cdot x-\int _{0}^{1}\max\{t-f(u),0\}\,\mathrm {d} u,

これは初期函数 f の非減少な書き換えである。特に、f に対する $f^{\text{inc}}=f$ は非減少である。

性質

閉凸函数の凸共役は再び閉凸函数である。多面体的凸函数（多面体的エピグラフを持つ凸函数）の凸共役は、再び多面体的凸函数である。

凸性

二つの函数 $f_{0}$ と $f_{1}$ および数 $0\leq \lambda \leq 1$ に対し、次の凸関係が成立する。

\left((1-\lambda )f_{0}+\lambda f_{1}\right)^{\star }\leq (1-\lambda )f_{0}^{\star }+\lambda f_{1}^{\star }

この演算 $\star$ はそれ自身が凸写像である。

極小畳み込み

二つの函数 f と g の極小畳み込み（infimal convolution）は、次で定義される（epi-sum とも呼ばれる）：

\left(f\Box g\right)(x)=\inf \left\{f(x-y)+g(y)\mid y\in \mathbb {R} ^{n}\right\}.

f₁, …, f_m は Rⁿ 上の真凸かつ下半連続な函数とする。このとき、これらの極小畳み込みは凸かつ下半連続である（が、必ずしも真凸ではない）^[12]。さらに次が成立する。

\left(f_{1}\Box \cdots \Box f_{m}\right)^{\star }=f_{1}^{\star }+\cdots +f_{m}^{\star }.

二つの函数の極小畳み込みは、次のような幾何学的解釈がある：二つの函数の極小畳み込みの（厳密な）エピグラフは、それらの函数の（厳密な）エピグラフのミンコフスキー和（英語版）である^[13]。

最大化引数

函数 $f$ が微分可能であるなら、その導函数は凸共役の計算における最大化引数（maximizing argument）である。すなわち、

f^{\prime }(x)=x^{*}(x):=\arg \sup _{x^{\star }}{\langle x,x^{\star }\rangle }-f^{\star }(x^{\star })

と

f^{\star \prime }(x^{\star })=x(x^{\star }):=\arg \sup _{x}{\langle x,x^{\star }\rangle }-f(x);

が成り立つ。したがって

x=\nabla f^{\star }(\nabla f(x)),

x^{\star }=\nabla f(\nabla f^{\star }(x^{\star })),

であり、さらに次が成立する。

f^{\prime \prime }(x)\cdot f^{\star \prime \prime }(x^{\star }(x))=1,

f^{\star \prime \prime }(x^{\star })\cdot f^{\prime \prime }(x(x^{\star }))=1.

スケーリング性

ある $\gamma >0$ に対し、 $\,g(x)=\alpha +\beta x+\gamma \cdot f(\lambda x+\delta )$ であるなら、次が成り立つ。

g^{\star }(x^{\star })=-\alpha -\delta {\frac {x^{\star }-\beta }{\lambda }}+\gamma \cdot f^{\star }\left({\frac {x^{\star }-\beta }{\lambda \gamma }}\right).

さらにパラメータ α が追加される場合は、次が成り立つ。

f_{\alpha }(x)=-f_{\alpha }({\tilde {x}}).

ここで ${\tilde {x}}$ は最大化引数であるように選ばれる。

線型変換の下での挙動

A を X から Y への有界線型作用素とする。X 上の任意の凸函数 f に対して、次が成り立つ。

\left(Af\right)^{\star }=f^{\star }A^{\star }

ここで

(Af)(y)=\inf\{f(x):x\in X,Ax=y\}

は f の A に関する原像であり、A^* は A の共役作用素である^[14]。

閉凸函数 f は、ある与えられた直交線型変換の集合 G に関して対称である、すなわち

f\left(Ax\right)=f(x),\;\forall x,\;\forall A\in G

であるための必要十分条件は、凸共役 f^* が G に関して対称であることである。

代表的な凸共役の表

次の表では、多くの有名な函数のルジャンドル変換で、有用な性質を持つものが示されている^[15]。

さらに見る

,

...

$g(x)$	$\operatorname {dom} (g)$	$g^{}(x^{})$	$\operatorname {dom} (g^{*})$
$f(ax)$ (where $a\neq 0$ )	$X$	$f^{}\left({\frac {x^{}}{a}}\right)$	$X^{*}$
$f(x+b)$	$X$	$f^{}(x^{})-\langle b,x^{*}\rangle$	$X^{*}$
$af(x)$ (where $a>0$ )	$X$	$af^{}\left({\frac {x^{}}{a}}\right)$	$X^{*}$
$\alpha +\beta x+\gamma \cdot f(\lambda x+\delta )$	$X$	$-\alpha -\delta {\frac {x^{}-\beta }{\lambda }}+\gamma \cdot f^{}\left({\frac {x^{*}-\beta }{\gamma \lambda }}\right)\quad (\gamma >0)$	$X^{*}$
${\frac {\|x\|^{p}}{p}}$ (where $p>1$ )	$\mathbb {R}$	${\frac {\|x^{*}\|^{q}}{q}}$ (where ${\frac {1}{p}}+{\frac {1}{q}}=1$ )	$\mathbb {R}$
${\frac {-x^{p}}{p}}$ (where $0<p<1$ )	$\mathbb {R} _{+}$	${\frac {-(-x^{*})^{q}}{q}}$ (where ${\frac {1}{p}}+{\frac {1}{q}}=1$ )	$\mathbb {R} _{--}$
${\sqrt {1+x^{2}}}$	$\mathbb {R}$	$-{\sqrt {1-(x^{*})^{2}}}$	$[-1,1]$
$-\log(x)$	$\mathbb {R} _{++}$	$-(1+\log(-x^{*}))$	$\mathbb {R} _{--}$
$e^{x}$	$\mathbb {R}$	${\begin{cases}x^{}\log(x^{})-x^{}&{\text{if }}x^{}>0\\0&{\text{if }}x^{*}=0\end{cases}}$	$\mathbb {R} _{+}$
$\log \left(1+e^{x}\right)$	$\mathbb {R}$	${\begin{cases}x^{}\log(x^{})+(1-x^{})\log(1-x^{})&{\text{if }}0<x^{}<1\\0&{\text{if }}x^{}=0,1\end{cases}}$	$[0,1]$
$-\log \left(1-e^{x}\right)$	$\mathbb {R}$	${\begin{cases}x^{}\log(x^{})-(1+x^{})\log(1+x^{})&{\text{if }}x^{}>0\\0&{\text{if }}x^{}=0\end{cases}}$	$\mathbb {R} _{+}$