# 坐标下降法

不是求整个变量的梯度，然后下降，而是循环的沿着变量的每一维进行单变量优化。

$$
x\_i^{k+1} =\arg \min\_{\epsilon \in R} f(x\_1^{k+1},x\_2^{k+1}, \ldots ,x\_{i-1}^{k+1},\epsilon,x\_{i+1}^{k},\ldots,x\_n^k)
$$

此方法收敛性与最速下降法类似。

单变量优化优点：

* 有可能可以精确直线搜索，或者单维度的牛顿法，等可以得到子问题的最优解。
* 可并行：将内循环的迭代变成单步并行。不过这点依赖于目标函数的结构，变量之间是否能否解耦。

内循环不一定要按维度下标依次迭代，可以乱序，自适应等。

## 分块坐标下降##\#

如果不能全变量解耦，那么希望变量之间能够分块解耦。

$$
f(x) = \sum\_{i=1}^m f\_i (x\_i), \qquad x\_i \in X\_i
X = X\_1 \oplus  X\_2 \oplus \ldots X\_n
$$

## 脑洞大开##\#

可否在最速下降与坐标下降做折衷，每次迭代只取梯度中最大的top k个分量。 好像一般函数，变化最大的几个分量“都在一起”。而且就那么2\~3个变化很快，所以k就取2或3. 缺点：这样就不容易精确直线搜索，或者单维度的牛顿法等。