在阅读相关文献的时候，经常会遇到梯度下降，坐标下降，牛顿迭代这样的术语，今天把他们的概念整理一下。
梯度下降
整理自百度
梯度下降法是一个最优化算法，通常也称为最速下降法。
顾名思义，梯度下降法的计算过程就是沿梯度下降的方向求解极小值（也可以沿梯度上升方向求解极大值）。 其迭代公式为 ,其中 代表梯度负方向， 表示梯度方向上的搜索步长。梯度方向我们可以通过对函数求导得到，步长的确定比较麻烦，太大了的话可能会发散，太小收敛速度又太慢。一般确定步长的方法是由线性搜索算法来确定，即把下一个点的坐标看做是a k+1的函数，然后求满足f(a k+1)的最小值的 即可。 因为一般情况下，梯度向量为0的话说明是到了一个极值点，此时梯度的幅值也为0.而采用梯度下降算法进行最优化求解时，算法迭代的终止条件是梯度向量的幅值接近0即可，可以设置个非常小的常数阈值。 举一个非常简单的例子，如求函数 的最小值。 利用梯度下降的方法解题步骤如下： 1、求梯度， 2、向梯度相反的方向移动 ，如下 ，其中， 为步长。如果步长足够小，则可以保证每一次迭代都在减小，但可能导致收敛太慢，如果步长太大，则不能保证每一次迭代都减少，也不能保证收敛。 3、循环迭代步骤2，直到 的值变化到使得 在两次迭代之间的差值足够小，比如0.00000001，也就是说，直到两次迭代计算出来的 基本没有变化，则说明此时 已经达到局部最小值了。 4、此时，输出 ，这个 就是使得函数 最小时的 的取值 。 %% 最速下降法图示 % 设置步长为0.1，f_change为改变前后的y值变化，仅设置了一个退出条件。 syms x;f=x^2; step=0.1;x=2;k=0; %设置步长,初始值,迭代记录数 f_change=x^2; %初始化差值 f_current=x^2; %计算当前函数值 ezplot(@(x,f)f-x.^2) %画出函数图像 axis([-2,2,-0.2,3]) %固定坐标轴 hold on while f_change>0.000000001 %设置条件，两次计算的值之差小于某个数，跳出循环 x=x-step*2*x; %-2*x为梯度反方向，step为步长，！最速下降法！ f_change = f_current - x^2; %计算两次函数值之差 f_current = x^2 ; %重新计算当前的函数值 plot(x,f_current,'ro','markersize',7) %标记当前的位置 drawnow;pause(0.2); k=k+1; end hold off fprintf('在迭代%d次后找到函数最小值为%e，对应的x值为%e\n',k,x^2,x)缺点： 靠近极小值时收敛速度减慢。 直线搜索时可能会产生一些问题。 可能会“之字形”地下降。 容易陷入局部最优解 坐标下降 转自http://blog.csdn.net/u013802188/article/details/40476989 首先介绍一个算法：coordinate-wise minimization问题的描述：给定一个可微的凸函数，如果在某一点x，使得f(x)在每一个坐标轴上都是最小值，那么f(x)是不是一个全局的最小值。
形式化的描述为：是不是对于所有的d，i都有
这里的代表第i个标准基向量。
答案为成立。
这是因为：
但是问题来了，如果对于凸函数f，若不可微该会怎样呢？
答案为不成立，上面的图片就给出了一个反例。
那么同样的问题，现在，其中g是可微的凸函数，每一个hi都是凸的？
答案为成立。
证明如下，对每一个y
坐标下降(Coordinate descent)：
这就意味着，对所有的，其中g是可微的凸函数，每一个hi都是凸的，我们可以使用坐标下降寻求一个最小值，我们从一个最初的猜想开始，对k进行循环：
每一次我们解决了，我们都会使用新的值。
Tseng (2001)的开创性工作证明：对这种f（f在紧集上连续，且f到达了其最小值），的极限值，k=1,2,3….是f的一个最小元(minimizer)。
在实分析领域：
随后收敛与x*( Bolzano-Weierstrass)
收敛于f*( monotoneconvergence)
其中：
坐标下降的顺序是任意的，可以是从1到n的任意排列。
可以在任何地方将单个的坐标替代成坐标块
关键在于一次一个地更新，所有的一起更新有可能会导致不收敛
我们现在讨论一下坐标下降的应用：
线性回归：
令，其中，A有p列：
最小化xi，对所有的xj，j不等于i：
解得：
坐标下降重复这个更新对所有的
对比坐标下降与梯度下降在线性回归中的表现（100个实例，n=100，p=20）
将坐标下降的一圈与梯度下降的一次迭代对比是不是公平呢？是的。
其中r=y-Ax。每一次的坐标更新需要O(n)个操作，其中O(n)去更新r，O(n)去计算，所以一圈就需要O(np)，跟梯度下降是一样的。
我们用相同的例子，用梯度下降进行比较，似乎是与计算梯度下降的最优性相违背。
那么坐标下降是一个一阶的方法吗？事实上不是，它使用了比一阶更多的信息。
现在我们再关注一下支持向量机：
SVM对偶中的坐标下降策略：
SMO(Sequentialminimal optimization)算法是两块的坐标下降，使用贪心法选择下一块，而不是用循环。
回调互补松弛条件(complementaryslackness conditions)：
v，d，s是原始的系数，截距和松弛，其中，使用任何的（1）中i使得来计算d，利用（1）（2）来计算2.
SMO重复下面两步：
选出不满足互补松弛的αi，αj
最小化αi，αj使所有的变量满足条件
第一步使用启发式的方法贪心得寻找αi，αj，第二步使用等式约束。
牛顿迭代法 转自http://blog.csdn.net/zkq_1986/article/details/52317258牛顿迭代法（Newton’s method）又称为牛顿-拉夫逊方法（Newton-Raphson method），它是牛顿在17世纪提出的一种在实数域和复数域上近似求解方程的方法。多数方程不存在求根公式，因此求精确根非常困难，甚至不可能，从而寻找方程的近似根就显得特别重要。 把f(x）在x0点附近展开成泰勒级数 f(x) = f(x0)+(x－x0)f’(x0)+(x－x0)^2*f”(x0)/2! +… 取其线性部分，作为非线性方程f(x) = 0的近似方程，即泰勒展开的前两项，则有f(x0)+f’(x0)(x－x0)=0 设f’(x0）≠0则其解为x1=x0－f(x0)/f’(x0) 这样，得到牛顿法的一个迭代序列：x(n+1）=x(n）－f(x(n))/f’(x(n)）。
