> For the complete documentation index, see [llms.txt](https://json007.gitbook.io/svm/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://json007.gitbook.io/svm/math-convex_optimization/zui_su_xia_jiang_fa.md).

# 最速下降法

梯度下降每步所求：

$$
\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://2270971654-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M7DcNFhVrwIk3Tks_pB%2Fsync%2F7f76a3061cd359d8983cf760f4a38ef70f5a124d.png?generation=1589383933369111\&alt=media)

![](https://2270971654-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M7DcNFhVrwIk3Tks_pB%2Fsync%2Fa91a57db31c5c50937ecb524ff7324f9fbd5dc9a.gif?generation=1589383933691423\&alt=media)

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

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