教材一覧
教材一覧
教材検索

凸関数・凹関数

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

目次

Twitter
Mailで保存

凸関数の劣勾配と劣微分

区間上に定義された関数\(f:\mathbb{R} \supset I\rightarrow \mathbb{R} \)が凸関数であるものとします。この関数\(f\)のエピグラフは、\begin{equation*}\mathrm{epi}\left( f\right) =\left\{ \left( x,y\right) \in I\times \mathbb{R} \ |\ y\geq f\left( x\right) \right\}
\end{equation*}と定義されます。関数\(f\)の定義域の内点\(x_{0}\in I^{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) +\varepsilon \right) \)は\(\mathrm{epi}\left( f\right) \)の内点である一方で点\(\left( x_{0},f\left(x_{0}\right) -\varepsilon \right) \)は\(\mathrm{epi}\left( f\right) \)の外点であり、したがって点\(\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
x_{0}+\beta f\left( x_{0}\right) \leq \alpha x+\beta y \quad \cdots (1)
\end{equation}を満たす非ゼロの法線ベクトル\(\left( \alpha ,\beta \right) \in \mathbb{R} ^{2}\backslash \left\{ \left( 0,0\right) \right\} \)が存在することが保証されます(上図)。

法線ベクトル\(\left( \alpha ,\beta\right) \)は非ゼロベクトルであるため、少なくとも一方の成分が非ゼロです。以下では\(\beta >0\)であることを示します。\(\beta <0\)が成り立つものと仮定します。\(\left( 1\right) \)において点\(x\)を固定した上で、両辺について\(y\rightarrow +\infty \)のときの極限をとると、左辺は有限な実数\(\alpha 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 I:\alpha x_{0}+\beta f\left( x_{0}\right) \leq \alpha x+\beta
f\left( x\right)
\end{equation*}すなわち、\begin{equation}
\forall x\in I:\beta \left[ f\left( x\right) -f\left( x_{0}\right) \right] \geq -\alpha \left( x-x_{0}\right) \quad \cdots (2)
\end{equation}を得ます。\(\beta =0\)が成り立つものと仮定すると、\begin{equation}\forall x\in I:0\geq -\alpha \left( x-x_{0}\right) \quad \cdots (3)
\end{equation}を得ます。仮定より\(x_{0}\)は\(I\)の内点であるため、点\(x\in I\)のとりかたによって\(x-x_{0}\)は正と負のどちらにもなり得ます。それにも関わらず\(\left( 3\right) \)を成立させるためには\(\alpha =0\)である必要があります。つまり、\(\left( \alpha ,\beta \right) =\left( 0,0\right) \)となりますが、これは\(\left( \alpha ,\beta \right) \)が非ゼロベクトルであることと矛盾です。したがって背理法より、\(\beta =0\)が成り立たないこと、すなわち\(\beta >0\)であることが示されました。すると\(\left( 2\right) \)より、\begin{equation*}\forall x\in I:f\left( x\right) -f\left( x_{0}\right) \geq -\frac{\alpha }{\beta }\left( x-x_{0}\right)
\end{equation*}を得ます。さらに、\begin{equation*}
c=-\frac{\alpha }{\beta }
\end{equation*}とおくと、これを、\begin{equation*}
\forall x\in I:f\left( x\right) -f\left( x_{0}\right) \geq c\left(
x-x_{0}\right)
\end{equation*}と表現できます。

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

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

例(凸関数の劣勾配と劣微分)
関数\(f:\mathbb{R} \rightarrow \mathbb{R} \)はそれぞれの\(x\in \mathbb{R} \)に対して、\begin{equation*}f\left( x\right) =\left\vert x\right\vert
\end{equation*}を定めるものとします。この関数\(f\)は凸関数です。点\(x_{0}\in \mathbb{R} \)を任意に選びます。\(\mathbb{R} \)は開集合であるため\(x_{0}\)は内点でもあります。\(x_{0}>0\)を満たす内点\(x_{0}\)における\(f\)の劣勾配は\(1\)であり、\(x_{0}=0\)における劣勾配は\(\left[ -1,1\right] \)に属する任意の実数であり、\(x_{0}<0\)を満たす内点\(x_{0}\)における\(f\)の劣勾配は\(-1\)です(演習問題)。したがって、この関数\(f\)のそれぞれの内点\(x_{0}\)における劣微分は、\begin{equation*}\partial \left( x_{0}\right) =\left\{
\begin{array}{cc}
\left\{ 1\right\} & \left( if\ x_{0}>0\right) \\
\left[ -1,1\right] & \left( if\ x_{0}=0\right) \\
\left\{ -1\right\} & \left( if\ x_{0}<0\right)
\end{array}\right.
\end{equation*}となります。

 

凹関数の劣勾配と劣微分

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

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

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

例(凹関数の内点の劣微分)
関数\(f:\mathbb{R} \rightarrow \mathbb{R} \)はそれぞれの\(x\in \mathbb{R} \)に対して、\begin{equation*}f\left( x\right) =-\left\vert x\right\vert
\end{equation*}を定めるものとします。この関数\(f\)は凹関数です。点\(x_{0}\in \mathbb{R} \)を任意に選びます。\(\mathbb{R} \)は開集合であるため\(x_{0}\)は内点でもあります。\(x_{0}>0\)を満たす内点\(x_{0}\)における\(f\)の劣勾配は\(-1\)であり、\(x_{0}=0\)における劣勾配は\(\left[ -1,1\right] \)に属する任意の実数であり、\(x_{0}<0\)を満たす内点\(x_{0}\)における\(f\)の劣勾配は\(1\)です(演習問題)。したがって、この関数\(f\)のそれぞれの内点\(x_{0}\)における劣微分は、\begin{equation*}\partial \left( x_{0}\right) =\left\{
\begin{array}{cc}
\left\{ -1\right\} & \left( if\ x_{0}>0\right) \\
\left[ -1,1\right] & \left( if\ x_{0}=0\right) \\
\left\{ 1\right\} & \left( if\ x_{0}<0\right)
\end{array}\right.
\end{equation*}となります。

 

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

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

命題(微分可能な凸関数の劣勾配と劣微分)
区間上に定義された凸関数\(f:\mathbb{R} \supset I\rightarrow \mathbb{R} \)が与えられたとき、定義域の内点\(x_{0}\in I^{i}\)を任意に選ぶ。\(f\)が点\(x_{0}\)において微分可能であるならば、\begin{equation*}\partial f\left( x_{0}\right) =\left\{ f^{\prime }\left( x_{0}\right)
\right\}
\end{equation*}という関係が成り立つ。つまり、内点\(x_{0}\)における微分係数\(f^{\prime}\left( x_{0}\right) \)はそこでの唯一の劣勾配である。
証明

プレミアム会員専用コンテンツです
ログイン】【会員登録

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

命題(微分可能な凹関数の劣勾配と劣微分)
区間上に定義された凸関数\(f:\mathbb{R} \supset I\rightarrow \mathbb{R} \)が与えられたとき、定義域の内点\(x_{0}\in I^{i}\)を任意に選ぶ。\(f\)が点\(x_{0}\)において微分可能であるならば、\begin{equation*}\partial f\left( x_{0}\right) =\left\{ f^{\prime }\left( x_{0}\right)
\right\}
\end{equation*}という関係が成り立つ。つまり、内点\(x_{0}\)における微分係数\(f^{\prime}\left( x_{0}\right) \)はそこでの唯一の劣勾配である。

 

演習問題

問題(関数の内点の劣微分)
関数\(f:\mathbb{R} \rightarrow \mathbb{R} \)はそれぞれの\(x\in \mathbb{R} \)に対して、\begin{equation*}f\left( x\right) =\left\vert x\right\vert
\end{equation*}を定めるものとします。\(\mathbb{R} \)のそれぞれの内点における\(f\)の劣微分を求めてください。
解答を見る

プレミアム会員専用コンテンツです
ログイン】【会員登録

問題(関数の内点の劣微分)
関数\(f:\mathbb{R} \rightarrow \mathbb{R} \)はそれぞれの\(x\in \mathbb{R} \)に対して、\begin{equation*}f\left( x\right) =x^{2}
\end{equation*}を定めるものとします。\(\mathbb{R} \)のそれぞれの内点における\(f\)の劣微分を求めてください。
解答を見る

プレミアム会員専用コンテンツです
ログイン】【会員登録

問題(劣微分は凸集合)
区間上に定義された関数\(f:\mathbb{R} \supset I\rightarrow \mathbb{R} \)が凸関数または凹関数であるものとします。定義域の内点\(x_{0}\in I^{i}\)を任意に選んだとき、劣微分\(\partial f\left( x_{0}\right) \)は凸集合であることを示してください。
解答を見る

プレミアム会員専用コンテンツです
ログイン】【会員登録

問題(劣微分は閉集合)
区間上に定義された関数\(f:\mathbb{R} \supset I\rightarrow \mathbb{R} \)が凸関数または凹関数であるものとします。定義域の内点\(x_{0}\in I^{i}\)を任意に選んだとき、劣微分\(\partial f\left( x_{0}\right) \)は閉集合であることを示してください。
解答を見る

プレミアム会員専用コンテンツです
ログイン】【会員登録

Twitter
Mailで保存

質問とコメント