梯度坐标下降

梯度下降

梯度下降法是一种常用的一阶优化方法，是求解无约束优化问题方法之一。

原理：考虑无约束优化问题$$\min_x f(x)$$，其中$f(x)$为连续可微函数，若能构造一个序列$x^0,x^1,x^2,…$满足$$f(x^{t+1}) < f(x^t),\ t=0,1,2…$$

不断迭代执行该过程即可收敛到局部极小点。根据泰勒展开式：$$f(x+\Delta x) \approx f(x)+\Delta x^T \nabla f(x)$$

欲满足：$$f(x+\Delta x) \ < f(x)$$也就是近似满足
：$$f(x)+\Delta x^T \nabla f(x)\ <\ f(x)\ \rightleftharpoons \Delta x f(x) \ < 0$$

为了保证$\Delta x f(x) \ < \ 0$成立，这里一般设置$\Delta x\ = \ -\gamma \nabla f(x)$这就是梯度下降法。当连续的两次迭代结果差小于阈值或者到达一定的迭代次数后，得到极小点

通过选取合适的步长，保证通过梯度下降收敛到局部极小点。当目标函数为凸函数时，局部极小点就对应着函数的全局最小点。

坐标下降法

坐标下降法是一种非梯度优化方法，在每次迭代中沿一个坐标方向进行搜索，通过循环使用不同的坐标方向来达到目标函数的局部极小值。

他的原理就是在各个维度上搜索当前维度上函数的最小值，知道维度循环完毕。

不妨假设目标是求解函数$f(x)$的极小值，其中$x=(x_1,x_2,…,x_d)^T \ \in R^d$是一个d维向量。从初始点$x_0$开始，坐标下降法通过迭代构造序列求解问题，$x^{t+1}$的第i个分量$x_i^{t+1}$构造为$$x_i^{t+1}= \arg\min\limits_{y \in R} f(x_1^(t+1),…,x_{i-1}^{t+1},y,x_{i+1}^t,…,x_d^t)$$

通过迭代执行过程显然有$$f(x^0)\geq f(x^1) \geq f(x^2)$$

这里要注意函数必须要可微，否则不成立。