对梯度迭代法与牛顿法求解极值问题的讨论

1、梯度下降算法发散举例0=0, 1=0, 2=0, h(x(i)=0, x0=1y(1)=400, y(2)=330, y(3)=369, y(4)=232, y(5)=540 x1(1)=2104, x1(2)=1600, x1(3)=2400, x1(4)=1416, x1(5)=3000 x2(1)=3, x2(2)=3, x2(3)=3, x2(4)=2, x2(5)=40=0+0.01(y(1)-h(x(1)x0(1)+.+(y(5)-h(x(5)x0(5)1=0+0.01(y(1)-h(x(1)x1(1)+.+(y(5)-h(x(5)x1(5)2=0+0.01(y(1)-h(x(1)

2、x2(1)+.+(y(5)-h(x(5)x2(5)x1yx20=0+0.01(y(1)-h(x(1)x0(1)+.+(y(5)-h(x(5)x0(5)=0.01（400+330+369+232+540）=18.711=0+0.01(y(1)-h(x(1)x1(1)+.+(y(5)-h(x(5)x1(5)=0.01（400*2104+330*1600+540*3000)=42037.122=0+0.01(y(1)-h(x(1)x2(1)+.+(y(5)-h(x(5)x2(5)=0.01(400*3+330*3+369*3+540*4)=59.21得到 ，和matlab一次迭代结果一致。据此计算再

3、次代入迭代公式得到：用matlab程序迭代两次结果如图：发现第二次迭代和手工算也没有什么区别，当迭代150次时，结果都是NaN，已经发散了，于是用矩阵法求求解结果如下：用矩阵法求解线性回归问题依照公式得到 即其实这里，即为X的广义逆矩阵，如果X为方阵且可逆的话，则可得到，矩阵法误差分析绝对误差向量，计算相对误差（采用第二范数）得这里看似是比较好的拟合结果，但其实这个结果并不稳定，也就是说如果每次观测的数据都有偏差，这个用最小二乘法的矩阵解法求出的解的差别可能千差万别，或者随着数据的不断输入，求的结果相差非常大，以至于感觉不能取得一个好的拟合结果，这就涉及到下面病态矩阵与条件数的知识了。病态矩阵

4、与条件数那么为什么用梯度下降算法迭代出现了发散呢？这里就涉及到了病态矩阵的概念了，而判断矩阵是否病态的准则就是条件数！求解方程组时如果对数据进行较小的扰动，则得出的结果具有很大波动，这样的矩阵称为病态矩阵。求解方程组时对数据的小扰动很敏感的矩阵。解线性方程组Ax=b时，若对于系数矩阵A及右端项b的小扰动A、b,方程组(A+A)=b+b的解与原方程组Ax=b的解差别很大，则称矩阵A为病态矩阵。下面给出一个病态矩阵的例子：病态矩阵实例可见非常小的扰动能引起解的非常大的变化，这样的矩就被称为病态矩阵。解决病态矩阵的解的问题也是现在研究的一个热点，在求解任何反问题的过程中通常会遇到病态矩阵问题，而且病

5、态矩阵问题还未有很好的解决方法，尤其是长方形、大型矩阵。目前主要有Tikhonov、奇异值截断、奇异值修正、迭代法等方法。得到定义1：设 ，|.|是Cnxn上的一个矩阵范数.矩阵A的条件数定义为条件数的定义与计算 -条件数：1-条件数：2-条件数：常用的条件数条件数的计算对于条件数的计算matlab给出了很好的支持，在matlab中可以用cond（X，p）函数来计算，X表示要计算条件数的矩阵，p表示p条件数，p如果不给出的话matlab默认值为2，即计算2条件数。下面用matlab计算上面矩阵条件数从以上实验结果可以看出矩阵不可逆的化条件数为无穷，且不可逆性约强的话（其实这个时候就是各个分量之

6、间的平行性越强）矩阵的条件数越大。以该矩阵为参数的线性方程解的波动性也就会越大。最小二乘法梯度迭代法与矩阵求解比较回到最初房屋价格问题，计算矩阵的条件数可以得到如下结果：可见该矩阵条件数非常之大，也就是该矩阵方程病态很严重，用矩阵解法虽然可以解出方程的解，但是该解是极不稳定的。下面给出梯度迭代法与矩阵求解最小二乘问题的异同：对于用梯度迭代法，结果是慢慢迭代而出的，如果出现了结果的不稳定性非常严重（原因就是矩阵病态，条件数过大），则可能出现迭代不收敛的情况（本例就是一个很好的例子），求不出最小二乘的参数。对于矩阵法，给出数据就可以得到结果，不论矩阵是否病态，但如果矩阵病态的话，数据小的波动会引起

7、解非常大的改变，如果数据在增加，则可能连续得出的解千差万别以至于得不到好的解。牛顿法求解极值存在的问题给定初值重复直到收敛其中H为海森矩阵， 为梯度向量称为海森矩阵(Hessian matrix)NxN维矩阵，N为特征变量数量，若考虑0，则实际上是(N+1)x(N+1)维简单二维向量例子求 的极值。按照推到公式第一步求出海森矩阵H海森矩阵H=代入迭代公式，令得到此时已将收敛，所以极值点为 ，极值为 3 如果将前面的系数改为2，则海森矩阵不可逆，此时牛顿迭代法不可用，因为此时只要满足 都可以是方程的解，方程欠定，有无穷解，牛顿迭代法只能解决适定方程，即解是唯一固定的，且不能直接得出是极大值还是极

8、小值。这是它的缺陷。对结果进行反思该方程实际上是没有极值点的，理由如下：令两个x相等，则3是极小值，令两个x相反，则3是极大值。实际上，0点只是梯度为零的点而不是极值点，牛顿迭代法求出的点是梯度为0即认为是极值点，这在一般情况下成立，但这种情况不成立，函数陷入了扁平化区域。画出函数的三维图发现，在0点附近一三象限取值为正，二四象限取值为负，这时候牛顿迭代法也不适用了。Matlab绘图如下：用matlab验证f=x(1)2+3*x(1)*x(2)+x(2)2;x,fval,exitflag,output=fminsearch(f,1 1);运行程序结果如下：可以发现exitflag为0，也就标志着极值不存在，画图也可看出极值不存在对梯度下降算法与牛顿法的理解梯度下降算法与牛顿法其实是一本同根的，用他们求极值其实都是找出梯度为0的点即认为是极值点，这在凸优化问题中是合适的，当处理扁平问题时是有bug的，即在这类问题中梯度为0的点不一定是极值点，这是这两大算法的致命缺点。随机梯度下降算法的迭代法与矩阵解法也是各有优劣，在矩阵非病态的情况下两者都能得到较好的结果，数据较少时采用矩阵法可以很快的得到结果，数据较多时求逆运算耗时不方便，多用梯度迭代法，而且迭代结果收敛。当矩阵病态时，梯度迭代法可能出现发散，矩阵求解法可以得出结果但随着数据的波动变化太大，得不到好的估计，但是矩