$$\mathbf{g}$$ is a subgradient of $$\mathbf{f}$$ (convex or not) at $$x$$ if

$f(y) \ge f(x)+g^T(y-x), \forall y$

$$\partial f(x)$$ 仅含有一个元素 $$g \leftrightarrow?g=\nabla f(x)$$ 且 $$f(x)$$ 在x处可导

$f(x^*)=\min_{x}f(x) \leftrightarrow 0\in \partial f(x^*)$

OK，终于可以开始正题了，经典梯度下降算法实际上是利用负梯度总是指向最小值点这一性质，然后每次迭代 $$x^{k+1}=x^k-\alpha_k\nabla f(x^k)$$ ， $$\alpha_k$$ 是一个很小的控制步进长度的数，可以是常量也可以是变量，迭代过程一直进行直到收敛。

$\begin{split} \|x_1-\alpha g-x^*\|^2 &= \|x_1-x^*\|^2 -2\alpha g^T(x_1-x^*)+\alpha^2\|g\|^2\\&\le \|x_1-x^*\|^2 -2\alpha (f(x_1)-f(x^*))+\alpha^2\|g\|^2\\&\le\|x_1-x^*\|^2\end{split}$

$$f$$ is convex and non-differentiable: minimize $$f(x)$$

Subgradient method: $$x^{k+1} = x^k-\alpha_k g^k$$

• $$x^k$$ is the $$k$$ th iterate
• $$g^k$$ is any subgradient of $$f$$ at $$x^k$$
• $$\alpha_k > 0$$ is the $$k$$ th step size