劣勾配と劣微分

関数 $f:{\mathbb{R}}^n\to \mathbb{R}$ が凸であるとは、任意の $x,y$ と $0\le \lambda \le 1$ に対して $f(\lambda x+(1-\lambda )y)\le \lambda f(x)+(1-\lambda )f(y)$ が成り立つこと（グラフ上の 2 点を結ぶ線分がグラフより上にあること）です。ベクトル $g$ が $f$ の点 $x$ での劣勾配であるとは、すべての $y$ について $$f(y)\ge f(x)+⟨g,y-x⟩$$ が成り立つこと、つまり点 $(x,f(x))$ を通り傾き $g$ の 1 次関数がグラフ全体の下にあることです。劣勾配全体の集合を $\partial f(x)$ と書き、劣微分といいます。まず、凸関数 $f$ と $d=y-x$、$0<t\le 1$ について、凸性から $f(x+td)=f((1-t)x+ty)\le (1-t)f(x)+tf(y)$、すなわち $$\frac{f(x+td)-f(x)}{t}\le f(y)-f(x)(\ast )$$ が成り立つことに注意します。$f$ が $x$ で微分可能なら、$t\to +0$ のとき左辺は合成関数の微分（全微分）により $⟨\nabla f(x),d⟩$ に近づくので、$f(y)\ge f(x)+⟨\nabla f(x),y-x⟩$、つまり $\nabla f(x)\in \partial f(x)$ です。逆に $g\in \partial f(x)$ なら任意の方向 $v$ と $t>0$ で $f(x+tv)-f(x)\ge t⟨g,v⟩$ なので、$t\to +0$ として $⟨\nabla f(x),v⟩\ge ⟨g,v⟩$。$v$ を $-v$ に替えれば逆向きの不等式も出るので $g=\nabla f(x)$。よって微分可能な点では $\partial f(x)=\{\nabla f(x)\}$ です。微分できない点では、下から接する直線が何本も引けるので劣微分は集合になります。

代表例を定義から確かめます。$f(x)=|x|$（1 変数）では、$x>0$ で $\{1\}$、$x<0$ で $\{-1\}$。$x=0$ では $|y|\ge gy$ がすべての $y$ で成り立つ条件で、$y=\pm 1$ を入れると $-1\le g\le 1$、逆に $|g|\le 1$ なら $gy\le |g||y|\le |y|$。よって $\partial |x|(0)=[-1,1]$。$f(x)=\Vert x{\Vert }_2$ では、$x\ne 0$ で微分可能なので $\partial f(x)=\{x/\Vert x{\Vert }_2\}$。$x=0$ では $\Vert y{\Vert }_2\ge ⟨g,y⟩$ がすべての $y$ で成り立つ条件で、$\Vert g{\Vert }_2\le 1$ なら $⟨g,y⟩=\Vert g{\Vert }_2\Vert y{\Vert }_2\cos \theta \le \Vert y{\Vert }_2$、逆に $y=g$ を入れると $\Vert g{\Vert }_2\ge \Vert g{\Vert }_2^2$ から $\Vert g{\Vert }_2\le 1$。よって $\partial f(0)=\{g\mid \Vert g{\Vert }_2\le 1\}$。

$f(x)={\max }_i{x}_i$ では、最大値をとる添字の集合を $I(x)=\{i\mid x_i=f(x)\}$ とし、$e_i$ を第 $i$ 成分だけ 1 の単位ベクトル、$1=(1,\dots ,1)$ とします。主張は $$\partial f(x)=\left\{g\right|g_i\ge 0,\sum _i{g}_i=1,i\notin I(x)\text{ なら }{g}_i=0\}$$ （最大を達成している成分の勾配 $e_i$ の重み付き平均）です。(a) この形の $g$ が劣勾配であること: $i\in I(x)$ なら $x_i=f(x)$ なので $⟨g,y-x⟩={\sum }_{i\in I(x)}{g}_i{y}_i-f(x){\sum }_i{g}_i\le {\max }_i{y}_i-f(x)=f(y)-f(x)$。(b) 逆に $g\in \partial f(x)$ とします。$y=x+s1$（$s$ は任意の実数）では $f(y)=f(x)+s$ なので $s\ge s{\sum }_i{g}_i$ がすべての $s$ で成り立ち、${\sum }_i{g}_i=1$。$y=x-e_j$ では $f(y)\le f(x)$ なので $f(x)\ge f(y)\ge f(x)-g_j$ より $g_j\ge 0$。$j\notin I(x)$ なら $\delta =f(x)-x_j>0$ とおき $y=x+\delta e_j$ とすると $f(y)=f(x)$ なので $0\ge \delta g_j$、よって $g_j\le 0$ で、合わせて $g_j=0$。例えば 2 変数 $\max (x_1,x_2)$ の $x_1=x_2$ の点では $I=\{1,2\}$ で、$\partial f=\{(\lambda ,1-\lambda )\mid 0\le \lambda \le 1\}$（$(1,0)$ と $(0,1)$ を結ぶ線分）です。実際、$\lambda y_1+(1-\lambda )y_2\le \max (y_1,y_2)$ から確かめられます。

最適性条件は定義からすぐ出ます。$0\in \partial f(x^{\ast })$ とは $f(y)\ge f(x^{\ast })$ がすべての $y$ で成り立つこと、つまり $x^{\ast }$ が最小点であることそのものです。微分可能な凸関数 $h$ と凸関数 $r$ の和 $f=h+r$ では、次が成り立ちます: $$x^{\ast }\text{ が }f\text{ の最小点}⟺-\nabla h(x^{\ast })\in \partial r(x^{\ast }).$$ (十分性) $s=-\nabla h(x^{\ast })\in \partial r(x^{\ast })$ なら、$h(y)\ge h(x^{\ast })+⟨\nabla h(x^{\ast }),y-x^{\ast }⟩$ と $r(y)\ge r(x^{\ast })+⟨s,y-x^{\ast }⟩$ を足して $f(y)\ge f(x^{\ast })$。(必要性) $x^{\ast }$ が最小点なら、$d=y-x^{\ast }$, $0<t\le 1$ として $r(x^{\ast }+td)-r(x^{\ast })\ge -\{h(x^{\ast }+td)-h(x^{\ast })\}$。これと $r$ についての $(\ast )$ から $$r(y)-r(x^{\ast })\ge \frac{r(x^{\ast }+td)-r(x^{\ast })}{t}\ge -\frac{h(x^{\ast }+td)-h(x^{\ast })}{t}\to -⟨\nabla h(x^{\ast }),d⟩(t\to +0)$$ となり、$-\nabla h(x^{\ast })\in \partial r(x^{\ast })$。したがって、場合分けして条件 $0\in \nabla h(x)+\partial r(x)$ が成り立たない範囲には最小点がない、と結論できます。