次梯度 subgradient
当优化问题的目标函数不可微的时候，我们就会去考虑梯度的替代品：次梯度。
一些目标函数不可微的凸优化问题，就可以使用次梯度方法来求解。
凸函数有一个很好的性质，那就是任意一点的切平面都位于函数图形的下方。对于凸函数 $f$，如果
$$ f(y) \geq f(x)+g^{T}(y-x) \quad \text{for all } y \tag{1} $$
就说 $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$ 的次梯度是有界的，即 $\| g \|_2 \leq G, \forall g \in \partial f(x), \forall x$ .
这样的迭代规则等价于 $$ \begin{equation} x^{(k+1)} = \underset{x}{\arg\min} \left\{f(x^{(k)}) + \langle g^{(k)}, x-x^{(k)} \rangle + \frac{1}{2\alpha_k} \|x-x^{(k)} \|^2\right\} \label{subgradient-updating-rules} \end{equation} $$ 上式右边是一个关于 $x$ 的二次函数，在 $x=x^{(k)}-\alpha_k g^{(k)}$ 处取得最小值。上式的意义在于，揭示了迭代过程与一阶近似最小化的联系。
我们关心的是 $$ f_{\text {best }}^{(k)}=\min \left\{f(x^{(1)}), \ldots, f(x^{(k)})\right\} $$ 首先： $$ \begin{aligned} \left\|x^{(k+1)}-x^{\star}\right\|_2^2 &=\left\|x^{(k)}-\alpha_k g^{(k)}-x^{\star}\right\|_2^2 \\ &=\left\|x^{(k)}-x^{\star}\right\|_2^2-2 \alpha_k g^{(k) T}\left(x^{(k)}-x^{\star}\right)+\alpha_k^2\left\|g^{(k)}\right\|_2^2 \\ & \leq\left\|x^{(k)}-x^{\star}\right\|_2^2-2 \alpha_k\left(f(x^{(k)})-f^{\star}\right)+\alpha_k^2\left\|g^{(k)}\right\|_2^2, \end{aligned} $$ 由此不难得到： $$ \left\|x^{(k+1)}-x^{\star}\right\|_2^2 \leq\left\|x^{(1)}-x^{\star}\right\|_2^2-2 \sum_{i=1}^k \alpha_i\left(f(x^{(i)})-f^{\star}\right)+\sum_{i=1}^k \alpha_i^2\left\|g^{(i)}\right\|_2^2 $$ 于是有： $$ 2 \sum_{i=1}^k \alpha_i\left(f(x^{(i)})-f^{\star}\right) \leq\left\|x^{(1)}-x^{\star}\right\|_2^2+\sum_{i=1}^k \alpha_i^2\left\|g^{(i)}\right\|_2^2 $$ 此外： $$ \sum_{i=1}^k \alpha_i\left(f(x^{(i)})-f^{\star}\right) \geq\left(\sum_{i=1}^k \alpha_i\right) \min _{i=1, \ldots, k}\left(f(x^{(i)})-f^{\star}\right) $$ 于是我们可以得到： $$ \begin{aligned} f_{\text {best }}^{(k)}-f^{\star}=\min _{i=1, \ldots, k} f(x^{(i)})-f^{\star} & \leq \frac{\left\|x^{(1)}-x^{\star}\right\|_2^2+\sum_{i=1}^k \alpha_i^2\left\|g^{(i)}\right\|_2^2}{2 \sum_{i=1}^k \alpha_i} \\ & \leq \frac{\left\|x^{(1)}-x^{\star}\right\|_2^2+G^2\sum_{i=1}^k \alpha_i^2}{2 \sum_{i=1}^k \alpha_i} \\ & \leq \frac{R^2+G^2\sum_{i=1}^k \alpha_i^2}{2 \sum_{i=1}^k \alpha_i} \\ \end{aligned}\label{subgradient-convergence-formula} $$ 在这里，我们让 $R=\left\|x^{(1)}-x^{\star}\right\|_2$ 或者是约束集的直径。
Constant step size
如果我们选择固定步长 $\alpha_i = h$，则 $$ f_{\text {best }}^{(k)}-f^{\star} \leq \frac{\operatorname{dist}\left(x^{(1)}, X^{\star}\right)^2+G^2 h^2 k}{2 h k} $$
Square summable but not summable
假定步长序列 $\{\alpha_i, i \geq 1\}$ 满足 $$ \|\alpha\|_2^2=\sum_{k=1}^{\infty} \alpha_k^2<\infty, \quad \sum_{k=1}^{\infty} \alpha_k=\infty $$ 根据式 $\eqref{subgradient-convergence-formula}$，可知当 $k \to \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} \leq \frac{RG \log k}{2\sqrt{k}} $$
Mirror descent
类似于式 $\eqref{subgradient-updating-rules}$，将2-范数换成 Bregman divergence，我们容易得到另一种更新的规则： $$ x^{(k+1)} = \underset{x}{\arg\min} \left\{f(x^{(k)}) + \langle g^{(k)}, x-x^{(k)} \rangle + \frac{1}{\alpha_k} B_{\psi}(x, x^{(k)})\right\} $$
$$ B_\psi({x} , {y})=\psi({x})-\psi({y})-\langle\nabla \psi({y}), {x}-{y}\rangle $$
对上式梯度，得到最优性条件： $$ \begin{aligned} & g^{(k)} + \frac{1}{\alpha_k} \left(\nabla \psi(x^{(k+1)}) - \nabla \psi (x^{(k)}) \right) = 0 \\ \Longleftrightarrow \; & \nabla \psi(x^{(k+1)}) = \nabla \psi (x^{(k)}) - \alpha_k g^{(k)} \\ \Longleftrightarrow \; & x^{(k+1)} = (\nabla \psi^\ast) \left(\nabla \psi (x^{(k)}) - \alpha_k g^{(k)} \right) \end{aligned} $$
假设 $\psi$ 是 $\sigma$-强凸函数，则 $$ B_{\psi}(x^\ast, x^{(k+1)}) \leq B_{\psi}(x^\ast, x^{(k)}) - \alpha_k \left(f(x^{(k)}) - f(x^\ast) \right) + \frac{\alpha^2}{2\sigma} \|g_k \|_{\ast}^2 $$ 于是我们成功用 $B_{\psi}(x^\ast, x_1)$ 代替了 $R^2 = \|x^\ast - x_1 \|_2^2$，用次梯度的对偶范数的上确界代替了梯度2-范数的上确界。
Piecewise linear
次梯度方法就是沿着次梯度的方向进行迭代的方法。如：
$$ \max_x f(x) = \max_x \: \min_{i=1\dots n} \; a_i^T x + b_i $$
目标函数是分段线性的凹函数，在若干点是不可微的，但是可以计算到 $f(x)$ 的次梯度，令 $I(x^\ast) = \{i \mid f(x^\ast) = a_i^T x^\ast + b_i \}$，则
- $a_i \in \partial f(x^\ast) \;\; \text{for all }\; i \in I$
- $\partial f(x^\ast) = \left\{s \in \mathrm{R}^{n}\mid s=\Sigma_{i \in I\left(x^{\ast}\right)} \lambda_{i} a^{i}, \Sigma_{i \in I\left(x^{\ast}\right)} \lambda_{i}=1, \lambda_{i} \geq 0 \text { for } i \in I\left(x^{\ast}\right)\right\}$
由此可以用次梯度方法来求解。