多変数の凸関数・凹関数の劣勾配と劣微分

凸関数の劣勾配と劣微分

凸集合上に定義された多変数関数\(f:\mathbb{R} ^{n}\supset X\rightarrow \mathbb{R} \)が凸関数であるものとします。この関数\(f\)のエピグラフは、\begin{equation*}\mathrm{epi}\left( f\right) =\left\{ \left( x,y\right) \in X\times \mathbb{R} \ |\ y\geq f\left( x\right) \right\}
\end{equation*}と定義されます。関数\(f\)の定義域の内点\(x_{0}\in X^{i}\)を任意に選ぶと、\begin{equation*}\left( x_{0},f\left( x_{0}\right) \right) \in \mathrm{epi}\left( f\right)
\end{equation*}が明らかに成り立ちます。加えて、この点\(\left( x_{0},f\left( x_{0}\right) \right) \)はエピグラフ\(\mathrm{epi}\left( f\right) \)の境界点です。なぜなら、任意の\(\varepsilon >0\)について、点\(\left( x_{0},f\left( x_{0}\right) \right) \)を中心とする半径\(\varepsilon \)の開近傍\(N_{\varepsilon }\left( x_{0},f\left(x_{0}\right) \right) \)はエピグラフ\(\mathrm{epi}\left( f\right) \)の内部および外部の双方と交わるからです。

凸関数のエピグラフは凸集合であるため\(\mathrm{epi}\left( f\right) \)は凸集合です。したがって、支持超平面定理より、凸集合\(\mathrm{epi}\left( f\right) \)とその境界点\(\left( x_{0},f\left( x_{0}\right) \right) \)を分離する超平面が存在するため、以下の条件\begin{equation*}\forall \left( x,y\right) \in \mathrm{epi}\left( f\right) :\left( \alpha
,\beta \right) \cdot \left( x_{0},f\left( x_{0}\right) \right) \leq \left(
\alpha ,\beta \right) \cdot \left( x,y\right)
\end{equation*}すなわち、\begin{equation}
\forall \left( x,y\right) \in \mathrm{epi}\left( f\right) :\alpha \cdot
x_{0}+\beta f\left( x_{0}\right) \leq \alpha \cdot x+\beta y \quad \cdots (1)
\end{equation}を満たす非ゼロの法線ベクトル\(\left( \alpha ,\beta \right)=\left( \alpha _{1},\cdots ,\alpha _{n},\beta \right) \in \mathbb{R} ^{n}\backslash \left\{ 0\right\} \)が存在することが保証されます。

法線ベクトル\(\left( \alpha ,\beta\right) \)は非ゼロベクトルであるため、少なくとも一方の成分が非ゼロです。以下では\(\beta >0\)であることを示します。\(\beta <0\)が成り立つものと仮定します。\(\left( 1\right) \)において点\(x\)を固定した上で、両辺について\(y\rightarrow +\infty \)のときの極限をとると、左辺は有限な実数\(\alpha \cdot x_{0}+\beta f\left( x_{0}\right) \)へ収束する一方で、\(\beta <0\)より右辺は負の無限大\(-\infty \)へ発散するため矛盾です。したがって背理法より\(\beta \geq 0\)であることが明らかになりました。エピグラフ上の点\(\left( x,y\right) \in \mathrm{epi}\left( f\right) \)の中でも、\begin{equation*}y=f\left( x\right)
\end{equation*}を満たすものに注目すると、これと\(\left( 1\right) \)より、\begin{equation*}\forall x\in X:\alpha \cdot x_{0}+\beta f\left( x_{0}\right) \leq \alpha
\cdot x+\beta f\left( x\right)
\end{equation*}すなわち、\begin{equation}
\forall x\in X:\beta \left[ f\left( x\right) -f\left( x_{0}\right) \right] \geq -\alpha \cdot \left( x-x_{0}\right) \quad \cdots (2)
\end{equation}を得ます。\(\beta =0\)が成り立つものと仮定すると、\begin{equation}\forall x\in X:0\geq -\alpha \cdot \left( x-x_{0}\right) \quad \cdots (3)
\end{equation}を得ます。仮定より\(x_{0}\)は\(X\)の内点であるため、点\(x\in X\)のとりかたによってベクトル\(x-x_{0}\)は任意の方向をとり得ます。それにも関わらず\(\left( 3\right) \)を成立させるためには\(\alpha =\left( 0,\cdots,0\right) \)である必要があります。つまり、\(\left( \alpha,\beta \right) =\left( 0,\cdots ,0,0\right) \)となりますが、これは\(\left( \alpha ,\beta\right) \)が非ゼロベクトルであることと矛盾です。したがって背理法より、\(\beta =0\)が成り立たないこと、すなわち\(\beta >0\)であることが示されました。すると\(\left( 2\right) \)より、\begin{equation*}\forall x\in X:f\left( x\right) -f\left( x_{0}\right) \geq -\frac{\alpha }{\beta }\cdot \left( x-x_{0}\right)
\end{equation*}を得ます。さらに、\begin{equation*}
c=-\frac{\alpha }{\beta }\in \mathbb{R} ^{n}
\end{equation*}とおくと、これを、\begin{equation*}
\forall x\in X:f\left( x\right) -f\left( x_{0}\right) \geq c\cdot \left(
x-x_{0}\right)
\end{equation*}と表現できます。

結論を整理しましょう。凸関数\(f:\mathbb{R} ^{n}\supset X\rightarrow \mathbb{R} \)の内点\(x_{0}\in X^{i}\)を任意に選んだ場合、以下の条件\begin{equation*}\forall x\in X:f\left( x\right) -f\left( x_{0}\right) \geq c\cdot \left(
x-x_{0}\right)
\end{equation*}を満たすベクトル\(c\in \mathbb{R} ^{n}\)の存在が保証されます。そこで、このベクトル\(c\)を凸関数\(f\)の内点\(x_{0}\)における劣勾配（subgradient）と呼びます。

先の議論より、凸関数\(f\)の内点\(x_{0}\)を選んだとき、その劣勾配は必ず存在します。その一方で、後に例示するように、劣勾配は一意的に定まるとは限りません。そこで、凸関数\(f\)の内点\(x_{0}\)における劣勾配をすべて集めてできる集合を、\begin{equation*}\partial f\left( x_{0}\right) =\left\{ c\in \mathbb{R} ^{n}\ |\ \forall x\in X:f\left( x\right) -f\left( x_{0}\right) \geq c\cdot
\left( x-x_{0}\right) \right\}
\end{equation*}で表記し、これを凸関数\(f\)の内点\(x_{0}\)における劣微分（subdifferential）と呼びます。凸関数\(f\)の内点\(x_{0}\)における劣勾配が存在することは劣微分\(\partial f\left( x_{0}\right) \)が非空集合であることを意味します。

凹関数の劣勾配と劣微分

凸集合上に定義された関数\(f:\mathbb{R} ^{n}\supset X\rightarrow \mathbb{R} \)が凹関数であるものとします。このとき、それぞれの\(x\in X\)に対して、\begin{equation*}\left( -f\right) \left( x\right) =-f\left( x\right)
\end{equation*}を定める関数\(-f:\mathbb{R} ^{n}\supset X\rightarrow \mathbb{R} \)を定義します。関数\(f\)が凹関数であることと関数\(-f\)が凸関数であることは必要十分であるため、凸集合の劣勾配に関する先の議論より、凸関数\(-f:\mathbb{R} ^{n}\supset X\rightarrow \mathbb{R} \)の内点\(x_{0}\in X^{i}\)を任意に選んだ場合、以下の条件\begin{equation*}\forall x\in X:\left[ -f\left( x\right) \right] -\left[ -f\left(
x_{0}\right) \right] \geq c\cdot \left( x-x_{0}\right)
\end{equation*}を満たすベクトル\(c\in \mathbb{R} ^{n}\)の存在が保証されます。これを変形すると、\begin{equation*}\forall x\in X:f\left( x_{0}\right) -f\left( x\right) \geq c\cdot \left(
x-x_{0}\right)
\end{equation*}すなわち、\begin{equation*}
\forall x\in I:f\left( x\right) -f\left( x_{0}\right) \leq -c\cdot \left(
x-x_{0}\right)
\end{equation*}を得ます。ベクトル\(c\)が存在する場合にはベクトル\(-c\)もまた存在します。

結論を整理しましょう。凹関数\(f:\mathbb{R} ^{n}\supset X\rightarrow \mathbb{R} \)の内点\(x_{0}\in X^{i}\)を任意に選んだ場合、以下の条件\begin{equation*}\forall x\in X:f\left( x\right) -f\left( x_{0}\right) \leq c\cdot \left(
x-x_{0}\right)
\end{equation*}を満たすベクトル\(c\in \mathbb{R} ^{n}\)の存在が保証されます。そこで、このベクトル\(c\)を凹関数\(f\)の内点\(x_{0}\)における劣勾配と呼びます。

先の議論より、凹関数\(f\)の内点\(x_{0}\)を選んだとき、その劣勾配は必ず存在します。その一方で、後に例示するように、劣勾配は一意的に定まるとは限りません。そこで、凹関数\(f\)の内点\(x_{0}\)における劣勾配をすべて集めてできる集合を、\begin{equation*}\partial f\left( x_{0}\right) =\left\{ c\in \mathbb{R} ^{n}\ |\ \forall x\in X:f\left( x\right) -f\left( x_{0}\right) \leq c\cdot
\left( x-x_{0}\right) \right\}
\end{equation*}で表記し、これを凹関数\(f\)の内点\(x_{0}\)における劣微分と呼びます。凹関数\(f\)の内点\(x_{0}\)における劣勾配が存在することは劣微分\(\partial f\left( x_{0}\right) \)が非空集合であることを意味します。

微分可能な凸関数・凹関数の劣勾配

先の例が示唆するように、凸関数や凹関数が定義域の内点において微分可能ではない場合にも、そこでの劣勾配は存在します。特に、凸関数が内点において全微分可能である場合、その内点における劣勾配は勾配ベクトルと一致するとともに、他に劣勾配が存在しないことが保証されます。多変数の凸関数が全微分可能な内点については、勾配ベクトルと劣微分が実質的に一致するということです。

凹関数についても同様の議論が成立します。つまり、凹関数が内点において全微分可能である場合、その内点における劣勾配は勾配ベクトルと一致するとともに、他に劣勾配が存在しないことが保証されます。凹関数が全微分可能な内点については、勾配ベクトルと劣微分が実質的に一致するということです。

演習問題