牛顿法和拟牛顿法

§4.6.5牛顿法拟牛顿法&x1x20Penaltymethod•实际化工过程数学模型：求解复杂、计算量大•数值算法实现模型求解：迭代形式逐渐逼近最优解x*，•求解过程：在可行域范围或非可行域内按照一定策略搜索最优值的问题。•初始点更新点最优解X*•判断所得点是否足够接近𝜺，满足则停止搜索•系统思想•迭代法共同特点：对求解变量的数值进行逐步改进，使之从开始不能满足方程的要求，逐渐逼近方程所要求的解，每一次迭代所提供的信息（表明待解变量的数值同方程的解尚有距离的信息），用来产生下一次改进值，迭代方案有多种，这就形成了不同的迭代方法。变量轮换单纯形法最速下降法共轭梯度法牛顿法&拟牛顿法系统思想一.牛顿法•1.问题提出•最速下降法：当前迭代点Xk,迭代简单，但容易产生锯齿现象，使得收敛缓慢，即一阶逼近函数得到的模型比较粗糙。•提高逼近阶数•牛顿法：二阶逼近函数算法，快速收敛•()minfX牛顿迭代最速下降图4-12从目标函数值近似值的观点比较最速下降法和牛顿法一、牛顿法将f(xk+1)在x=xk处一阶泰勒展开：)()()(1'1kkkkkxxxfxfxf目标函数趋于零0)()()('1'kkkkkxxfxxfxf)()(1'1kkkkxfxfxx一.牛顿法将f(xk+1)在x=xk处二阶泰勒展开：2111)(21)(')()(kkkkkkkkxxxfxxxfxfxf目标函数趋于零一.牛顿法——一维搜索简化公式'1''()()kkkkfxxxfx-1'''=()()kkkxfxfx一.牛顿法处的二次近似值：在)(假定要求kXxf))(()(21))(()()(展开：处进行二阶在点)()(2)()()()()(kkTkkkTkkxxxfxxxxxfxfxfTaylorx))(()()()()(2)(kkkxxxfxfxf))(()()()1()()1(2)1()(kkkkkxxxfxfxf推广到多元函数情况，即得到求解多元函数极小的牛顿迭代算法：一.牛顿法：0令上式为0))(()()()1()()1(2)1()(kkkkkxxxfxfxf)()()(1)(2)()1(kkkkxfxfxx)()()(1)()()1(kkkkxfxHxx此时有,0)(则，0)(矩阵正定，即Hesse若1)()(kkxHxH——Newton迭代公式有,,比较迭代公式kk1kkSxx1-k1kkkhHS)()()()(2kkkkxfhxfH其中1.牛顿法几何解释几何直观解释：最密切的二次曲线逼近2.Newton算法•Step1:给初始点x0,精度ε0,k=0Step2:计算Step3:由方程组H(xk)△xk=-hk解出xk+1,当Hk可逆时，xk+1=xk-Hk-1.hkStep4:）(H和)(h2kkkkxfxfstep2转1,kk否则，令;xx停止,)(f若1*1kkx例1.设221212126+233fxxxxxxx分析:搜索方向解：1124,64,6344344,56,().56TTxxfffxxx故121212212622333fxxxxxxxx求在点1(4,6)Tx处的搜索方向.2(),()fxfx故需要写出的表达式.121212122622333fxxxxxxxx𝑺𝒌=−𝛁𝟐𝒇𝒙−𝟏𝛁𝒇(𝒙)2222124,64,62214,62124,6164,45656TTTTxxxxffxxfxxfxx故2222212212221212122112223,22322332233ffxxxxffxxxxxxxxxx2116456()564fx所以1211141()6201441fx进而得因此所求的牛顿方向为2116456()564fx由114344162014415611011556301123163𝒔𝟏=−𝛁𝟐𝒇𝒙−𝟏𝛁𝒇(𝒙)例2：用牛顿法求解：2201219min9,122Tfxxxx解：12()9xfxx，因所以迭代终止,10,fx最优点为:10,0.Txx1109099210()09fx100xxd0099111001/99991𝒔𝟎=−𝛁𝟐𝒇𝒙−𝟏𝛁𝒇(𝒙)3.牛顿法优缺点(1)对正定二次函数，迭代一次就可以得到极小点．(2)如果正定且初始点选取合适，算法很快收敛．优点𝑯∗(2)收敛性与初始点的选取依赖很大．(3)每次都需要计算海森阵计算量大．(4)每次都需要解方程组方程组有时奇异或病态的，无法确定𝑺𝒌或𝑺𝒌不是下降方向．(1)要求函数二阶可微.缺点𝛁𝟐𝒇𝒙𝒌𝛁𝟐𝒇𝒙𝒌∙∆𝒙𝒌=−𝛁𝒇(𝒙𝒌)二.阻尼牛顿法—Newton法改进这样往往可以克服上述缺点.针对缺点中的(2),在求新迭代点时，不直接用公式进行迭代，而是以作为搜索方向进行一维搜索，求步长，使1.基本思想ksk)(min0kkksxfkkksxxk1然后，令2.阻尼牛顿法算法Step1:给出0,01,0nxRkStep2:计算,kfx如果,kfx停．否则计算2(),kfx并令Step4:令转Step2.Step3:沿进行线搜索，得最优步长.kks,1,k1kksxxkkk𝑺𝒌=−𝛁𝟐𝒇𝒙−𝟏𝛁𝒇(𝒙)3.收敛性定理定理3.7xf二次连续可微，2fx正定．设kx是由阻尼牛顿法得到的迭代点列.记0.fx必有聚点,且任何聚点有界,kx若水平集0nLxRfxfxx满足则1.分析：Newton法优点：高收敛速度（二阶收敛）缺点：对初始点目标函数要求高，计算量，存储量大（需要计算、存储hessian矩阵及其逆矩阵）拟牛顿法——模拟牛顿法给出的一个“保优去劣”的算法考虑Newton迭代公式：搜索方向为进行改进：一、避免求逆矩阵，用则上式变为此时搜索方向为步长因子为二、更大的灵活性，一般化,...)2,1,0(,11khHxxkkkk1，步长因子sk1kkkhH11H替代HGkkk1s，xk1kkkkkkkhGhGx,1k长但步长因子取为最优步,s此时,...)2,1,0(,1kkkkkkkkhGkhGtxx时，阻尼牛顿法G当;法单位阵）时，最速下降(G当1kkkHI这样的Hk存在？1、为保证总是下降方向，要求每一个Gk均称为正定矩阵2、为易于计算，要求有简单的迭代形式，最简单的迭代关系为人为附加条件G并易于计算，对,s若存在，使kkkkhGkkkhGskkkGG1G为校正公式称为校正矩阵，称上式Gk拟牛顿条件分析：Hk-1需满足的条件，并利用此条件确定Gk由归纳法，若由Hk可求Hk+1,则在xk+1点，Taylor展开想到))(()-x（21）)(()()(f则),(H），(h），()(h记11211112kkkkkkTkkkkkxxxfxxxxfxfxxfxfxfx)(h111kkkkkxxHhkkkkkxxhh1111)(H1kkHG称为拟牛顿方程）(G则有d）()(y记)(G111111kkkkkkkkkkkkkkkkdyxxxfxfhhxxhh在确定拟牛顿方程式的Hk+1时，若矩阵Hk+1对称，则需要待定（n+n2)/2个未知数，n个方程，所以拟牛顿方程一般有无穷个解，故由拟牛顿方程确定的一族算法，通常称之为拟牛顿法拟Newton算法1、给定初始点x0,正定矩阵H0,精度ε0,k=02、计算搜索方向3、令xk+1=xk+tk.sk,其中tk为f(xk+tkSk)=minf(xk+tsk)4、若，则xk+1为最优解，否则转步骤55、按照校正公式Gk+1=Gk+△Gk,计算GK+1使得Gk+1满足拟牛顿条件或拟Newton方程：Gk+1*yk=dk令k=k+1,转步骤2)(skkkxfG)(11kkxfhkkkkkkkkkkkkxxdhhxxfyxfhxf11111,)(f-）(),(),(h令DFP算法1、DFP算法提出：(1)Davidon(2)Fletcher&Powell(3)多变量无约束优化2、如何确定△G(k)?——秩2校正法TkkkTkkkkkkkvvbuuaGGGG1HkkkkRvuRa,,,a待定：根据拟Newton条件：Gk+1yk=dk,我们有满足上述方程的解很多，可如下确定一组解则我们可以取kkkkTkkkTkkkkkkkkTkkkkyGdyvbyuudyvvbuuaGa即：)(kkkTkkkkkTkkkyGyvvbdyuua,1,1y,TkTkkkkkkkkkkyvbyGvuadu即由此得到Gk的DFP校正公式性质：H00,则可以推出Hk0正交继承性kkkkTkkkkkkTkkkkyGyyvbyGvyuaduT11,1,kkTkkTkkkkTkkTkkkyGyGyyGydddGG1DFP算法步骤将拟Newton法第5步骤改为:5、按DFP校正公式计算Gk,k=k+1,转步骤2kkTkkTkkkkTkkTkkkyGyGyyGysddHH1BFGS算法近似的拟牛顿条件Hesse逆1kkkdyG近似的拟牛顿条件B1HesseydkkkkkTkkTkkkkTkTkkkkkkkkdBdBddBydyyBBFGSGBy111B校正公式得,,d对换Summary非线性问题规划求解变量轮换法单纯形法最速下降法共轭梯度法牛顿法拟牛顿法无约束最优化问题有约束最优化问题单变量函数的优化——一维搜索多变量函数的优化策略系统思想Summary函数值搜索（零阶法）变量轮换法单纯形法梯度信息搜索（一阶法）最速下降法共轭梯度法二阶近似值搜索（二阶法）牛顿法拟牛顿法无约束多变量函数的优化策略1、选择初始点x0。当然初始点离最小点越近越好。2、确定搜索方向Sk，使目标函数从xk沿此方向下降。3、在xk方向上进行一维搜索。在由xk出发的射线x=xk+αkSk(αk≥0)上选取步长αk,使一元（α）函数f(xk+αkSk)在α=αk处取最小值。它是一个单变量函数极小问题。由此得到新点xk+1=xk+αkSk(αk≥0)4、检验xk+1是否最优解。共同缺点在于有多重局部解存在时，不一定能找出全局最优解Summary变量轮换法特点：可靠性较高，属于直接法，只需目标函数值信息，不需要目标函数导数。程序简单，易于掌握。但是搜索效率低，且越接近极值点，搜索速度越慢。单纯形法特点：是不需要复杂的导数运算，它朝最优点的移动完全由上一个单纯形的结果所定，计算机上使用时贮存少。但由于步长固定，故缺少加速的方法。单纯形：指多维空间的凸多边形的顶点数比空间维数多，如正四面体Summary最速