第三章无约束优化方法课件.ppt

1、3.1 3.1 引言引言一一.目的：目的：求一组求一组 n n 维设计变量维设计变量 X=xX=x1 1,x,x2 2,x,x n n T T,使目标函数达到使目标函数达到 min.f(x)XRmin.f(x)XRn n即求目标函数的最优解：最优点即求目标函数的最优解：最优点 x x*和最优值和最优值 f(xf(x*)。二二.意义：意义：l 为约束优化方法的研究提供了策略思想、概念基础和基本方法；为约束优化方法的研究提供了策略思想、概念基础和基本方法；l 为约束优化问题的间接解法提供了有效而方便的方法；为约束优化问题的间接解法提供了有效而方便的方法；l 对于某些工程问题，进行分析后，便于提供解

2、决的有效方法；对于某些工程问题，进行分析后，便于提供解决的有效方法；l 约束优化问题的求解往往可以通过一系列无约束优化方法实现；约束优化问题的求解往往可以通过一系列无约束优化方法实现；l 无约束优化问题的解法是优化设计方法的基本组成部分。无约束优化问题的解法是优化设计方法的基本组成部分。3.1 3.1 引言引言三三.内容：内容：一维搜索：一维搜索：求最优步长因子求最优步长因子(k)(k)多维（变量）优化：多维（变量）优化：确定搜索方向确定搜索方向 S(k)S(k)黄金分割黄金分割 切线法切线法 平分法平分法插值法插值法 格点法格点法坐标轮换法坐标轮换法 最速下降法最速下降法共轭方向法共轭方向法

3、 鲍威尔法鲍威尔法梯度法梯度法 共轭梯度法共轭梯度法牛顿法牛顿法 单形替换法单形替换法变尺度法变尺度法 3.1 3.1 引言引言四四.无约束优化方法计算步骤：无约束优化方法计算步骤：1、选择一个初始点、选择一个初始点x(0)，这一点越靠近极小点，这一点越靠近极小点x*越好。越好。2、若已经取得某设计点、若已经取得某设计点x(k)，并且该点不是近似极小点，则在，并且该点不是近似极小点，则在x(k)点根据函数点根据函数f(x)的性质，选择一个方向的性质，选择一个方向S(k)，并且沿此方向，并且沿此方向搜索函数值是下降的，称下降方向。搜索函数值是下降的，称下降方向。3、当搜索方向、当搜索方向S(k)

4、确定后，由确定后，由x(k)点出发，沿点出发，沿S(k)方向进行搜索，方向进行搜索，定出步长因子定出步长因子 (k)，得到新的设计点：，得到新的设计点：x(k+1)=x(k)+(k)S(k)，并满足并满足f(x(k+1)x2?f2*fP*?f2fP*?x3 x2 f3 f2x2 xp*f2 fP*x1 x2 f1 f2x2 xp*f2 fP*出口出口YYYNNNabcdx3 xp*f3 fP*x1 xp*f1 fP*二次插值法区间缩短流程图二次插值法区间缩短流程图3.2 3.2 一维搜索方法一维搜索方法24 与黄金分割法相比，二次插值法充分利用函数值的信息；与黄金分割法相比，二次插值法充分利用

5、函数值的信息；收敛快；调用函数次数少。收敛快；调用函数次数少。4.4.方法评价方法评价:5.5.迭代终止条件迭代终止条件:2424ff当满足如下两个条件，可终止迭代：当满足如下两个条件，可终止迭代：如果如果 和和 两点的距离很小，即：两点的距离很小，即：如果如果 和和 充分接近，即：充分接近，即：4f2f二次插值法的算法框图二次插值法的算法框图解：解：1）确定初始插值结点与函数值确定初始插值结点与函数值2()710f 11.525.22355.1105.121f5.7325.16355.7105.723f5.4)5.75.1(5.0225.10355.4105.422f15.15.725.22

6、25.1613131ffc15.75.4)1()5.15.4/()25.2225.10()/()(32112122cffc2）计算插值函数极小点计算插值函数极小点 例例3-3 用二次插值法求一维函数用二次插值法求一维函数 的最优解。的最优解。初始单谷搜索区间初始单谷搜索区间 ，迭代精度，迭代精度13,1.5,7.5 3105115.75.121)(212131*4ccp1035510524f075.8)55.7()5.15()(4314 5.42125.101f5.7325.163f5421035510522f由于判别式成立，表明由于判别式成立，表明 落在单谷搜索区间之内落在单谷搜索区间之内

7、44224ff3）缩短单谷搜索区间缩短单谷搜索区间 由于由于 和和 ，则舍弃左边的区间，则舍弃左边的区间 ，构成缩短后的新搜，构成缩短后的新搜索区间索区间 。即：。即：12,13,4）检验迭代终止条件检验迭代终止条件 25.45.725.1025.1613131ffc15.752)5.45/()25.1010()/()(32112122cffc5125.75.421)(2121314cc1035510524f3241005554*10)(4*fff满足迭代终止条件，输出最优解满足迭代终止条件，输出最优解()f00六六.切线法：切线法：一维搜索函数一维搜索函数 ，假定已给出较好的近似点，假定已给

8、出较好的近似点 ，连续可微的函，连续可微的函数在极小点附近与一个二次函数很接近，所以可以在数在极小点附近与一个二次函数很接近，所以可以在 附近用一个二附近用一个二次函数次函数 来逼近函数来逼近函数 ：()()f2000001()()()()()()()2ffff 以二次函数以二次函数 的极小点作为的极小点作为 极小点的一个新近似点极小点的一个新近似点 ，根，根据极值必要条件：据极值必要条件：()()f10)(0)()(0100 ff)()(0001ff,2,1,0)()(1 kffkkkk3.2 一维搜索方法一维搜索方法解：解：1)1)求函数的一阶、二阶导函数：求函数的一阶、二阶导函数：)12

9、(12)()433(4)(223 ff24212)1323(12)(52134)433333(4)(20230 ff16667.524523)()(0001 ff例例3-4 给定函数给定函数 ，初始值为，初始值为 ，控制误差控制误差 ，试用切线法求其极小点。，试用切线法求其极小点。432()46164f030.001 2)2)求求00(),()ff 3)3)求求14.000594.000664.039604.334745.1666784.0472086.86992109.44586184.3332240.005513.3829932.30199153.3518-524.000664.03960

10、4.334745.16667343210 kk)(kf)(kf 1k值 4)4)迭代值如下：迭代值如下：切切线线法法流流程程图图NY开始开始结束结束k=k+1)()(),(),(1kkkkkkffff 计算kkkorf11)(给定给定k=0,)()(1*kkff.收敛速度快；收敛速度快；.需要计算函数的一阶和二阶导数，增加迭代工作量；需要计算函数的一阶和二阶导数，增加迭代工作量；.要求初始点选得比较好，离极小点不远，否则有可能使极小要求初始点选得比较好，离极小点不远，否则有可能使极小化序列发散或收敛到非极小点。化序列发散或收敛到非极小点。切线法优缺点切线法优缺点:3.2 一维搜索方法一维搜索方

11、法3.2 一维搜索方法一维搜索方法 取具有极小点的单峰函数的探索区间取具有极小点的单峰函数的探索区间 a,ba,b 的坐标中点的坐标中点 作为计算点，计算目标函数在该点处的导数为作为计算点，计算目标函数在该点处的导数为 ，并利用，并利用函数函数在极小点处的导数为零而在其左侧为负、右侧为正在极小点处的导数为零而在其左侧为负、右侧为正的原理，来判断的原理，来判断极小点所在的那一半探索区间，以消掉另一半区间。这样逐次迭代极小点所在的那一半探索区间，以消掉另一半区间。这样逐次迭代下去，总能将探索区间收敛到一个局部极小点附近，求得极小点的下去，总能将探索区间收敛到一个局部极小点附近，求得极小点的近似解。

12、近似解。收敛速度虽然较慢，但缩短率也达到收敛速度虽然较慢，但缩短率也达到0.50.5，特别是每次迭代计算量，特别是每次迭代计算量较少，可靠性较好，所以仍然是一个受欢迎的方法。较少，可靠性较好，所以仍然是一个受欢迎的方法。0.5()ab七七.平分法：平分法：()f3.2 一维搜索方法一维搜索方法12,kka b 0.5()kkkabkkba平分法的迭代计算步骤平分法的迭代计算步骤:给定给定 计算计算 ，若，若 ，则停止迭代并取，则停止迭代并取 否则进行下一步。否则进行下一步。计算计算 ，若，若 或或 ，则停止迭代并取，则停止迭代并取 若若 则取则取 为缩短后的搜索区间为缩短后的搜索区间 转第二步

13、转第二步 若若 则取则取 为缩短后的搜索区间为缩短后的搜索区间 转第二步转第二步*k()kf()0kf()kf*k()0kf,kkb1,1kkab()0kf,kka1,1kkab当当 求解困难时求解困难时:()kf 可直接计算可直接计算 并比较两者大小，用序列消去法原并比较两者大小，用序列消去法原理消去掉近一半的区域，再重新迭代，直到将探索区间缩短至精度要理消去掉近一半的区域，再重新迭代，直到将探索区间缩短至精度要求为止。求为止。(),()kkff例例3-5 试用平分法求试用平分法求 的极小点和极小值，设的极小点和极小值，设解：解：1)1)取取 2)2)计算计算 3)3)缩短搜索区间为缩短搜索

14、区间为 取取 4)4)计算计算 5)5)所以函数的极小点为所以函数的极小点为 ,极小值为极小值为:2()1036f,2,6,0.01a b10.5()4ab11()21020f 1,4,6a bb20.5()5ab22()2100f*5*2()510 53611f 3.2 一维搜索方法一维搜索方法 设一维函数为设一维函数为f(x)，搜索区间为，搜索区间为a,b，一维收敛精度为，一维收敛精度为。在区间在区间a,b的内部取的内部取n个等分点：个等分点：x1,x2,xn。区间被分为区间被分为n+1等分，各分点坐标为等分，各分点坐标为 对应各点的函数值为对应各点的函数值为y1,y2,yn+2。比较其大

15、小，取最小者。比较其大小，取最小者ym=minyk,k=1,2,n2，则在区间，则在区间 x xm-1m-1,x,xm+1m+1 内必包含极小内必包含极小点，取点，取 x xm-1m-1,x,xm+1m+1 为缩短后新区间，若新区间满足收敛条件为缩短后新区间，若新区间满足收敛条件:x m+1-xm+1 ，则最优解为，则最优解为x*=xm，y*=ym 若不能满足精度要求，把当前区间作为初始搜索区间，重复上若不能满足精度要求，把当前区间作为初始搜索区间，重复上述步骤直至满足精度为止。述步骤直至满足精度为止。八八.格点法：格点法：(1)1,2,21kbaxak(k.,n)n 新区间新区间y1ym-1

16、ymym+1Yn2x1axm-1xmxm+1Xn2b格点法区间搜索原理格点法区间搜索原理格格点点法法流流程程图图YN开始开始p=y,m=k)(),1(1kkxfyknabaxyp给定给定,banm=0,k=1，p=足够大的数足够大的数k=nk=k+1,11mmxxba|b-a|Npfxxm*,YYN相同点：相同点：都是利用区间消去法原理将初始搜索区间不断缩短，从而都是利用区间消去法原理将初始搜索区间不断缩短，从而 求得极小点的数值近似解。求得极小点的数值近似解。不同点：不同点：试验点位置的确定方法不同。试验点位置的确定方法不同。直接法直接法中试验点的位置是由某种给定的规律确定的，并未考虑函数中

17、试验点的位置是由某种给定的规律确定的，并未考虑函数值的分布。值的分布。黄金分割法是按照等比例黄金分割法是按照等比例0.618缩短率确定的，仅仅利用了试验点缩短率确定的，仅仅利用了试验点函数值进行大小的比较；函数值进行大小的比较；间接法间接法中，试验点的位置是按函数值近似分布的极小点确定的，利中，试验点的位置是按函数值近似分布的极小点确定的，利用了函数值本身或其导数信息。用了函数值本身或其导数信息。当函数具有较好的解析性质时，间接方法比直接方法效果更好。当函数具有较好的解析性质时，间接方法比直接方法效果更好。3.2 一维搜索方法一维搜索方法九九.间接法与直接法的异同点：间接法与直接法的异同点：3

18、.2 一维搜索方法一维搜索方法 1.1.掌握进退法确定单谷搜索区间；掌握进退法确定单谷搜索区间；2.2.掌握黄金分割法的原理和程序设计；掌握黄金分割法的原理和程序设计；3.3.掌握二次插值法的原理和程序设计；掌握二次插值法的原理和程序设计；4.4.掌握切线法的原理和流程；掌握切线法的原理和流程；5.5.了解平分法和格点法。了解平分法和格点法。()sin()f十十.学习要求：学习要求：试用二次插值法求试用二次插值法求 的近似极小点和极小值，已知的近似极小点和极小值，已知十一十一.习题：习题：*45一一.坐标轮换法：坐标轮换法：1.1.基本思想：基本思想：2.2.搜索方向与步长：搜索方向与步长：每

19、次以一个变量坐标轴作为搜索方向，将每次以一个变量坐标轴作为搜索方向，将n维的优化问题转化为一维搜索问题。例，第维的优化问题转化为一维搜索问题。例，第k轮迭代的第轮迭代的第i i次搜索，是固定除次搜索，是固定除xi外的外的n-1个变个变量，沿量，沿xi变量坐标轴作一维搜索，求得极值点变量坐标轴作一维搜索，求得极值点 xi(k)n次搜索后获得极值点序列次搜索后获得极值点序列x1(k),x2(k,xn(k)，若未收敛，则开始第，若未收敛，则开始第k+1次迭代，直至次迭代，直至收敛到最优点收敛到最优点x*。：次搜索的收敛条件轮第第；：次搜索的迭代公式轮第第；：次搜索的步长轮第第向；个设计变量的坐标轴方

20、为第次搜索的方向：轮第第)()()()()(1)()()()(,.,2,1,kikikikikikikikikiSikniSxxikSikiSik3.3 坐标轮换法、共轭方向法和坐标轮换法、共轭方向法和Poweel法法一一.坐标轮换法：坐标轮换法：3.3.方法评价：方法评价：方法简单，容易实现。方法简单，容易实现。当维数增加时，效率明显下降。当维数增加时，效率明显下降。收敛慢，以振荡方式逼近最优点收敛慢，以振荡方式逼近最优点。受目标函数的性态影响很大。受目标函数的性态影响很大。如图如图 a)a)所示，二次就收敛到极值点；所示，二次就收敛到极值点；如图如图 b)b)所示，多次迭代后逼近极值点；所

21、示，多次迭代后逼近极值点；如图如图 c)c)所示，目标函数等值线出现山脊（或所示，目标函数等值线出现山脊（或称陡谷），在脊线的尖点称陡谷），在脊线的尖点A处没有一个坐标方向可处没有一个坐标方向可以使函数值下降，只有在锐角所包含的范围搜索才以使函数值下降，只有在锐角所包含的范围搜索才可以达到函数值下降的目的，故坐标轮换法对此类可以达到函数值下降的目的，故坐标轮换法对此类函数会失效。函数会失效。3.3 坐标轮换法、共轭方向法和坐标轮换法、共轭方向法和Poweel法法i=n坐坐标标轮轮换换法法的的流流程程图图开始开始给定：给定：x0,k=1i=1,x0k=x0 xik=x0k-1沿沿ei方向一维搜索

22、求方向一维搜索求 ixik=xi-1k+ikeix=xk f=f(x)|xnk-x0k|x*=x f*=f(x*)结束结束i=i+1x0k+1=xnkk=k+1NYNY此问题可用一维优化方法求解，此问题可用一维优化方法求解，这里用微分学求解：这里用微分学求解：解：解：1.1.作第一轮迭代计算作第一轮迭代计算11)1(0)1(1e xx0010011)1(1x51得：得：2222)1(1)1(251005exx1)1)沿沿e1方向进行一维搜索方向进行一维搜索例例4-1 用坐标轮换法求目标函数用坐标轮换法求目标函数 的无约束最优解，给定初始点的无约束最优解，给定初始点 ，精度要求，精度要求2212

23、1212()10460F xxxx xxx(0)(0)120 0 xx 0.1其中其中 为第一轮的起始点。为第一轮的起始点。取：取：(1)0 x(1)(0)0 xx按最优步长原则确定按最优步长原则确定1(1)2111min()1060F x(1)150 x2)2)以以 为新起点，沿为新起点，沿e2方向方向一维搜索：一维搜索：(1)1x按最优步长原则确定按最优步长原则确定2(1)2222min()935F x24.5得：得：(1)254.5x3)3)按迭代终止条件检验按迭代终止条件检验(1)(1)222054.56.7xx 2.2.作第二轮迭代计算，如此作第二轮迭代计算，如此共进行共进行9 9轮

24、得到结果轮得到结果*128,6,()8xxf x二二.共轭方向法共轭方向法：1.1.共轭方向的由来：共轭方向的由来：2.2.共轭方向的定义：共轭方向的定义：共轭方向概念是在研究具有正定矩阵共轭方向概念是在研究具有正定矩阵G的二次函数的二次函数 的极小化问题时形成的。其基本思想是在不用导数的极小化问题时形成的。其基本思想是在不用导数的前提下，在迭代中逐次构造的前提下，在迭代中逐次构造G的共轭方向。的共轭方向。共轭。阵则称这组向量是关于矩能满足若有一组非零向量，为正定实对称矩阵设正交。和则即，时则，为单位矩阵若的方向是共轭方向。和是关于矩阵共轭，和则称向量满足，和维向量若有两个，为实对称正定矩阵设

25、AjiASSSSSASSSSISSIASSSSASSSSnAjTinTTT),(0,.,00,02121212121212121CxBGxxxfTT21)(3.3 坐标轮换法、共轭方向法和坐标轮换法、共轭方向法和Poweel法法3.3.共轭方向法的二次收敛性：共轭方向法的二次收敛性：正定的二元二次函数的等值线为一组正定的二元二次函数的等值线为一组椭圆，任选初始点椭圆，任选初始点x0，沿某个下降方向，沿某个下降方向S0作一维搜索，得作一维搜索，得x1 此时，此时，x1点的梯度必然与方向点的梯度必然与方向S0垂直，垂直，即有：即有：1000 xxSx0 x*x1 1S1-f(x1)S1 0S010

26、()0Tf xS S0与某一等值线相切于与某一等值线相切于x1点。点。下一次的迭代，若选择负梯度方向为搜下一次的迭代，若选择负梯度方向为搜索方向，将产生锯齿现象。为避免锯齿的产生，我们取迭代方向索方向，将产生锯齿现象。为避免锯齿的产生，我们取迭代方向S0直指极直指极小点小点x*，如图所示。，如图所示。若选定这样的方向，则对于二元二次函数只需进行若选定这样的方向，则对于二元二次函数只需进行S0 和和S1两次搜索就两次搜索就可以求得极小点可以求得极小点x*，即，即*111xxS3.3 坐标轮换法、共轭方向法和坐标轮换法、共轭方向法和Poweel法法3.3.共轭方向法的二次收敛性（续）：共轭方向法的

27、二次收敛性（续）：由于由于 ，当，当 时时 ，由由 是是 的极小的极小点，应满足极值必要条件，故点，应满足极值必要条件，故 即：即：等式两端同乘以等式两端同乘以 ,得得 ，故两个向量，故两个向量 ，是是G的的共轭向量。共轭向量。因此，若要使第二个迭代点成为正定二元二次函数的极小点，因此，若要使第二个迭代点成为正定二元二次函数的极小点，只要使只要使两次一维搜索的方向两次一维搜索的方向 ，关于函数的二阶导数矩阵关于函数的二阶导数矩阵G共轭就可以了。共轭就可以了。对于正定二次对于正定二次n维函数，从任意的初始点出发，沿着这维函数，从任意的初始点出发，沿着这n个共轭方向进个共轭方向进行一维搜索，就可以

28、得到目标函数的极小点。因此，对于二次函数来说，行一维搜索，就可以得到目标函数的极小点。因此，对于二次函数来说，经过经过n步搜索就可以达到函数的极小点。步搜索就可以达到函数的极小点。对于非二次对于非二次n维函数，可以用二阶泰勒级数将函数在极小点附近展开，维函数，可以用二阶泰勒级数将函数在极小点附近展开，省略去高于二次的项后可以得到函数的二次近似，同样按照二次函数构成省略去高于二次的项后可以得到函数的二次近似，同样按照二次函数构成共轭方向。共轭方向。11()f xGxb1*xx110S*x()f x*()0f xGxb*111111()()()0f xG xSbf xGS 0()TS01()0TS

29、GS 1S0S1S0S3.3 坐标轮换法、共轭方向法和坐标轮换法、共轭方向法和Poweel法法4.4.二维函数的共轭方向：二维函数的共轭方向：二维函数二维函数 ，任意给定某个方，任意给定某个方向向 ，按这个方向上的两条平行线进行一，按这个方向上的两条平行线进行一维搜索求得的极小点为维搜索求得的极小点为 和和 ，它们应，它们应该是方向为该是方向为 的两条平行线与目标函数等的两条平行线与目标函数等值线的切点。值线的切点。连接两个切点连接两个切点 和和 构成向量：构成向量：可以证明，如果二维函数的海塞矩阵可以证明，如果二维函数的海塞矩阵H是正定的，则是正定的，则S1向量与向量向量与向量S2满足条件：

30、满足条件：12(,)f x x1S(2)X1S(2)X2(2)(1)SXX021HSST(1)X(1)X具有这种性质的方向为关于正定矩阵具有这种性质的方向为关于正定矩阵H H的共轭方向。的共轭方向。3.3 坐标轮换法、共轭方向法和坐标轮换法、共轭方向法和Poweel法法 所以有：所以有：4.4.二维函数的共轭方向（续）：二维函数的共轭方向（续）：证明：证明：120TS HS 设二维函数在极值点设二维函数在极值点X*附近的二次泰勒展开式为：附近的二次泰勒展开式为：)()(5.0)()()()(*2*XXXfXXXXXfXfXfTT 由此得函数的一阶导数：由此得函数的一阶导数：)()()(*2*X

31、XXfXfXf)()()(*1*2*1XXXfXfXf）（）（)()()(*2*2*2XXXfXfXf）（）（由于由于S1为等值线的切线，故方向为等值线的切线，故方向S1应垂直于应垂直于X(1),X(2)的梯度方向：的梯度方向：3.3 坐标轮换法、共轭方向法和坐标轮换法、共轭方向法和Poweel法法 所以有：所以有：4.4.二维函数的共轭方向（续二维函数的共轭方向（续2 2）：）：两式相减得：两式相减得：由由 ，上式可简化为：，上式可简化为：0)()()()1(2*21121XXXfSXfXfSTT）（）（）（2(2)(1)SXX 0)()(2*2112*1SXfSXXXfSTT）（）（120

32、TSHS )()()(*1*2*111XXXfXfSXfSTT）（）（)()()(*2*2*121XXXfXfSXfSTT）（）（3.3 坐标轮换法、共轭方向法和坐标轮换法、共轭方向法和Poweel法法5.5.二维函数共轭方向法的迭代过程：二维函数共轭方向法的迭代过程：1.1.令循环次数令循环次数k k1 1，取初始点，取初始点 ，初，初始搜索方向为坐标方向始搜索方向为坐标方向 4.取下次循环的初始点取下次循环的初始点 ，替换，替换掉原来的第一方向掉原来的第一方向 ，构成新的搜索方向：，构成新的搜索方向：(2)X(1)X5.k=k+15.k=k+1，转步骤，转步骤2 2。0kX121,0,0,

33、1kTkTSS 2.2.从从 出发，依次沿出发，依次沿 和和 进行一维进行一维搜索，分别得到相应的极小点搜索，分别得到相应的极小点 和和 。0kX1kS2kS 3.3.构建新方向构建新方向 ，沿，沿 方向方向进行搜索，得到第进行搜索，得到第k k次的极小点次的极小点320kkkSXX3kS3kX103kkXX1kS111223,kkkkSSSS3.3 坐标轮换法、共轭方向法和坐标轮换法、共轭方向法和Poweel法法6.6.多维二次函数共轭方向的构建：多维二次函数共轭方向的构建：如果如果n n维函数的海维函数的海赛矩阵是正定的，一赛矩阵是正定的，一组非零向量组非零向量 满足：满足：则向量系：则向

34、量系：是关于海赛矩阵是关于海赛矩阵H共共轭，即他们是轭，即他们是n个互个互为共轭的方向。为共轭的方向。12,nS SS0()TijS HSij(1,2,)iS in3.3 坐标轮换法、共轭方向法和坐标轮换法、共轭方向法和Poweel法法8.8.方法评价：方法评价：l 计算步骤复杂计算步骤复杂;l 是二次收敛方法，收敛快。对非正定函数，也很有效是二次收敛方法，收敛快。对非正定函数，也很有效;l 是比较稳定的方法。是比较稳定的方法。7.7.说明：说明：l 若是正定二次函数，若是正定二次函数，n n 轮迭代后收敛于最优点轮迭代后收敛于最优点 x x*。若是非正定二次函数，则迭代次数增加。若是非正定二

35、次函数，则迭代次数增加。l 若是若是 n n 维问题，步骤相同。维问题，步骤相同。搜索方向：第一轮迭代，沿初始方向组搜索方向：第一轮迭代，沿初始方向组 S Si i(1)(1)(i=1,2,(i=1,2,n),n)的的 n n 个方向和共轭方向个方向和共轭方向 S S(1)(1)，搜索，搜索 n+1 n+1 次得极值点次得极值点 x xn+1n+1(1)(1)；第二轮；第二轮迭代，沿方向组迭代，沿方向组 S Si i(2)(2)(i=1,2,(i=1,2,n,n；im)im)的的 n-1 n-1 个方向和共个方向和共轭方向轭方向 S S(1)(1)，构筑共轭方向，构筑共轭方向 S S(2)(2

36、)搜索搜索 n+1n+1次得极值点次得极值点 x xn+1n+1(2)(2)。其。其中，为保证搜索方向的线性无关，去除了中，为保证搜索方向的线性无关，去除了 S Sm m(2)(2)方向方向 。l 在第在第 k k 轮迭代中，为避免产生线性相关或近似线性相关，需轮迭代中，为避免产生线性相关或近似线性相关，需要去除前一轮中的某个方向要去除前一轮中的某个方向 S Sm m(k)(k)。去除的原则请自学。去除的原则请自学。3.3 坐标轮换法、共轭方向法和坐标轮换法、共轭方向法和Poweel法法共轭方向法的程序框图共轭方向法的程序框图9.9.共轭方向法的缺陷：共轭方向法的缺陷：共轭方向法的迭代过程可能

37、会产生不理想的情况，在以后某环的迭代共轭方向法的迭代过程可能会产生不理想的情况，在以后某环的迭代中可能出现基本方向组为线性相关向量系。以后的搜索将在维数下降后中可能出现基本方向组为线性相关向量系。以后的搜索将在维数下降后的设计空间中进行，无法收敛到的设计空间中进行，无法收敛到n维设计空间中目标函数的极小点。维设计空间中目标函数的极小点。以三维问题为例，设从初始点以三维问题为例，设从初始点 出发，沿着坐标轴方向出发，沿着坐标轴方向 ，进行第一环搜索，在各个方向获得极小点为：进行第一环搜索，在各个方向获得极小点为：)0(X123,e e e11)0()1(1eXX2211)0(22)0(1)1(2

38、eeXeXX332211)0(33)1(2)1(3eeeXeXX 由该环搜索的初始点由该环搜索的初始点 与终点与终点 产生的新生方向：产生的新生方向：)1(3X)0(X332211)0()1(3)1(eeeXXS3.3 坐标轮换法、共轭方向法和坐标轮换法、共轭方向法和Poweel法法9.9.共轭方向法的缺陷（续）：共轭方向法的缺陷（续）：如果其中第三维优化步长如果其中第三维优化步长 等于或非常接近等于或非常接近0，即表示沿着则坐标轴，即表示沿着则坐标轴方向方向 的搜索没有前进或前进很少，则共轭方向：的搜索没有前进或前进很少，则共轭方向：表明向量表明向量 与向量与向量 是线性相关的。是线性相关的

39、。3(1)S1(1)12210001000010S 3e12,e e 第第2 2环搜索的基本方向组环搜索的基本方向组 中，中，是是 与与 线性相关或接近线性相关，即向量线性相关或接近线性相关，即向量 在在 和和 组成的平面内。以后的组成的平面内。以后的搜索将在维数下降（不包含方向搜索将在维数下降（不包含方向 ）的平面中进行，无法收敛到）的平面中进行，无法收敛到 空间空间中目标函数中目标函数 的极小点的极小点 。(2)(2)(2)(1)12123,Se Se SS(2)3S(2)1S(2)2S(2)3S(2)1S(2)2S(2)3S3R()f X*X3.3 坐标轮换法、共轭方向法和坐标轮换法、共

40、轭方向法和Poweel法法0 x三三.Poweel.Poweel法法：1.1.基本步骤：基本步骤：1.给定初始点给定初始点 ，选取由，选取由n n个线性无关的向量个线性无关的向量 组成的初组成的初始方向组，置始方向组，置 。2.从从 出发，顺次沿出发，顺次沿 作一维搜索得作一维搜索得 。接着。接着以以 为起点，沿方向：为起点，沿方向：移动一个移动一个 的距离，得到：的距离，得到：00012,nSSS0k 0 x12,kkknSSS12,kkknxxxknx10kkknnSxx0kknxx100()2kkkkkknnnnxxxxxx 分别称为一轮迭代的始点、终点和反射点。它们所对应的分别称为一轮

41、迭代的始点、终点和反射点。它们所对应的函数值分别为：函数值分别为：01,kkknnxxx10231(),(),()kkknnFf xFf xFf x 同时计算各中间点处的函数值，并记为：同时计算各中间点处的函数值，并记为：()(0,1,2,)kiiff xin3.3 坐标轮换法、共轭方向法和坐标轮换法、共轭方向法和Poweel法法3.3 坐标轮换法、共轭方向法和坐标轮换法、共轭方向法和Poweel法法1.1.基本步骤（续）：基本步骤（续）：计算计算n个函数值之差：个函数值之差：3.为了构造第为了构造第k1环基本方向组，采用如下判别式：环基本方向组，采用如下判别式：按以下两种情况处理：按以下两种

42、情况处理：1(0,1,2,)iiiffin 其中最大者记作：其中最大者记作：11maxmimmi nff 31221231213(2)()()2mmFFFFFFFFF鲍威尔判别式鲍威尔判别式 a.上式中至少一个不等式成立，则第上式中至少一个不等式成立，则第k+1环的基本方向仍用老方向组环的基本方向仍用老方向组.,k+1的环初始点取的环初始点取:12,kkknSSS102310123kknkknxxFFxxFF1.1.基本步骤（续基本步骤（续2 2）：）：b.两式均不成立，两式均不成立，则淘汰函数值下降最大的方向，并用第则淘汰函数值下降最大的方向，并用第k环的新生环的新生方向补入方向补入k+1环

43、基本方向组的最后，即环基本方向组的最后，即k+1环的方向组为：环的方向组为：k+1环的初始点取环的初始点取 ，是第是第k环沿环沿 方向搜索的极小点。方向搜索的极小点。12111,kkkkkkmmnnSSSSSS10kkxxkx1knS3.3 坐标轮换法、共轭方向法和坐标轮换法、共轭方向法和Poweel法法鲍鲍威威尔尔法法的的流流程程图图一一.梯度法梯度法（最速下降法）（最速下降法）：1.1.基本思想：基本思想：2.2.负梯度方向为最速下降方向的证明：负梯度方向为最速下降方向的证明：目标函数负梯度向量方向代表最速目标函数负梯度向量方向代表最速下降方向，因此选择负梯度向量方向下降方向，因此选择负梯

44、度向量方向为搜索方向，期望很快找到最优点。为搜索方向，期望很快找到最优点。S由方向导数概念可得：由方向导数概念可得：21212211coscos,coscos)(xfxfxfxfSfKx设：设：12coscosS()()()()()()cos(),)KKTKKxff xSf xSf xSS ()cos(),)Kf xS取最小值取最小值1 1时，时，S为梯度的负方向。为梯度的负方向。3.4 3.4 梯度法和共轭梯度法梯度法和共轭梯度法4.4.迭代格式：迭代格式：3.3.搜索方向：搜索方向：a.a.任意给定一个初始步长，使其满足：任意给定一个初始步长，使其满足：根据一元函数的极值必要条件和多元复合

45、函数的求导公式，得：根据一元函数的极值必要条件和多元复合函数的求导公式，得：()(1)()()kkkkkfXXXfX(1)()()kkkkXXfX或或负梯度方向负梯度方向 或单位负梯度向量或单位负梯度向量()kfX()()()()()kkkf xSf x5.5.最佳步长最佳步长 的选取：的选取：k()()()()()kkkkf XSf Xb.b.沿负梯度方向作一维搜索，求最佳步长，对目标函数求极小，以得沿负梯度方向作一维搜索，求最佳步长，对目标函数求极小，以得到最佳步长：到最佳步长：)(min)(min)(kkxfXf1()()()()()0kkTkkTkkf xf xf xf xf x 即：

46、即：1()0kTkSS3.4 3.4 梯度法和共轭梯度法梯度法和共轭梯度法 最速下降法向极小点的逼近路径是最速下降法向极小点的逼近路径是锯齿形路线，越接近极小点，锯齿越锯齿形路线，越接近极小点，锯齿越细，前进速度越慢。细，前进速度越慢。这是因为，梯度是函数的局部性质，这是因为，梯度是函数的局部性质，从局部上看，在该点附近函数的下降从局部上看，在该点附近函数的下降最快，但从总体上看则走了许多弯路，最快，但从总体上看则走了许多弯路，因此函数值的下降并不快。因此函数值的下降并不快。5.5.最佳步长最佳步长 的选取（续）：的选取（续）：k 此式表明，相邻的两个迭代点的梯度是彼此正交的。也即在梯度的此式

47、表明，相邻的两个迭代点的梯度是彼此正交的。也即在梯度的迭代过程中，相邻的搜索方向相互垂直。迭代过程中，相邻的搜索方向相互垂直。6.6.搜索路径：搜索路径：3.4 3.4 梯度法和共轭梯度法梯度法和共轭梯度法（1）任选初始迭代点）任选初始迭代点x(0)，选收敛精度选收敛精度。（2）确定）确定x(k)点的梯度点的梯度(开始开始k=0)。（3）判断是否满足终止条件）判断是否满足终止条件 ，若满足输出最优解，结束，若满足输出最优解，结束计算。否则转下步。计算。否则转下步。（4）从）从x(k)点出发，沿点出发，沿 方向作一维搜索求最优步长方向作一维搜索求最优步长(k)。得下。得下一迭代点一迭代点 。令。

48、令k=k+1 返回步骤（返回步骤（2）。）。7.7.迭代终止条件：迭代终止条件：采用梯度准则：采用梯度准则：8.8.迭代步骤：迭代步骤：)(kXf()kf X()kf X(1)()()kkkkxxf x3.4 3.4 梯度法和共轭梯度法梯度法和共轭梯度法梯梯度度法法流流程程图图NY开始开始给定：给定：x(0)，k=0 x*=x(k)f*=f(x(k)结束结束x(k)=x(0)k=k+1)()()1()(kkkkkkxfxxxf和最佳搜索步长计算)(kxf3.4 3.4 梯度法和共轭梯度法梯度法和共轭梯度法9.9.方法评价：方法评价：l 迭代过程简单，对初始点的选迭代过程简单，对初始点的选择，要

49、求不高。择，要求不高。l 梯度方向目标函数值下降迅速梯度方向目标函数值下降迅速只是个局部性质，从整体来看，只是个局部性质，从整体来看，不一定是收敛最快的方向。不一定是收敛最快的方向。l 以二维二次函数为例，相邻两以二维二次函数为例，相邻两次的搜索方向是正交的，所以搜次的搜索方向是正交的，所以搜索路径是曲折的锯齿形的；对于索路径是曲折的锯齿形的；对于高维的非线性函数，接近极值点高维的非线性函数，接近极值点处，容易陷入稳定的锯齿形搜索处，容易陷入稳定的锯齿形搜索路径。路径。例例4-1 二维无约束目标函数二维无约束目标函数 试试用梯度法求其极小值，初始点用梯度法求其极小值，初始点 ，精度，精度221

50、21212()10460f Xxxx xxx(0)0,0TX410 解：解：1 1）计算目标函数在初始点的梯度、梯度的模和单位负梯度方向）计算目标函数在初始点的梯度、梯度的模和单位负梯度方向41042102)0()0(12212)0(1)0()0(XXxxxxxXfxXfXf7703.104102222)0(21)0()0(fxXfxXfXf3714.09285.07703.104,10)0()0()0(TXfXfS 2 2）计算最佳搜索步长）计算最佳搜索步长)0()0()0()0()0()0()1(3714.09285.03714.09285.000SXX607706.10)(6552.0)