无约束最优化方法PPT课件.ppt

第 五 章无约束最优化方法第五章 无约束最优化 （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) ) 精确一维搜索 最 速 下降法：梯度方向函数值变化最快的方向第五章 无约束最优化5.2 最速下降法（续）x(1), 0, k=1| f(x(k) ) |0得 x(k+1)=x(k)+kd(k)k=k+1第五章 无约束最优化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第五章 无约束最优化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 正定， 尽量小特点：全局二阶收敛第五章 无约束最优化5.4 共轭梯度法一、共轭梯度法的方向： 设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)的组合：第五章 无约束最优化5.4 共轭梯度法一、共轭梯度法的方向： （续）使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第五章 无约束最优化5.4 共轭梯度法一、共轭梯度法的方向： （续） 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重新开始第五章 无约束最优化5.4 共轭梯度法三、算法特点： 1、全局收敛（下降算法）；线性收敛； 2、每步迭代只需存储若干向量（适用于大规模问题）； 3、有二次终结性（对于正定二次函数，至多n次迭代可达opt.） 注：对不同的 k公式，对于正定二次函数是相等的，对非正定二次函数，有不同的效果，经验上PRP效果较好。

第五章 无约束最优化5.5 变尺度法一、变尺度法的基本思路： (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公式上，可得到第五章 5.5 变尺度法二、2、BFGS法（续）用此公式求方向时，需用到矩阵求逆或解方程： d= -B-1 f(x) 或 Bd= - f(x)由于每次只有秩2的变换，这里的计算量仍可以降下来为了得到H-公式，可对上面 求逆（推导得）：BFGS法有变尺度法的全部优点，并且在一定条件下可以证明在BFGS法中使用前文中介绍的不精确一维搜索有全局收敛性 第五章 5.5 变尺度法三、Broyden族 当在秩2公式中，、 任意选取时可得到不同的公式，经过理论推导，可得到下列结果：第五章 5.5 变尺度法三、Broyden族（续）第五章 无约束最优化 5.6 直接算法 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)得到新的单纯形重复上述过程第五章 5.6 直接算法一、1、单纯形法基本思路： （续）几点注意： 当x(n+1)又是新单纯形的最大值点时，取次大值点进行反射； 若某一个点x出现在连续m个单纯形中的时候，取各点与x连线的中点（n个）与x点构成新的单纯形，继续进行经验上取 m 1.65n+0.05n2 例如：n=2时，可取m 1.65 2+0.05 4 =3.5 可取 m=4.12345789106111213第五章 5.6 直接算法一、1、单纯形法基本思路： （续） 优点：不需求导数，不需要一维搜索 缺点：无法加速，收敛慢，效果差2、改进单纯形法： （可变多面体算法） 设第k步迭代得到n+1个点： x(0),x(1), x(n) ，得到x max,x min及 通过下列4步操作选新迭代点： 1 反射： 取反射系数 0,(单纯形法中 =1) 2 扩展：给定扩展系数 1,计算。

加速）第五章 5.6 直接算法一、 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 ) 得到新单纯形经验上：=1,0.40.6, 2.33.0 . 有人建议:=1, =0.5， =2 算法停机准则取：第五章 5.6 直接算法二、模式搜索法： 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) =第五章 5.6 直接算法二、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) ；第五章 5.6 直接算法二、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第五章 5.6 直接算法二、2、算法： (续)1f1f ?Noyes =y(n), y(0)=2 -xx= ,f=f(x)y(n)=x?Noy(0)=xYes ?YesNo=0.1 2停；x为解。