第5章-无约束最优化方法--筹学与最优化方法-课件.ppt

《第5章-无约束最优化方法--筹学与最优化方法-课件.ppt》由会员分享，可在线阅读，更多相关《第5章-无约束最优化方法--筹学与最优化方法-课件.ppt（36页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第 五五 章章无约束最优化方法无约束最优化方法第五章第五章 无约束最优化无约束最优化 （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)精确一维搜索精确一维搜索 最最 速速 下降法：梯度方向函数值变化最快的方下降法：

2、梯度方向函数值变化最快的方向向第五章第五章 无约束最优化无约束最优化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.

3、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法法：（续）（续）特点：二阶收敛，局部收敛。特点：二阶收敛，局

4、部收敛。（当当x(k)充分接近充分接近x*时时,局部函数可用正定二次函数很好地近似，局部函数可用正定二次函数很好地近似，故收敛很快故收敛很快）二次终结性：当二次终结性：当f(x)为正定二次函数时，从任意初始点可一步迭为正定二次函数时，从任意初始点可一步迭代达到最优解。代达到最优解。设设f(x)=12xTQx+PTx+r ,Qnn对称正定，对称正定，P Rn,r R.x(1),f(x(1)=Q x(1)+P 2f(x(1)=Q 迭代：迭代：x(2)=x(1)-Q 1(Qx(1)+P)=-Q 1 P (驻点即驻点即opt.)主要缺点：主要缺点：(1)局部收敛局部收敛 (2)用到二阶用到二阶Hess

5、e阵，且要求正定阵，且要求正定 (3)需计算需计算Hesse阵逆或解阵逆或解n阶线性方程组，计算量大阶线性方程组，计算量大第五章第五章 无约束最优化无约束最优化5.3 Newton法及其修正法及其修正二、二、Newton法的改进：法的改进：(1)为减小工作量，取为减小工作量，取m（正整数），使每正整数），使每m次迭代使用同一个次迭代使用同一个Hesse阵，迭代公式变为：阵，迭代公式变为：x(km+j+1)=x(km+j)-2f(x(km)-1 f(x(km+j)j=0,1,2,m-1 ,k=0,1,2,特点：收敛速度随特点：收敛速度随m的增大而下降的增大而下降 m=1时即时即Newton法，法

6、，m 即线性收敛。即线性收敛。(2)带线性搜索的带线性搜索的Newton法：法：在在Newton迭代中，取迭代中，取d(k)=-2f(x(k)-1 f(x(k),加入线性搜索：加入线性搜索：min f(x(k)+k d(k)求得求得k,x(k+1)=x(k)+kd(k)特点：可改善局部收敛性，当特点：可改善局部收敛性，当d(k)为函数上升方向时，可向负方为函数上升方向时，可向负方向搜索，但可能出现向搜索，但可能出现 d(k)均非下降方向的情况。均非下降方向的情况。第五章第五章 无约束最优化无约束最优化5.3 Newton法及其修正法及其修正二、二、Newton法的改进：法的改进：（续）（续）(

7、3)Goldstein-Price方法方法(G-P法法)：取取 d(k)=-2f(x(k)-1 f(x(k)，2f(x(k)正定正定 -f(x(k)，否则否则采用下列精确一维搜索：采用下列精确一维搜索：求求k，使其中使其中(0,12)1 f(x(k)+k d(k)f(x(k)+f(x(k)Td(k)k 2 f(x(k)+k d(k)f(x(k)+(1-)f(x(k)Td(k)k特点：在一定条件下，特点：在一定条件下，G-P法全局收敛。法全局收敛。但当但当2f(x(k)非正定情况较多时，收敛速度降为非正定情况较多时，收敛速度降为接近线性。接近线性。第五章第五章 无约束最优化无约束最优化5.4 共

8、轭梯度法共轭梯度法一、共轭梯度法的方向：一、共轭梯度法的方向：设设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 精确一维

9、搜索保证方向导数为精确一维搜索保证方向导数为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).

10、根据根据式，有式，有 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 共轭梯度法共轭梯度法一、共轭梯度法的方向：一、共轭梯度法的方向：（续）（续）上式中由上式中由式有：式有：-f(x(k+1)T f(x(j+1)=0 由由式有：式有：j(k)d(j)T y(j)=j(k)jd(j)T Gd(j)于是于是 j(k)=0 故故式中只有式中只有 k(k)0,记记k=k(k)可得到公式：可得到公式：d(k+1)=-f(x

11、(k+1)+k d(k)当当 j=k时，由时，由,式得：式得：(11)注意：注意：第五章第五章 无约束最优化无约束最优化二、算法流程图x(1),0d(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、每步迭代只需存储若干向量（适用于、每步迭代只需存

12、储若干向量（适用于大规模问题）；大规模问题）；3、有二次终结性（对于正定二次函数，、有二次终结性（对于正定二次函数，至多至多n次迭代可达次迭代可达opt.）注：对不同的注：对不同的 k公式，对于正定二次函数公式，对于正定二次函数是相等的，对非正定二次函数，有不同是相等的，对非正定二次函数，有不同的效果，经验上的效果，经验上PRP效果较好。效果较好。第五章第五章 无约束最优化无约束最优化5.5 变尺度法变尺度法一、变尺度法的基本思路：一、变尺度法的基本思路：（续）（续）3、拟、拟Newton方程：方程：记：记：s(k)=x(k+1)-x(k),y(k)=f(x(k+1)-f(x(k)当当 f 为

13、二次函数时：为二次函数时：f(x)=1 2xTBx+c T x+b f=B x+c 有有 y(k)=Bs(k)或或 s(k)=B-1 y(k)称称 H y=S 或或 y=BS 为拟为拟Newton方程。方程。显然显然 当当H 正定时正定时,B-1=H.4、”近似近似”：对于对于f(x)的二阶的二阶Taylor展式，舍去高阶项，展式，舍去高阶项，有有 y(k)2f(x(k)s(k)或或 s(k)(2f(x(k)-1 y(k)用矩阵用矩阵B(k)或或H(K)分别取代分别取代 2f(x(k)或者或者(2f(x(k)-1使拟使拟Newton方程成立，可看作是对方程成立，可看作是对 2f(x(k)或或(

14、2f(x(k)-1的一的一种近似。此种近似种近似。此种近似H 或或 B 不唯一。不唯一。第五章第五章 无约束最优化无约束最优化5.5 变尺度法变尺度法一、变尺度法的基本思路：一、变尺度法的基本思路：（续）（续）5、变尺度法的主要特点：、变尺度法的主要特点：只需用到函数的一阶梯度；（只需用到函数的一阶梯度；（Newton法用到二阶法用到二阶Hesse阵）阵）下降算法，故全局收敛；下降算法，故全局收敛；不需求矩阵逆；（计算量小）不需求矩阵逆；（计算量小）一般可达到超线性收敛；（速度快）一般可达到超线性收敛；（速度快）有二次终结性。有二次终结性。二、二、DFP(Davidon(1959),Fletc

15、her and Powell(1963)法和法和 BFGS(Broyden(1970),Fletcher(1970),Goldfarb(1970),Schanno(1970)法法:1、DFP法：法：以下省去各量上标，以下省去各量上标，x,s,y,H 表示第表示第k 步的量，步的量，等表示第等表示第k+1步的量。步的量。第五章第五章 无约束最优化无约束最优化5.5 变尺度法变尺度法二、二、DFP 法和法和BFGS 法法:1、DFP法：法：（续）（续）第五章第五章 5.5 5.5 变尺度法变尺度法变尺度法变尺度法二、二、1、DFP法：法：（续）（续）Ex.用用DFP法求解法求解 10 x12+x2

16、2解：取初始点解：取初始点x(1)=(110,1)T,H(1)=I (单位矩阵单位矩阵)得到如下结果：得到如下结果：（计算过程见下页计算过程见下页）第五章第五章 5.5 5.5 变尺度法变尺度法变尺度法变尺度法二、二、1、DFP法：法：（续）（续）计算过程：计算过程：第五章第五章 5.5 5.5 变尺度法变尺度法变尺度法变尺度法二、二、1、DFP法：法：（续）（续）定理：设定理：设H对称正定，对称正定，sTy0那么那么DFP法产生的法产生的 对称正定。对称正定。注：注：下列各情况下有下列各情况下有sTy0：1 f(x)为正定二次函数；为正定二次函数；2 精确一维搜索时；精确一维搜索时；3 前章

17、介绍的不精确一维搜索时。前章介绍的不精确一维搜索时。可以证明：可以证明：DFP法在精确一维搜索前提下，超线性收敛。法在精确一维搜索前提下，超线性收敛。2、BFGS法法 若把前面的推导，平行地用在若把前面的推导，平行地用在y=Bs公式上，可得到公式上，可得到第五章第五章 5.5 5.5 变尺度法变尺度法变尺度法变尺度法二、2、BFGS法（续）法（续）用此公式求方向时，需用到矩阵求逆或解方程：用此公式求方向时，需用到矩阵求逆或解方程：d=-B-1 f(x)或或 Bd=-f(x)由于每次只有秩由于每次只有秩2的变换，这里的计算量仍可以的变换，这里的计算量仍可以降下来。为了得到降下来。为了得到H-公式

18、，可对上面公式，可对上面 求逆求逆（推导得）：（推导得）：BFGS法有变尺度法的全部优点，并且在一定条法有变尺度法的全部优点，并且在一定条件下可以证明在件下可以证明在BFGS法中使用前文中介绍的法中使用前文中介绍的不精确一维搜索有全局收敛性。不精确一维搜索有全局收敛性。第五章第五章 5.5 5.5 变尺度法变尺度法变尺度法变尺度法三、三、Broyden族族 当在秩当在秩2公式中，公式中，、任意选取时可得到不同的公式，经过任意选取时可得到不同的公式，经过理论推导，可得到下列结果：理论推导，可得到下列结果：第五章第五章 无约束最优化无约束最优化 5.6 直接算法直接算法 min f(x)一、单纯形

19、法及可变多面体算法一、单纯形法及可变多面体算法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.

20、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

21、直接算法直接算法一、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.

22、33.0.有人建议有人建议:=1,=0.5，=2 。算法停机准则取：算法停机准则取：第五章第五章 5.6 直接算法直接算法二、模式搜索法：二、模式搜索法：Hooke&Jeeves 19611、基本思想与主要过程：基本思想与主要过程：利用两类移动（探测性移动和模式性移动）进行一步迭代：利用两类移动（探测性移动和模式性移动）进行一步迭代：探测性移动的目的：探求一个沿各坐标方向的新点并得到探测性移动的目的：探求一个沿各坐标方向的新点并得到 一一 个个“有前途有前途”的方向；的方向；模式性移动的目的：沿上述模式性移动的目的：沿上述“有前途有前途”方向加速移动。方向加速移动。主要过程：第主要过程：第k步

23、迭代，设已得到步迭代，设已得到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

24、)=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为解