次梯度与次梯度方法

次梯度 subgradient

当优化问题的目标函数不可微的时候，我们就会去考虑梯度的替代品：次梯度。

一些目标函数不可微的凸优化问题，就可以使用次梯度方法来求解。

凸函数有一个很好的性质，那就是任意一点的切平面都位于函数图形的下方。对于凸函数 $f$，如果

$$\begin{array}{}\text{(1)}& f(y)\ge f(x)+g^T(y-x)\text{for all }y\end{array}$$

就说 $g$ 是 $x$ 这点的次梯度。

函数的梯度是一个向量，注意次梯度方向可能不唯一，所有次梯度构成的集合叫做次微分(subdifferential)，$x$ 的次微分记作 $\partial f(x)$。

在上面的定义下，凸函数的次微分总是非空，凹函数的次微分是空集。类似地，把式(1)的不等号方向改变可以得到对于凹函数的次微分的定义。

如果要把次梯度的概念推广到一般函数的话，那么会发现，一般函数可能再某个点不存在次梯度（次梯度为空集），而凸函数不会存在这样的问题。在凸函数的定义域的相对内点集上，次梯度集总是非空（凸函数在定义域的边界的连续性比较复杂）。

以一维为例，$f$ 在 $x_0$ 不一定可导，但是有左导数 $a$，右导数 $b$，那么 $[a,b]$ 就是 $f$ 在 $x_0$ 这点的次微分。比如 $f=|x|$ 在 $x=0$ 处的次微分就是 $[-1,1]$。

通过次梯度可以得到一个函数（不管是不是凸的）全局最优解的性质。 如果 $0\in \partial f(x^{\ast })$，那么 $x^{\ast }$ 就是全局最小点。

次梯度方法

次梯度的迭代式如下： $$x^{(k+1)}=x^{(k)}-{\alpha }_k{g}^{(k)}$$ 因为次梯度方向可能不是一个下降方向，所以不能使用类似梯度下降法那样的收敛性分析方法。我们仍然假设 $f$ 的次梯度是有界的，即 $\parallel g{\parallel }_2\le G,\mathrm{\forall }g\in \partial f(x),\mathrm{\forall }x$ .

这样的迭代规则等价于 $$\begin{array}{}\text{(1)}& x^{(k+1)}=\underset{x}{\arg min}\{f(x^{(k)})+⟨g^{(k)},x-x^{(k)}⟩+\frac{1}{2{\alpha }_k}\parallel x-x^{(k)}{\parallel }^2\}\end{array}$$ 上式右边是一个关于 $x$ 的二次函数，在 $x=x^{(k)}-{\alpha }_k{g}^{(k)}$ 处取得最小值。上式的意义在于，揭示了迭代过程与一阶近似最小化的联系。

我们关心的是 $$f_{\text{best }}^{(k)}=min\{f(x^{(1)}),\dots ,f(x^{(k)})\}$$ 首先： $$\begin{array}{rl}{\parallel x^{(k+1)}-x^{\star }\parallel }_2^2& ={\parallel x^{(k)}-{\alpha }_k{g}^{(k)}-x^{\star }\parallel }_2^2\\ & ={\parallel x^{(k)}-x^{\star }\parallel }_2^2-2{\alpha }_k{g}^{(k)T}(x^{(k)}-x^{\star })+{\alpha }_k^2{\parallel g^{(k)}\parallel }_2^2\\ & \le {\parallel x^{(k)}-x^{\star }\parallel }_2^2-2{\alpha }_k(f(x^{(k)})-f^{\star })+{\alpha }_k^2{\parallel g^{(k)}\parallel }_2^2,\end{array}$$ 由此不难得到： $${\parallel x^{(k+1)}-x^{\star }\parallel }_2^2\le {\parallel x^{(1)}-x^{\star }\parallel }_2^2-2\sum _{i=1}^k{\alpha }_i(f(x^{(i)})-f^{\star })+\sum _{i=1}^k{\alpha }_i^2{\parallel g^{(i)}\parallel }_2^2$$ 于是有： $$2\sum _{i=1}^k{\alpha }_i(f(x^{(i)})-f^{\star })\le {\parallel x^{(1)}-x^{\star }\parallel }_2^2+\sum _{i=1}^k{\alpha }_i^2{\parallel g^{(i)}\parallel }_2^2$$ 此外： $$\sum _{i=1}^k{\alpha }_i(f(x^{(i)})-f^{\star })\ge \left(\sum _{i=1}^k{\alpha }_i\right)\underset{i=1,\dots ,k}{min}(f(x^{(i)})-f^{\star })$$ 于是我们可以得到： $$\begin{array}{rl}{f}_{\text{best }}^{(k)}-f^{\star }=\underset{i=1,\dots ,k}{min}f(x^{(i)})-f^{\star }& \le \frac{{\parallel x^{(1)}-x^{\star }\parallel }_2^2+\sum _{i=1}^k{\alpha }_i^2{\parallel g^{(i)}\parallel }_2^2}{2\sum _{i=1}^k{\alpha }_i}\\ & \le \frac{{\parallel x^{(1)}-x^{\star }\parallel }_2^2+G^2\sum _{i=1}^k{\alpha }_i^2}{2\sum _{i=1}^k{\alpha }_i}\\ & \le \frac{R^2+G^2\sum _{i=1}^k{\alpha }_i^2}{2\sum _{i=1}^k{\alpha }_i}\end{array}$$ 在这里，我们让 $R={\parallel x^{(1)}-x^{\star }\parallel }_2$ 或者是约束集的直径。

Constant step size

如果我们选择固定步长 ${\alpha }_i=h$，则 $$f_{\text{best }}^{(k)}-f^{\star }\le \frac{\mathrm{dist}{(x^{(1)},X^{\star })}^2+G^2{h}^{2}k}{2hk}$$

Square summable but not summable

假定步长序列 $\{{\alpha }_i,i\ge 1\}$ 满足 $$\parallel \alpha {\parallel }_2^2=\sum _{k=1}^{\mathrm{\infty }}{\alpha }_k^2<\mathrm{\infty },\sum _{k=1}^{\mathrm{\infty }}{\alpha }_k=\mathrm{\infty }$$ 根据式 $\text{(???)}$，可知当 $k\to \mathrm{\infty }$ 时，$f_{\text{best}}^{(k)}\to f^{\star }$ .

Diminishing step size rule

如果 ${\alpha }_k=\frac{R}{G\sqrt{k}}$，那么 $$f_{\text{best }}^{(k)}-f^{\star }\le \frac{RG\log k}{2\sqrt{k}}$$

Mirror descent

类似于式 $\text{(1)}$，将2-范数换成 Bregman divergence，我们容易得到另一种更新的规则： $$x^{(k+1)}=\underset{x}{\arg min}\{f(x^{(k)})+⟨g^{(k)},x-x^{(k)}⟩+\frac{1}{{\alpha }_k}{B}_{\psi }(x,x^{(k)})\}$$

$$B_{\psi }(x,y)=\psi (x)-\psi (y)-⟨\mathrm{\nabla }\psi (y),x-y⟩$$

对上式梯度，得到最优性条件： $$\begin{array}{rl}& g^{(k)}+\frac{1}{{\alpha }_k}(\mathrm{\nabla }\psi (x^{(k+1)})-\mathrm{\nabla }\psi (x^{(k)}))=0\\ ⟺& \mathrm{\nabla }\psi (x^{(k+1)})=\mathrm{\nabla }\psi (x^{(k)})-{\alpha }_k{g}^{(k)}\\ ⟺& x^{(k+1)}=(\mathrm{\nabla }{\psi }^{\ast })(\mathrm{\nabla }\psi (x^{(k)})-{\alpha }_k{g}^{(k)})\end{array}$$

假设 $\psi$ 是 $\sigma$-强凸函数，则 $$B_{\psi }(x^{\ast },x^{(k+1)})\le B_{\psi }(x^{\ast },x^{(k)})-{\alpha }_k(f(x^{(k)})-f(x^{\ast }))+\frac{{\alpha }^2}{2\sigma }\parallel g_k{\parallel }_{\ast }^2$$ 于是我们成功用 $B_{\psi }(x^{\ast },x_1)$ 代替了 $R^2=\parallel x^{\ast }-x_1{\parallel }_2^2$，用次梯度的对偶范数的上确界代替了梯度2-范数的上确界。

Piecewise linear

次梯度方法就是沿着次梯度的方向进行迭代的方法。如：

$$\underset{x}{max}f(x)=\underset{x}{max}\underset{i=1\dots n}{min}{a}_i^{T}x+b_i$$

目标函数是分段线性的凹函数，在若干点是不可微的，但是可以计算到 $f(x)$ 的次梯度，令 $I(x^{\ast })=\{i\mid f(x^{\ast })=a_i^T{x}^{\ast }+b_i\}$，则

1. $a_i\in \partial f(x^{\ast })\text{for all }i\in I$
2. $\partial f(x^{\ast })=\{s\in {\mathrm{R}}^n\mid s={\mathrm{\Sigma }}_{i\in I\left(x^{\ast }\right)}{\lambda }_i{a}^i,{\mathrm{\Sigma }}_{i\in I\left(x^{\ast }\right)}{\lambda }_i=1,{\lambda }_i\ge 0\text{ for }i\in I\left(x^{\ast }\right)\}$

由此可以用次梯度方法来求解。

参考： 【凸优化笔记5】-次梯度方法（Subgradient method）