最速下降法

梯度下降每步所求：

$$\arg \min_d \{\nabla f(x^k)^T d \quad s.t. ||d||=1\} \\ = -\arg \max_d \{|\nabla f(x^k)^T d| \quad s.t. ||d||=1\}$$

范数定义不同，方向不同，例如对于L1范数：

$$d^k = -sign(\frac {\partial f(x)}{\partial x_i})e_i \\ i= \arg \max_j |\frac {\partial f(x)}{\partial x_i}|$$

验证是下降方向：

$$\nabla f(x^k) \neq 0 \nabla f(x^k)^T d^k \lt \nabla f(x^k)^T \frac {-\nabla f(x^k)}{||\nabla f(x^k)||} = -||\nabla f(x^k)|| \lt 0$$

证明：

$$|a \cdot b| = |a_1b_1 + \ldots + a_nb_n| \\ \le |a_1b_1| + \ldots + |a_nb_n| \\ \le |a_k| * (|b_1|+ \ldots + |b_n|) \\ = ||a||_{\infty} ||b||_1 \\ ||a||_{\infty} = \max |a_i| \\ |\nabla f(x^k)^T d| \lt || \nabla f(x^k) || * ||d||_1$$

算法过程

最速下降法直观上就是沿着变换最快的坐标下降。所以接下来引出坐标下降法及分块坐标下降法。

https://zhuanlan.zhihu.com/p/23799012 无聊的最速下降法推导