坐标下降算法

* 可微和可导

• 对于多元函数，可微指的是可全微分，可导指的是可偏导数。可偏导仅指多元函数沿着轴方向导数存在的意思。直观感受是：可微意味着曲面在可微点处可以存在一个与其相切的平面。而可导就不存在这个特性了。 *　可微必可导，可导不一定可微

* 可微条件:

• 必要条件：若函数在某点可微，则该函数在该点对x和y的偏导数必存在。
• 充分条件：若函数对x和y的偏导数在这点的某一邻域内都存在，且均在这点连续，则该函数在这点可微。

* 可导和凸函数

若函数图形上任意两点的连线段必在函数图形的上方(下方)，则称该函数为凸函数(凹函数)。 数学表达式定义为：

*　函数f(X)，对任意不相等的$X_1，X_2 \in (a,b)$, 以及$\lambda\in(0，1)$，有

$f[λX_1+(1-λ)X_2]≤λf(X_1)+(1-λ)f(X_2)$

则f(x)称作凸函数。

• 从上述定义不能推断凸函数在凸性区间是否可导，从而凸函数也不一定有二阶导数。 举一个不可导的例子： 一个区间内，图形为向下凸折线段的函数，折线段上任意两点的连线段在该段函数图形上方，极端情形是该函数某两点连线正好与函数图形上某一线段重合（即上述不等式中的等号成立），根据定义，它是凸函数，可它不可导（但是连续，没有间断点），也没有二阶导数。

* 可微和平滑

*　一个处处可微分的函数是平滑函数

坐标下降算法基础

https://www.leiphone.com/news/201703/fbO2gmk0xkCdj4SB.html

* 坐标下降算法的适用情况

• 在什么情况下收敛？如果目标函数是光滑而且凸的，就一定会收敛。但很多问题不光滑，比如Lasso就不光滑，那怎么办？如果是不光滑的，只要光滑部分可分就可以了。在很多稀疏问题上，CD是可以保证是收敛的。

总结来说，当问题是光滑且凸的时候，坐标下降算法一定可以收敛，当问题不光滑的时候，当不光滑的部分是可分的，那么坐标下降算法也可以收敛。

坐标下降算法的优点是容易计算，同时收敛很快；缺点是当loss比较复杂时，会很明显的降低速度。

*可分函数

* 适用情况

*　可以求解lasso

http://blog.csdn.net/u013802188/article/details/40476989

* 证明

非求导的算法

• 对难以求导的方法，进行有限误差的近似计算

坐标下降算法

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

  1. 坐标下降算法：每次迭代中在当前点沿着一个坐标方向进行一维的搜索，其他方向固定
  2. 非导数的算法: 按照某一个方向一维搜索最小值

• 算法

  $x_i^{k+1}=arg \min\limits_{y\in R}f(x_1^{k+1},x_2^{k+1},...,x_{i-1}^{k+1},y,x_{i+1}^k,...,x_n^k)$

补充

http://www.cnblogs.com/pinard/p/6018889.html