现代设计方法优化设计无约束优化PPT学习教案

1、会计学1本章主要内容 优化设计概述 优化设计的数学基础 一维探索优化方法 无约束优化方法 约束问题优化方法 优化设计若干问题第1页/共69页 优化设计概述 优化设计的数学基础 一维探索优化方法 无约束优化方法 约束问题优化方法 优化设计若干问题 坐标轮换法 梯度法 牛顿法 变尺度法 共轭方向法 共轭梯度法 鲍威尔法无约束优化方法第2页/共69页(1) 算法思想1.将多维问题，降为多个 一维问题；2.在一维上可使用黄金分 割法等直接采样优化方 法；3.轮换地以每一个坐标轴 作为一维搜索方向的优 化搜索方法。x1x2X 0X 1X 2X 3f(X)=c第3页/共69页开始给定 x、d 的初始值计算

2、a*使f(x+ad)极小x x + a*d满足收敛条件？形成新的d结束第4页/共69页(2) 算法1. 初始化， 0，M，n, k=1, x=x(0).2. 对于i=1,2,n， 进行 2.1 Si=ei; 2.2 i=min f(x+Si) 2.3 x= x+iSi, f=f(x).3. 如果|iSi|M, 转步4; 否则，k=k+1,转步2。4. 输出x, f. 结束。第5页/共69页(3) 举例)0 , 0(22),( min)0(2221212121Xxxxxxxxxf第6页/共69页(3) 举例)0 , 0(22),( min)0(2221212121Xxxxxxxxxf第7页/共6

3、9页)0 , 0(22),( min)0(2221212121Xxxxxxxxxf013S(3) 举例104S以上举例是手算实现该算法，用计算机实现时，需用进退法和黄金分割法实现一维搜索。第8页/共69页(4) 算法分析1.对于维数较高的优化问题，搜索时间过长，一般当n10时， 则不应采用此方法。2. 算法效率与f(x)形态有关。收敛速度最快收敛速度慢搜索无效第9页/共69页基本思想 梯度方向是函数值增加最快的方向，而负梯度方向是函数下降最快的方向，所以梯度法以负梯度方向为搜索方向，每次迭代都沿着负梯度方向一维搜索，直到满足精度要求为止。因此，梯度法又称为最速下降法。梯度法f(x0)df(x)

4、=2f(x)=1x0f(x)=0第10页/共69页 设在某次迭代中已取得迭代点X(k)，从该点出发，取负梯度方向为搜索方向S(k)，即： )()()()()()()()(kkkkkXfXfSXfS 或或niiknkxfXfxfxfxfXf12)(T21)()( , )(其中，第11页/共69页这样，第k+1次迭代计算所得的新点为：)()()()()()()1(kkkkkXfXfXX)()()()()1(kkkkXfXX 或或上式即为 梯度法迭代公式。第12页/共69页 因为X(k)已知，故 和 不难求出，只要知道步长 后，就可以得到新点X(k+1)。由于每次迭代能保证 ，如此反复计算，最后总能

5、达到最优点X*。 为了使目标函数值在搜索方向S(k)上获得最多的下降，每次迭代都进行一维搜索求最优步长，即求 )()(kXf)()(kXf)()()()1(kkXfXf)()(min)()()()()(kkkkkSXfSXf第13页/共69页迭代步骤1）任选初始点X(0)，计算精度 ，令k=0 ；2）计算 和 ；3）收敛判断， A.若 ，则X(k)为近似最优点，停止迭代，输出最优解： ， ； B.若 ，则转下一步继续迭代；4）令)()(kXf)()(kXf?)()(kXf)()(kXf)(*kXX )()()(*kXfXf)()(kXf)()()()()(kkkXfXfS 第14页/共69页5

6、）确定最优步长因子 ，使6）计算 ；7）令k=k+1，转2）。)(k)(min)()()()()()(kkkkkSXfSXf)()()()1(kkkkSXX第15页/共69页例1： 用梯度法求函数 的极小值，初始点 ，计算精度 。 2221) 1() 1()(xxXfTX0 , 0)0(01. 05 . 0) 12(2)()(2222)(22)(2222)(*2)0()0()0()0()0(21XfSXXXfSXfxxXf第16页/共69页解：（1） 如果 转（2），否则转（5）。 970. 0243. 0)()(492.16)(164)(82)()0()0()0()0()0(21XfXfSX

7、fXfxxXf1)0()(Xf例2. 用一阶梯度法求目标函数 f(X)=x12+4x22 在初始点 X(0)=2 2T，迭代精度 =10-2 下的最优解。第17页/共69页（2）492.16645. 7)(970. 0243. 022)0()0()1()0()0()0()0()1(dXdfSXX第18页/共69页（3） ，并转（1）。（4）第7次迭代后， 成立，停止迭代。（5）取 时， f(X*)=2.59610-60 092. 0476. 1157. 20)()1()0()0()1(XdXdf,000096. 00016. 0)7(TXTXX000096. 00016. 0*)7(01. 0

8、0032. 0)(1)7(Xf比较上面两个例题，能得出什么样的结论？第19页/共69页梯度法的特点：负梯度方向只是函数值在点X(k)的邻域内下降最快的方向，离开该邻域以后函数值不一定下降最快。因此，采用负梯度方向，从局部看函数值下降快，从全局看却要走很多弯路。因此，梯度法的收敛速度较慢。梯度法的迭代过程，每相邻两步的搜索方向是垂直的，也就是说梯度法的迭代路线是呈锯齿形前进的。第20页/共69页梯度法迭代过程中，当迭代点离理论极小点较远时，一次迭代的函数值下降量大。迭代点离极小点越近，函数值下降的速度就越慢。因此，梯度法常与其它优化方法结合使用。即第一步采用梯度法，后面采用其它的方法确定搜索方向

9、。梯度法的收敛速度与目标函数的性质有关。如果目标函数的等值线（面）为同心圆（球），则无论从哪里出发，只需要一次搜索就能达到极小点。第21页/共69页第22页/共69页1.基本牛顿法设目标函数是连续二阶可微的，将函数在X(k)点按泰勒级数展开后，取到二次项将上式展开，得)()(21)()()()()(2)()()()(kkkkkTkXXXfXXXXXfXfXf 牛顿法第23页/共69页)(21)()(21)()()()()(22)()(2)(2)(2)()()()(kkkkkkTkkTkXfXXfXXXXfXfXXXfXfXf 对X求导，设X(k+1)是极小点，并令一阶导数为0，得0)()()(

10、)(1)(2)(kkkkTXXXfXfXXf)()()()()()(21)(2kkkkkXfXXfXXf 即即第24页/共69页)()()()()(1)(2)()(1)(2)(1)1(kkkkkkkkXfXfSXfXfXXX ,令令即即可可得得到到解解出出)()(1kkkSXX 则则上式即为基本牛顿法的迭代公式，其中S(k)称为牛顿方向。例. 用基本牛顿法求下列函数的极小值:TXxxXf)2,2(4)()0(2221第25页/共69页基本牛顿法的特点：对于二次函数而言，取到二次项的泰勒展开式就是目标函数本身。如果二阶导数矩阵正定，那么按基本牛顿法求出的X(1)就是目标函数的精确极小点。因此，对

11、正定二次函数而言，牛顿法只需一次迭代就可以达到精确极小点。基本牛顿法迭代时步长总是为1，对非二次函数、非正定函数而言，一次迭代并不能达到极小点，有时还可能失效（即总是不能收敛）。第26页/共69页2.阻尼牛顿法 基本牛顿法对非正定函数失效是因为沿牛顿方向搜索时，步长总是为1，这并不能保证找到的下一个迭代点是该方向上的极小点。为此，增加步长因子和一维搜索过程。此时的牛顿法称为阻尼牛顿法。阻尼牛顿法比基本牛顿法多一个一维搜索过程第27页/共69页阻尼牛顿法迭代步骤：1）选取初始点X(0)，计算精度 ，令k=0 ；2）计算 ；3）4）5）按一维搜索结果，计算1)(2)(2)()()()(kkkXfX

12、fXf 、；令令)()()(1)(2)(kkkXfXfS )(min)()()()()()()(kkkkkkSXfSXf ，使，使一维搜索，求一维搜索，求；)()()(1kkkkSXX 第28页/共69页6）收敛判断， A.若 ，则X(k+1)为近似最优点，停止迭代，输出最优解 和 ； B.若 ，则令k=k+1，转2）继续迭代.?)()(kXf)()(kXf)1(*kXX)()()1(*kXfXf)()(kXf例. 用阻尼牛顿法求下列函数的极小值:TXxxxxxXf) 11 (923)()0(122213231，第29页/共69页 数学分析表明，牛顿法具有很好的局部收敛性质，对二次函数来说，仅

13、一步就达到优化点，但对一般函数来说，在一定条件下，当初始点的选取充分接近目标函数的极小点时，有很快的收敛速度，但若初始点选取离极小点比较远，就难保证收敛；另外，牛顿法必须求一阶导数、二阶导数矩阵及其逆阵，这对复杂的目标函数来说，是比较较困难的。 第30页/共69页 梯度法构造简单，只用到一阶偏导数，计算量小，迭代初期收敛速度快，但当迭代点到最优点附近时收敛速度极慢； 变尺度法是在梯度法和牛顿法的基础上发展起来的一种优化方法。用得较多的是 DFP（Davidon-Fletcher-Powell)变尺度法。1.基本思想变尺度法第31页/共69页 牛顿法收敛很快，对二次函数只需迭代一次就能达到最优点

14、，对非二次函数也能较快达到最优点，但牛顿法计算量和存储量偏大。而且某些函数可能根本无法计算二阶偏导数矩阵及其逆阵。 为了综合梯度法和牛顿法的优点，扬长避短，产生了变尺度法。第32页/共69页变尺度法的搜索方向为变尺度法的基本迭代公式为)()()()()()1(kkkkkXfAXX)()()()(kkkXfAS牛顿方向。称为拟个矩阵序列。搜索方向一置的变化而变化，形成度矩阵，它随迭代点位阶方阵，称为变尺是一个需要构造的式中，)()()()()(kkkkXfASnA，得到牛顿法。，得到牛顿法。令令，得到梯度法，得到梯度法令令1)(2)()()(kkkXfAIA第33页/共69页2.变尺度矩阵的构建

15、 变尺度矩阵A(k)的构建是从A(0)=I开始，通过迭代公式 A(k+1) = A(k) + E(k)得到的。E(k)称为修正矩阵，通过它的一步步修正，使A(k)逐步逼近 ，即使变尺度法的迭代方向逐步逼近牛顿方向。 修正矩阵取不同的形式，就形成了不同的变尺度法。1)(2)(kXf第34页/共69页DFP变尺度法修正矩阵E(k)的构造公式为)()()()()()()()()()()()()(kkTkkTkkkkTkTkkkkgAgAggAgSSSE)()()()()1()1()()1()(kkkkkkkXfgXfgggg 式中，式中，第35页/共69页3.变尺度法的迭代步骤结束；否则转下一步；结

16、束；否则转下一步；为极小点，迭代为极小点，迭代，则，则收敛判断：若收敛判断：若）；计算计算）梯度法）梯度法）（第一步迭代实际就是（第一步迭代实际就是；一维搜索一维搜索）；，计算计算）阶单位方阵）；阶单位方阵）；为为，令令）；，计算精度，计算精度取初始点取初始点） )1()1()1()1()()()()1()0()0()0()0()0()0(6)(54)(3(021kkkkkkkkXgXfgSXXIgSXfgnIIAkX第36页/共69页），转步骤，转步骤）令）令新的搜索方向新的搜索方向计算变尺度矩阵，构造计算变尺度矩阵，构造）4187)1()1()1()()()()()()()()()()()

17、()()()()()1()1(kkgASgAgAggAgSSSAEAASkkkkkTkkTkkkkTkTkkkkkkkk 例. 用变尺度法求下列函数的极小值。01. 0)0 , 0(60410)()0(21212221，TXxxxxxxXf第37页/共69页用变尺度法求函数的极小值。 =0.0160410)(21212221xxxxxxXf解：(1)取初始点：00)0(X1001A)0(I41042102)()0(122121)0(XXxxxxxfxfXf4104101001)0()0(XfIS第38页/共69页(2)一维搜索(3)052. 3631. 74107631. 000)0()0()

18、0()1(SXX526. 5211. 242102)1(122121)1()1(XXxxxxxfxfXfg526. 1211.12410526. 5211. 2)0()1()0(ggg如何求 ？)1(A第39页/共69页)()()()()()()()()()()()()()()()1(AAAA AAkkTkkTkkkkTkTkkkkkkkgggggSSSE利用：0897. 1386. 0386. 0673. 0A526. 1211.121001526. 1211.121001526. 1,211.12526. 1211.121001526. 1211.124 ,104 ,104107631.

19、01001AAAAAA)1()0()0()0()0()0()0()0()0()0()0()0()0()0()0()0()1(TTTTTTgggggSSSE第40页/共69页(4)搜索方向169. 5646. 0526. 5211. 20897. 1386. 0386. 0673. 0A)1()1()1(XfS；方法同前。最优步长因子：5701. 0) 1 (9999. 59999. 7169. 5646. 05701. 0052. 3631. 7)1()1()1()2(SXX一维搜索得：与牛顿法比较其结果非常接近，从本例中可以看出用近似矩阵代替二阶导数及逆阵是可行的。 第41页/共69页如何判

20、断搜索结束？0001. 00001. 042102)2(122121)2()2(XXxxxxxfxfXfg因为：01. 0 )2(g即：为极小点。因此： )2(X)1 ()1 ()1 ()0(A、：求解解决此类问题的关键是S第42页/共69页1.椭圆的共轭方向共轭方向法SiS椭圆的一簇平行弦的中点联系通过圆心。并称中点连线方向S与平行弦方向Si为相互共轭方向。第43页/共69页2.共轭方向的代数定义定义: 设 A 为nn 阶实对称正定矩阵，而S1、S2为在n维欧氏空间En中的两个非零向量，如果满足式 S1TAS2=0则称向量S1与S2关于实对称正定矩阵A是共轭的。第44页/共69页共轭是正交关

21、系的推广： 当A=I 时， 共轭就是正交。由 A 对称正定,得：所以, 即共轭是仿射变换Q下的正交.0)()()()(212121212/12/12/12/1SSQSQSQSQSASSQQUDUDUDDUDUUATTTTTTTTT关于二次函数Hesse矩阵A共轭的几何意义与正交概念的关系变换前变换后第45页/共69页几何定义与代数定义是等价的。 设X(1): min f(X1+aSi)X(2): min f(X2+aSi)X(1)= X1+a1SiX(2)= X2+a2Si则 Si与S=X(2)-X(1)共轭.X1X2SiS0)(0)()()( 0)()()( )()1()2()2(222)1

22、(11121ASSXXASbAXSSaXfSabAXSSaXfSabAXfAXXXbCXfTiTiTiiTiTiiTiTT第46页/共69页性质：对于二次函数, 沿n个共轭方向依次进行一维搜索,在第n次搜索时达到整体最优解。n为X维数.X1X2SiS第47页/共69页第一轮: S1(1), S2(1) 不一定 共轭, 产生S(1).第二轮: 取S1(2)= S2(1) S2(2) =S(1), 产生S(2).第三轮: 取S1(3)= S(1) S2(3) =S(2), 所以,由定义知, 对于二次函数, S(1), S(2)共轭.第一轮第二轮算法：第48页/共69页算法分析1.对于二次函数,经过

23、n轮(每轮n次一维搜索)循环后, 第n轮中的n个搜索方向相互共轭. 所以,第n轮能达到最优解.2.对于非二次函数,经过n轮循环后, 第n轮中的n个搜索方向对于f(x)的二次局部近似函数的Hesse矩阵只是近似相互共轭,虽然有较高的逼近,但不一定到达极值点.3.算法可能出现n个方向线性相关.例如,当一维搜索中a=0时,X1(2)=X0(2)时S(1)与S(2)线性相关.此时,不能得到最优解.4.对于非二次函数,经过n轮循环后,可以重新选择n个初始搜索方向,以减小前面搜索方向线性相关或退化的影响.第49页/共69页算法思想结合共轭方向法和梯度法的优点,取相互共轭的搜索方向,同时取为与当前点梯度方向

24、相关方向.一般共轭梯度法:1.初始化. g0= f(x0), 选择S0使 S0Tg00.2.如果|gk|eps, 结束.3.一维搜索 xk+1=xk+ak Sk :min f(xk+ak Sk).4.选择Sk+1,使Sk+1THSj=0, j=0,1,k. H=2f(xk)5.k=k+1,转步2.共轭梯度法第50页/共69页梯度法与共轭梯度法第51页/共69页Fletcher-Reeves 共轭梯度法选择 ：x2-f(xk+1)Skxkxk+1kSkSk1x*x1Sk+1= -gk+1+kSk第52页/共69页)()()()1()()(21)(kkkkTTSXXBAXXfXgCXBAXXXfg

25、k+1S(k)X(k)X(k+1)由一维搜索性质，得0)(1kTkSg推导Fletcher-Reeves 共轭方向：第53页/共69页)()(1)()()()1(1)()1(1)(kkkkkkkkkkkkkkASggASXXAggBAXgBAXg0)(1kTkSg0 So0001)()()()1(1)()()()()(1)()()()()()()()(1kTkkTkkkTkkkkTkkkTkkTkkkTkkTkkTkkkTkkTkkkTkkTkggASSggSSASggAgSggggASSggASSSgSg0)1(kTkSgkTkkTkkkTkkTkkkkkggSgggSgSgS)1(1)()1(1)(第54页/共69页00)()(0)()()()(1111)(11)() 1()() 1(1)()()() 1(1)() 1(1kTkkkTkkkTkkTkkkkTkkkTkkkTkkkkkkkkkkkkSgSgggggSgggASSSggASXXAggBAXgBAXgkTkkTkkkTkkTkkkkkggSgggSgS