运筹学与最优化方法无约束最优化.pptx
第五章 无约束最优化 （f）min f(x)f:RnR 5.1 最优性条件 设 f 连续可微 必要条件：若x*l.opt.则f(x*)=0 (驻点)。当 f 凸时，x*l.opt.f(x*)=0 注意：f(x)f(x*)+Tf(x*)(x-x*),x.故 f(x*)f(x)，x.（由于Tf(x*)=0）5.2 最速下降法 在迭代点 x(k)取方向 d(k)=f(x(k)精确一维搜索 最 速 下降法：梯度方向函数值变化最快的方向第1页/共36页第五章 无约束最优化5.2 最速下降法（续）x(1),0,k=1|f(x(k)|0得 x(k+1)=x(k)+kd(k)k=k+1第2页/共36页第五章 无约束最优化5.2 最速下降法（续）特点：全局收敛，线性收敛，易产生扭摆现象而造成早停。（当x(k)距最优点较远时，速度快，而接近最优点时，速度下降）原因：f(x)=f(x(k)+Tf(x(k)(x-x(k)+o|x-x(k)|当 x(k)接近 l.opt.时 f(x(k)0，于是高阶项 o|x-x(k)|的影响可能超过Tf(x(k)(x-x(k)。5.3 Newton法及其修正一、Newton法：设f(x)二阶可微，取f(x)在x(k)点附近的二阶Taylor近似函数：qk(x)=f(x(k)+Tf(x(k)(x-x(k)+12(x-x(k)T2f(x(k)(x-x(k)求驻点：qk(x)=f(x(k)+2f(x(k)(x-x(k)=0第3页/共36页第五章 无约束最优化Newton法：（续）当2f(x(k)正定时，有极小点：x(k+1)=x(k)-2f(x(k)-1 f(x(k)Newton迭代公式 实用中常用 2f(x(k)S=-f(x(k)解得s(k)x(k+1)=x(k)+s(k)x(1),0,k=12f(x(k)S=-f(x(k)得s(k),x(k+1)=x(k)+s(k)|s(k)|0 使 2f(x(k)+I 正定，尽量小。特点：全局二阶收敛。第8页/共36页无约束最优化-共轭梯度法一、共轭梯度法的方向：设f(x)=(1/2)xTGx+bTx+c Gnn对称正定，b Rn,从最速下降方向开始，构造一组共轭方向：设初始点x(1),取d(1)=-f(x(1)(最速下降方向)设k1,已得到k个相互共轭的方向d(1),d(2),d(k),以及，由x(1)开始依次沿上述方向精确一维搜索得到点x(2),，x(k),x(k+1).即有下式：x(i+1)=x(i)+id(i),i=1,2,k 精确一维搜索保证方向导数为0：fT(x(i+1)d(i)=0,i=1,2,k 在x(i+1)点构造新方向d(k+1)为-f(x(k+1)与d(1),d(2),d(k)的组合：第9页/共36页共轭梯度法一、共轭梯度法的方向：（续）使d(k+1)与d(1),d(2),d(k)都共轭：d(k+1)TG d(j)=0 ,j=1,2,k Gram-Schmidt过程：i,j=1,2,k 记 y(j)=f(x(j+1)-f(x(j)=G(x(j+1)-x(j)=jGd(j).根据式，有 d(i)T y(j)=j d(i)T G d(j)=0 ,ij 根据，有 d(k+1)T y(j)=j d(k+1)T G d(j)=0 ,j=1,2,k 这里的j应为i第10页/共36页共轭梯度法一、共轭梯度法的方向：（续）jk,ij 有 f(x(j+1)T d(i)=0 由式 由式 f(x(j+1)T f(x(i)=0 i0d(1)=-f(x(1),k=1k=k+1k=1|f(x(k)|0得 k x(k+1)=x(k)+k d(k)k=n?x(1)=x(n+1)d(1)=-f(x(1),k=1求 kd(k+1)=-f(x(k+1)+kd(k)yNyN重新开始第14页/共36页5.4 共轭梯度法三、算法特点：1、全局收敛（下降算法）；线性收敛；2、每步迭代只需存储若干向量（适用于大规模问题）；3、有二次终结性（对于正定二次函数，至多n次迭代可达opt.）注：对不同的 k公式，对于正定二次函数是相等的，对非正定二次函数，有不同的效果，经验上PRP效果较好。第15页/共36页变尺度法一、变尺度法的基本思路：(f)min f(x),f:R n R1、基本思想：用对称正定矩阵H(k)近似2f(x(k),而H(k)的产生从给定H(1)开始逐步修整得到。2、算法框图：x(1),H(1)对称0,k=1d(k)=-H(k)f(x(k)一维搜索得kx(k+1)=x(k)+k d(k)|x(k+1)-x(k)|0那么DFP法产生的 对称正定。注：下列各情况下有sTy0：1 f(x)为正定二次函数；2 精确一维搜索时；3 前章介绍的不精确一维搜索时。可以证明：DFP法在精确一维搜索前提下，超线性收敛。2、BFGS法 若把前面的推导，平行地用在y=Bs公式上，可得到第23页/共36页二、2、BFGS法（续）用此公式求方向时，需用到矩阵求逆或解方程：d=-B-1 f(x)或 Bd=-f(x)由于每次只有秩2的变换，这里的计算量仍可以降下来。为了得到H-公式，可对上面 求逆（推导得）：BFGS法有变尺度法的全部优点，并且在一定条件下可以证明在BFGS法中使用前文中介绍的不精确一维搜索有全局收敛性。第24页/共36页三、Broyden族 当在秩2公式中，、任意选取时可得到不同的公式，经过理论推导，可得到下列结果：第25页/共36页三、Broyden族（续）第26页/共36页直接算法 min f(x)一、单纯形法及可变多面体算法1、单纯形法基本思路：设 x(0),x(1),x(n)是R n中n+1个点构成的一个当前的单纯形。比较各点的函数值得到：x max,x min使 f(x max)=maxf(x(0),f(x(1),f(x(n)f(x min)=minf(x(0),f(x(1),f(x(n)取单纯形中除去x max点外，其他各点的形心：去掉x max，加入x(n+1)得到新的单纯形。重复上述过程。第27页/共36页一、1、单纯形法基本思路：（续）几点注意：当x(n+1)又是新单纯形的最大值点时，取次大值点进行反射；若某一个点x出现在连续m个单纯形中的时候，取各点与x连线的中点（n个）与x点构成新的单纯形，继续进行。经验上取 2 例如：n=2时，可取 2 可取 m=4.12345789106111213第28页/共36页一、1、单纯形法基本思路：（续）优点：不需求导数，不需要一维搜索。缺点：无法加速，收敛慢，效果差。2、改进单纯形法：（可变多面体算法）设第k步迭代得到n+1个点：x(0),x(1),x(n)，得到x max,x min及 通过下列4步操作选新迭代点：1 反射：取反射系数 0,(单纯形法中=1)2 扩展：给定扩展系数 1,计算。（加速）第29页/共36页一、2、改进单纯形法：（续）若f(y(1)f(y(2),那么y(2)取代x max;否则，y(1)取代x max。若maxf(x(i)|x(i)x max f(y(1)f(x min),y(1)取代x max。3 收缩：若f(x max)f(y(1)f(x(i),x(i)x max,计算 ,以y(3)取代x max。4 减半：若f(y(1)f(x max),重新取各点，使 x(i)=x min+1 2(x(i)-x min)得到新单纯形。经验上：0.6,2.3.有人建议:=1,=0.5，=2 。算法停机准则取：第30页/共36页二、模式搜索法：Hooke&Jeeves 19611、基本思想与主要过程：利用两类移动（探测性移动和模式性移动）进行一步迭代：探测性移动的目的：探求一个沿各坐标方向的新点并得到 一 个“有前途”的方向；模式性移动的目的：沿上述“有前途”方向加速移动。主要过程：第k步迭代，设已得到x(k)1探测性移动：给定步长k，设通过模式性移动得到y(0),依次沿各坐标方向e(i)=(0,1,0,0)T i 移动k步长：i=0,1,n-1 ,=y(i)+e(i+1)若f()f(y(i),则 y(i+1)=第31页/共36页二、1、基本思想与主要过程：（续）否则取 =y(i)+e(i+1)若f()f(y(i),则 y(i+1)=否则 y(i+1)=y(i)最后得到y(n)。若f(y(n)f(x(k),令x(k+1)=y(n).2模式性移动：x(k+1)-x(k)为一个有前途的方向，取 y(0)=x(k+1)+(x(k+1)-x(k)=2 x(k+1)-x(k)f(y(0)f(x(k+1)?3 几点措施：若探测性移动得到y(n)使f(y(n)f(x(k),则跳过模式性移动而令y(0)=x(k)重新进行探测性移动，初始y(0)=x(1)；第32页/共36页二、1、基本思想与主要过程：（续）若y(n)=y(0)（即每一个坐标方向的移动都失败），减小 k，重复上述过程。当进行到k充分小（k 0计算f=f(x)f1=f(y(0),i=1y(i)=y(i-1)+e(i)计算f2=f(y(i)f2f1?f1=f2in?yesyes1Noi=i+12Noy(i)=y(i-1)+(-)e(i)计算f2=f(y(i)f2f1?y(i)=y(i-1)yesNo第34页/共36页二、2、算法：(续)1f1f?Noyes=y(n),y(0)=2 -xx=,f=f(x)y(n)=x?Noy(0)=xYes?YesNo=0.1 2停；x为解第35页/共36页感谢您的观看！第36页/共36页
