机械优化设计无约束方法演示文稿

1、机械优化设计无约束方法演示文稿（优选）机械优化设计无约束方法第1章所列举的机械优化设计问题，都是在一定的限制条件 下追求某一指标为最小，它们都属于约束优化问题。工程问题大 都如此。为什么要研究无约束优化问题?(1) 有些实际问题，其数学模型本身就是一个无约束优化问题。(2) 通过熟悉它的解法可以为研究约束优化问题打下良好的基础。(3) 约束优化问题的求解可以通过一系列无约束优化方法来达到。 所以无约束优化问题的解法是优化设计方法的基本组成部分，也 是优化方法的基础。(4) 对于多维无约束问题来说，古典极值理论中令一阶导数为零，但要求二阶可微，且要判断海赛矩阵为正定才能求得极小点，这种方法有理论

2、意义，但在实际应用中受到限制。和一维问题一样，若多元函数F(X)不可微，亦无法求解。但 古典极值理论是无约束优化方法发展的基础。兰=0dx竺=0dx2、知°§4T概述(4-1)minF(X)XgRh若F(X)存在一阶导数，则可按照如前所述的极值条件来确定其极值点可能的位置(称为驻点)。即求方程VF = O的解。也就是求X,使其满足1. n个未知量n个方程的方程组，一般是非线性的2. 求解该方程组与求无约束极值一样困难， 甚至更困难。若用数值计算方法求解问题4T,按照寻优思路不同，可分为: 匾索类基本思福是从某一石定的初始点用开始，沿给定的捜索方 向9进行捜索，确定步长日0使

3、函数值沿9下降最大（或达到给定的 值）O其迭代格式如下：X“1 = xk +%s* 伙=0 丄 2,）入爬山类方法。搜索方向的构成问题是无约 束优化方法的关键收敛?结束形成新SY k=k+l爬山类方法的寻优思想直接法（不用导数的信息）单形替换法2 间接法（用到导数的信息）共觇梯度法）梯度方向梯度方向是目标函数上升最快的方 向，负梯度方向则是最速下降方向；二）基本思想|SW=_X7F（X）二g叫2 ）迭代公 Xk+） = X（k）-a（k）/F（X伙） 式三）终止判别条件*可取最优步长或下降步长:/111%1fV为了使目标函数值沿搜索方向-冯(*)能够获得最大的下 降值，其步长因子也应取一维搜索

4、的最佳步长。即有/(兀小)=fxk -akVf(xk) = min fxk - aVf(xk)a=min(a)根据一元函数极值的必要条件和多元复合函数求导公式，得0G)二-VfxA -akVf(xk)7 Vf(x) = 0Vf(xk+l)fVf(xk) = O(sk+1)Tsk =0在最速下降法中，相邻两个迭代点上的函数梯度相互垂直。而搜索方向就是负梯度方向，因此相邻两个搜 索方向互相垂直。这就是说在迭代点向函数极小点靠近的过程，走的是曲折的路线。形成“之”字形的锯齿现象,而且越接近极小点锯齿越细O最速下降法的搜索路径梯度法的迭代过程给定X。, £K=K+1从X出发，沿-g捜索得X、

5、=X 2宀2Y特点(1)初始点可任选，每次迭代计算量小，存储量少， 程序简短。即使从一个不好的初始点出发，开始的几步 迭代，目标函数值下降很快，然后慢慢逼近局部极小点。(2)任意相邻两点的搜索方向是正交的，它的迭代路 径为绕道逼近极小点。当迭代点接近极小点时，步长变 得很小，越走越慢。求F (X )=卅+25卅的极小值解：取初始点X0=2,21T,则初始点处函数值及梯度分别为50x2VF(X°) =F(X °) = 104丁 4 _2 4%X】=X°订 F(X°) =Vz、/_°o21002 loo。04100F(Xl) = nnF(X0(X

6、°)= min( 2-4q)2 +25(2 -100。门=min 0(d)a/（a。）= 一 8（2 4兔）一 5000 （2 100 兔）=0兔=0.020030720000X12 4。02 100。01.919877-0.3071785X102= 36861640000,F（X*） = 000卩（归2）" +必0(严)= 104v(r°)=2订。420r1=ro«ov(r°)=_410u202 4a；10 20qy/(Y) = min一 aV 0(Y°) = min (o')(a') (2 4q')2 +

7、(10 20q')2'(4 )= 8(2 4af) -40(10- 20af) = 0良丫70Xk+ -x < (1 -X XM2M是/Xx)的海赛矩阵最大特征值的上界 加是/(工)的海赛矩阵最小特征值的下界迭代过程简单，对初始点的选择，要 求不高。梯度方向目标函数值下降迅速只是个 局部性质，从整体来看.不一定是收敛 最快的方向。以二维二次函数为例，相邻两次的搜 索方向是正交的，所以捜索路径是曲折 的锯齿形的；对于高维的非线性函数， 接近极值点处，容易陷入稳定的锯齿形 搜索路径。梯度法的收敛速度与目标函数的性质 密切相关。对于等值线（面）为同心（球）的目标函数，一次搜索即

8、可达到 极小点。*量速下降法只利用了函数一阶导数的信息，在极值点附近收敛较慢，从函数等值 线特性分析可知，在极值点附近，函数具有二次函数的特性，如果利用二次导数的 信息，在极值点附近进行寻优，应该具有较快的收敛速度？一原始牛顿法用目标函数的近似二次函数的极小点来近似原函数的极小点；J原函数：F（X）（近似二次函数（X） = F（X）+黒了2）+2空守乩必1）迭代方向：S（J-H打（牛顿方向）2）步长因子：Q三1对于二次函数，f（X）的泰勒展开式不是近似的，而是精确的。海赛矩阵是一个常矩阵，其中各元素为常数。因此，无论从任何点出发，只需一步就可找到极小点。二次收敛若某一迭代方法能使二次函数在有限

9、次迭代内达到极小点。牛 顿方法是二次收敛的求逆矩阵？设4是门阶方阵，如果存在门阶方阵B, AB=BA=E 则称A是可逆矩阵，B是的逆矩阵。E是门阶单位矩阵逆矩阵的求法：一 (12、 一求矩阵的逆矩阵I。1丿AB = BA =q 2、(1 0、6 5丿2丫勺1人広W i丿求F (X )=卅+25卅的极小值解：取初始点X°=2, 2则初始点处梯度，海赛矩阵及其逆阵分别为V2F(X°)050V'FCX0)-1 =X1 = X0 歹尸色纬卩=1/2001/501/20F"""041/50JL100O'02xr-4 "50x2x

10、°_100_VF(X°)二）阻尼牛顿法从牛顿法迭代公式的推演中可以看到，迭代点的位置是按照 极值条件确定的，其中并未含有沿下降方向捜寻的概念。因 此对于非二次函数，如果采用上述牛顿迭代公式，有时会使 函数值上升。基本牛顿法的步长因子恒为仁有时会导致迭代 发散而失效。仍取牛顿方向，但改用最优步长因子，在牛顿方向上进行一维搜索，避免了迭代后函数值上升的现象:X（Z =x（k）X）伙） 在纵正定时可保证收敛性。*具有二次收敛性，但用到二阶导数矩阵求逆给定x（）, e方法特点(1) 初始点应选在X*附近，有一定难度；(2) 尽管每次迭代都不会使函数值上升，但不能保证每次下降(3)

11、若迭代点的海赛矩阵为奇异，则无法求逆矩阵，不能构造牛顿法方向;(4) 不仅要计算梯度，还要求海赛矩阵及其逆矩阵，计算量和 存储量大。此外，对于二阶不可微的RX)也不适用。虽然阻尼牛顿法有上述缺点，但在特定条件下它具有收敛 最快的优点，并为其他的算法提供了思路和理论依据。梯度法与牛顿法：一般迭代式：xk+1=xk+aksk 伙=0,1,2,)梯度法：xk+l =xk -akVf(xk)伙= 0,1,2,)牛顿法：厂= -v2/(x)rvr(x)伙=o,i,2,.-)阻尼牛顿法：xk+i=xk-aky2f(xk)rf(xk) 伙= 0,1,2,)xk+i=xk-akAkVf(xk)4-3变尺度法D

12、FP变尺度法首先有戴维顿（Davidon）与1959年提出，又于1963年由弗莱彻（Fletcher）和鲍维尔加以发展和完善，成为现代公认的较好的算法之一。DFP法是基于牛顿法的思想又作了重要改进。这种算法仅 用到梯度，不必计算海赛阵及其逆矩阵，但又能使搜索方向逐 渐逼近牛顿方向，具有较快的收敛速度。变量的尺度变换是放大或缩小各个坐标。通过尺度变换可以把函数的偏心程度降低到最低限度。尺度变换技巧能显ILL'著地改进几乎所有极小化方法的收敛性质O例如在用最速下降法求门必）=Z12 +25/极小值时，需要进行10次迭代才能达到极小点 = 0,0f如作变换J2=5X2把兀2的尺度放大5倍，则

13、目标函数等值线由一簇椭圆变成 一簇同心圆。消除了函数的偏心，用最速下降法只需一次迭代即可求 得极小点。梯度法构造简单，只用到一阶偏导数，计算量小，初始 点可任选，且开始几次迭代，目标函数值下降很快；其主要 缺点是迭代点接近X*时，即使对二次正定函数收敛也非常慢。牛顿法收敛很快，对于二次函数只需迭代一次便达到最 优点，对非二次函数也能较快迭代到最优点，但要计算二阶 偏导数矩阵及其逆阵，对维数较高的优化问题，其计算工作 和存储量都太大。能不能将两种算法的优点综合起来,扬长避短?xk+1 =xk-akAkVf（xk）Ak是需要构造n X的一个对称方阵,如A厶则得到梯度法； 如川二w予（卅）则得到阻尼

14、牛顿法；当矩阵牡不断地迭代而能很好地逼近/（*）时，就可以不再需要计算二阶导数。对于二次函数：y（x） = xTGx +bx +c进行尺度变换X妙在新的坐标系中，函数/仪）的二次项变为:xtQtGQx如G是正定，贝|总存在矩阵Q,使得:Qtgq = i用矩阵01右乘等式两边,QrG=Q用矩阵0左乘等式两边，得： QQ G = I 所以 QQT=Gl上式说明：二次函数矩阵G的逆阵，可以通过尺度变换 矩阵0来求得。牛顿迭代公式:xk+i=xk-akV2f(xk)rW(xk) 伙=0,1,2,.-)W = h -akQQTVf(xk) 伙= 0,1,2,)记：QQTA称为变尺度矩阵搜索方向：严二&a

15、mp;巧(址)仗= 0,1,2,)迭代公式：x1 =卅-akAkVf(xk) 伙= 0,1,2,)在例4一2中/(x) =x； + 25x；1厂f(x) = x +25xf =- x x22_2 O' G 0 501152如取Q=忑000QGQ =°2i l°5a/2050020"Lo5°_"1疋01 0"01_0 1.52.从而求得G-1 - QQt =r 1ni 0r 1i75 o丄02口0 *5 72 J0 +L5尽-°五这与在例4-2中所得结果一致，而且只需通过一次迭代即可求得极小点 x* = 00丁和极小值

16、f (x*) =0比较牛顿法迭代公式护"=Z - /QQTyf (“)和梯度法迭代公式护“二疋-攻Y/X护)可以看出，差别在于牛顿法中多了 qqt部分。QQt实际上是在工空间内测量距离大小的一种度量，称作尺度矩阵H(H =如如在未进行尺度变换前，向量兀长度的概念是I X II =（办）才变换后向量K对于H尺度下的长度h II h =（砂円血示=txT（QQT）x）i = （xtHx）2这样的长度定义，在确定“长度”这个纯量大小时，使得某些方向起的作用比较兀， 晃些方向起的作用比较小。为使这种尺度有用，必须对一切非零向蚤的X均有X阪0,即要求矩阵H正定。既然牛顿法迭代公式可用尺度变换矩

17、阵HQQt表示出来，即?+l =它和梯度法迭代公式只差一个尺度矩阵Ho牛顿法就可看成是经过尺度变换后的梯度法。 经过尺度变换，使函数偏心率减小到零，函数的等 值面变为球面（或超球面），使设计空间中任意点处函 数的梯度都通过极小点，用最速下降法只需一次迭 代就可达到极小点。这就是对变换前的二次函数，在使用牛顿方法时， 由于其牛顿方向直接指向极小点，因此只需一次迭 代就能找到极小点。从初始矩阵4。=/(单位矩阵)开始，通过对公式Ak+i=Ak+AAk中修正矩阵M的不断修正，在迭代中逐步逼近于因此，一旦达到最优点附近，就可望达到牛顿法 的收敛速度。1) DFP法(DavidonFIetcherPow

18、ell)加 _ 2心丫 AkAgkgkYAk一心丁观“逸丁人仏g"2) BFGS算法(Broyden-Fletcher-Gold frob-Shanno )汕5+叩严-AAAg'Axf -心愼丁 才DFP算法由于舍入误差和一维搜索不精确，有 可能导致构造矩阵的正定性遭到破坏，以至算法 不稳定。BFGS算法对于维数较高问题具有更好的 稳定性。例43：用DFP算法求下列问题的极值:/(xpx2)二兀2 +2xf _4兀-2xx2解：°咖*碱麟构造第一次2兀2兀4-4'°=vr(x°)=4耳一 2兀X02取初始变尺度矩阵为单位矩阵4。=人则第一

19、次搜寻方向为1 0 42沿d°方向进行一维搜索，得X1 = X° + (7 6?° =丁+ a.'41 + 4&00丄02_l-2a0_兔为一维搜索最佳步长，应满足/(x1) = min/(x° +加°) = min(40a2 -20a-3) aa得：r ? ii _厶aQ = 0.25 ,兀=0 52)再按DFP法构造点0处的搜寻方向孔 需计算a1 _2旺2兀一 4-1s -4x2 一 2xlx1.2._143224Ax° =兀】_兀0 =2110.51-0.5代入校正公式=Ax°Ax° r A&

20、#176;Ag0Ag°rA0心丁倔。 Ag°rA0Ag00_1-1-051-9-12>+ _015-0.50.2525-121621251950195041Too第二次搜寻方向为2d=-Ag= 6再沿加进行一维搜索，得5X2 = X1e为一维搜索最佳步长，应满足Q1 1/(x2) = min/(x1 +ad) = min(-a2 _4a_)&Q 52得0冷,x23）判断兀2是否为极值点梯度:W2) =2兀2兀2 4x2海赛矩阵:V2f(x2) =2-2-24梯度为零向量，海赛矩阵正定。可见点满足极值充要条 件，因此为极小点。=4f(x*) = -8每次迭代需要

21、计算二阶导数矩阵,矩阵求逆计算:大，存储量大收敛速度比较慢针对牛顿法，提出了变尺度法针对最速下降法，提出了只用梯度信息，但收 敛速度更快的共轨梯度法每次以一个变量坐标轴作为搜索方向'将n维的优化问题轮 流地转化为一系列一维捜索问题。 例，第k轮迭代的第i次搜索， 是固定除Xj外的n-1个变量， 沿Xj变坐标轴作一维捜索， 求得极值点Xj®n次搜索后 获得极值点序列x/k), X2%), Xn<k若未收敛，则开始第k+1 次迭代，直至收敛到最优点X*O-）捜索方向第k轮第i次搜索的方向：弓为第i个设计变量的坐标轴方向；篇丘轮第,次搜索的步长 少性产）；第r轮第歆搜索的迭代

22、公式才）=s+加約/）,心1,2,.丿；第行仑第i次搜索的收敛条件：乜 3依次沿个n个正交坐标轴玄=1 o . of,2=0 1 . 0r = 0 0 . If二）迭代步骤1）几何描述（以二维问题为例）2）坐标轮换法流程川）匕b)方法简单，容易实现。当维数增加时，效率明显下降。 收敛慢，以振荡方式逼近最优点。受目标函数的性态影响很大。如a）所示，二次就收敛到极值点;如b)所示.多次迭代后逼近极值点;如c）所示，目标函数等值线出现山脊（或称陡谷儿 若捜索到A点，再沿两个坐标 轴，以±t°步长测试，目标函数值均上升，计 算机判断A点为最优点。事实上发生错误。1.共轨方向：设Gn

23、Xn阶实对称正定矩阵，如果有两个"维向量別和/ 满足(dQ)TGdl = 0,则称向量別与加关于矩阵G共辘。当G为单位矩阵时，(d°)Tdl=O假设目标函数/&)在极值点附近的二次近似函数为y(x) = x'Gx +bTx +c对二维情况任选取初始点疋沿某个下降方向/作一维搜索，得0x1 =x° +aod°= LT4因为 兔是沿別方向搜索的最佳步长，即在点0处函数f(X)沿方向別的方向导数为零。考虑到点0处方向导数与梯度之间的关系，故有 亜=rvf(x1)rj°=O如果按最速下降法，选择负梯度方向"/(*)为搜索方向,

24、 则将发生锯齿现象。取下一次的迭代搜索方向/直指极小点疋。如°1如果能够选定这样的搜索方向，那么对于二元二次函数只需顺次进行d。、d1两次直线搜索就可以求到极小点X* ,即有x* =Xl +如1那么这样的加方向应该满足什么条件呢？ 对于前述的二次函数：f(x) = xTGx+bTx+c 有 Vf(x)=Gxl+b当X1 兀*时， e H0xW(x)极小点，应满足极值必要条件，故有Vf(x)=Gx +b = 0Vf(x=G(x +ad)+b=Vf(x) + aGd =0将等式两边同时左乘得:宦)3=o(d°)TGdl = 0(八“)/ = 0就是使/直指极小点疋,刃所必须满足

25、的条件。 两个向量/和/称为G的共轨向量，或称/和/ 对G是共轨方向。2. 共轨方向的性质性质1若非零向量系別",2,.0识是对G共辘，则这 加个向量是线性无关的。性质2在兀维空间中互相共轨的非零向量的个数不超过性质3从任意初始点出发，顺次沿个G的共轨方向 別,加，血,进行一维搜索，最多经过兀次迭代就可以 找到的二次函数极小点。在无约束方法中许 多算法都是以共轨方向作 为搜索方向，它们具有许 多特点。根据构造共辘方 向的原理不同，可以形成 不同的共轨方向法。关键：新的共轨方向确定3. 共轨梯度法共轨梯度法是共轨方向法中的一种，该方法中 每一个共轨向量都是依赖于迭代点处的负梯度 而构造

26、出来。从屮出发，沿负梯度方向作一维搜索：dk=-Vf(xk)/+i =xk + akd * (k = 0丄 2,)设与小共轨的下一个方向小+i由於和点卅+，的负梯度的 线性组合构成，即：严=呵（*+】）+阳斤共轨条件：（djv/awo则:解得：pk =-Vf(xA)rV2/(x)-Vf(xA+1) + AA = OVf(x)rV2/(xA)-Vf(x)令 y(x) = x Gx +bJx +c为函数的泰勒二次展开式则 Vf(xk)=Gxk+bVf(xk+l) = Gxk+1+b上两式相减，并代入Xk+l =xk +akdkakGdk =Vf(xk+1)-Vf(xk)将式 aAG=Vf（xA&q

27、uot;）-W"）与式旷'=町（严 +则 转置两边相乘，应用共轨条件得：-vr（x）+後巧x）r号（卅为-巧（*）=oIIL.1. 1|2Vf（xA）rv（xA）|附（*）k+1因此 dk+1 =-Vf（xk+l） + /3kdk一冈（*）xk+i = xk + ockdk 伙=0丄 2,）（开始）*给定、&A*-0.v* 41 *-xk +akdk: min/3 +adk)A + l酬+l_g& +42求下列问题的极值f （兀）=xi +2兀；-4x -2xx2 ,已知初始点1，1丁迭代精度s = 0.001解：1）第一次沿负梯度方向搜寻 计算初始点处的梯度

28、x1 = x° +(z0J° =T+ a. 4=1 + 4%0丄0_-2_l-2a0_vr(x°)=4x2 一 2xX0为一维搜索最佳步长，应满足/(x1) = min/(x° +caZ0) = min(40cif2 一20&-3)aa得：= 0.25 x1 =20.5122）第二次迭代：WL.2520A=lk（x°）n2八一盼）+0°宀x2 = xl + ad1 =代入目标函数21.52 '-2 "2 +2a+ a_0.5_1.5_05 + 1.5af(x) = (2 + 2a)2 + 2(0.5 + 1.

29、5a)2 2(2 + 2q)(0.5 +1 5q) 4(2 + 2a)=如)由 0) = 0得 = 1x2从而有：因 |V/(x2)|收敛。：2)=&鲍威尔法是以共轨方向为基础的收敛较快的直接法之 一，是一种十分有效的算法。1964年，鲍维尔提岀这种 算法，其基本思想是直接利用迭代点的目标函数值来构造 共轨方向，然后从任一初始点开始，逐次沿共轨方向作一 维搜索求极小点。并在以后的实践中进行了改进。.Powee I法(共辘方向法、方向加速法):若沿连接相邻两轮搜索末端的向量s方向搜索，收 敛速度加快。其中：5=x2勺。因为两条平行线Sp S2与同心椭圆族相切，两个切 点的连线S直指中心。

30、称Sp S2与S为共轨方向。:以共轨方向打破振荡，加速收敛。这种方法是在研究具有正定矩阵A的二次函数 F(X) = XTHX+bTX+c 极小化的基础上形成。设X&, XE为从不同点出发，沿同一方向引进行一维搜索得到两个极小点, 如图所示。根据梯度与等值面垂直的性质，Sj与Xk, Xk+1两点处的梯度gp gk+1 存在关系.丁. 丁心5=0（sjy gk+=o对于上述二次函数，其x1% Xk+l两点处梯度可表示为gk=HX +b gk+=HXk+lb相减得m Ag 冲gR=H(X-Xk) 因而有(S丁(跖|gj |(sTh(x* |x*)I若取方向sk =xk+i-xk则s*和&am

31、p;共轨只要沿s防向分别对函数作两次一维搜索，得到两个极小点靜，xk+i9 两个切点（极小点）的连线所给的方向，就是与Sj 起对H为共轨方向。设A为实对称正定矩阵，若有两个"维向量&和S?, 满足AS2 =0,则称向量S和S?是关于矩阵共轨， ,和S?的方向是共辘方向。若4为单位矩阵/,贝IJ盯厲2=0时，即sj S2 -0, 则S和S?正交。设A为正定实对称矩阵，若有一组非零向量S,S2，.,S”， 能满足StT AS J = 0(/j),则称这组向量是关于矩阵4共轨。这组关于4矩阵共辘的斤个非零向量几S?,心是线性无关的。若/込心是线性无关的向量组，则可以构造出"

32、;个向量S,S2，,S”，满足S,7XSj=0,(心力6设5上2，心是关丁71矩阵共轨的斤个非零向量，对于函数/(X) 分别从两个初始点X。和*0出发，沿Si(i = 1,2,.,/?)方向进行一维 搜索，分别得到最优点和勺，向量S = E -勺 也是与向量组 Sj (i = 12屮)中每一个向量关于4矩阵共轨。设2，心是关于4矩阵共辘的个非零向量，则对于二次函数 f(x)C + BTX+-从任意初始点x出发，依次沿 s( = 12屮)方向进行一维搜索，至多斤步可收敛至极值点，称为 二次收敛性。第-轮迭代:选初始点X，令X。依次沿两个坐标轴方向押1）*?作两次-维搜索, 分別求巒（X舶极值点,

33、吃。构筑共觇方向：S=勺-X。,作第三次搜索，求得心）的极值点寸）。第二轮迭代：令x。=勺，分别沿S?,S方向作两次 一维搜索，分别求得'（M勺极值点计2），2（2）。构筑共轨方向：S=£-X。巴 沿此方向 作第三次搜索，求得'（Qd勺极值点X3。每轮迭代结束时，检验是否满足收敛条件:V®，r (*+1) r (k) Jo Jof.(Z< £*2 o°X1若满足，贝U X*="（Z。 若不满足，则作下一轮迭代。要点1）开始采用坐标轴方向；顺次沿n个方向做一维捜索得到一 个终点，由始点和终点构成一个新的方向。2）每轮迭代产生

34、一个新方向取代原来的第一方向，替换原则 是去掉原方向组的第一个方向而将新方向排在原方向的最后；n轮 迭代后可产生n个彼此共辘的方向；3）若目标函数为正定二次函数，n轮结束后即可到达最优点。改进鲍威尔算法1）每一轮迭代都用由始点和终点构成一个新的捜索方向代替 原方向组的第一个向量，而不管它的“好坏汁02）在改进的算法中首先要判断原向量组是否需要替换。若需 要替换，还要进一步判断原向量组哪个向量最坏，然后在用新的方 向替换这个最坏的方向或向量，以保证逐次生成共轨方向;3）每轮迭代中始点禺匚终点X/和反射点XX寫=2X；-X；沿方向S加=Xf-X：移动一个X；-X；距离令 F严F(X鳥(心0丄芥)G

35、0=F(X) = F0, G2=F(Xl)= Fn,G3=F(X=) Af = F-i - 片4）根据是否满足判别条件Gq<G0（G。-2G2 +G3）（Go-G2 A,） < 0.5，”（G° Gj确定是否要对原方向组进行替换a）若不满足判别条件，则下轮迭代仍用原方向组，并以X/和 X中函数值小者作为下轮迭代的始点。b）若满足判别条件，则下轮迭代对方向组进行替换，将补 充到原方向组的最后位.而除掉S/。即新方向组为SA s' Sgb Sg+十，s, S”+,作另下轮迭代馬接索方向。卞一轮迭代的 始点取为陰严方向进行一维搜索的极小点XJ+I5）判断是否满足收敛准则

36、这样重复迭代的结果，后面加进去的向量都彼此对G共轨,经门轮迭代即可得到一个由门个共轨方向所组成的方向组o对于二次函次，最多门次就可找到极小点，而对一般函数,往往要超过门次才能找到极小点（这里表示设计空 间的维数）。Powell 修正算法用Powell法求F(%兀2 )=10 E +x2-5)2+禽內尸的极小值解:取初始点Xo°=O, 0T,取初始捜索方向S1o=e1=1 0r,S2o=e2=O1r,初始点处函数值6。=化=代(&) = 250Si0X'Xj+eSf*+ Qa0F = F（xf） = 10（£Z -5）2 +%26F_ 4.5455a】 =10

37、0 / 22 = 4.5455 = 20（Q_5） + 2d da片=F(f ) = 22.272A】=代一片=250 - 22.727 = 227.273"4.5455"+ o?04.5455"0z_1_.a2 _巧=F() = 10(4.5455 +色5)2+(4.5455 -a2)2=20(勺_ 0.4545 )_2(4.5455 _色) da2n 4.5455 a. =18.181/22 =0.8264 X；=20.8264G?=巧=F(£) = 15.214A2 =F-F2 =22.727 15.214 = 7.513Sf, S2°A

38、m=A1 =227.273"4.5455"oX ?=2 X-X 讣=20.826409.90911.6528G3 =F(X?) = 385.24G3 <G0(G°-2G2+GJ(G°-G2-第二轮迭代：第二轮迭代初始点及其函数值X冷X；4.5455"0.8264J2<O.5A/77(Go-G3)2若是正定二次函数r n轮迭代后收敛于最优点x* o若是非正定二次函数,则迭代次数増加。若是n维问题r步骤相同。搜索方向：第一轮迭代，沿初始方向组(i=lf2n)的n个 方向和共辄方向Sf搜索n+1次得极值点xn+1w ;第二轮迭代f 沿方向

39、组Sj(i=lf2n ; i#m )的n-1个方向和共辘方向Sf 构筑共辘方向S搜索n+1次得极值点x”x。具中,为保证搜索 方向的线性无关,去除了 Sm方向。在第k轮迭代中,为避免产生线性相关或近似线性相关,需要 去除前一轮中的某个方向Sm(k)。一去除的原则请自学。计算步骤复杂；是二次收敛方法r收敛快。对非正定函数,也很有效; 是比较稳定的方法。前面介绍的许多优化方法，除鲍威尔（Powell）法和坐 标轮换法外，都需要计算目标函数的导数，而在实际工程的 最优化问题中，目标函数的导数往往很难求出或者根本无法 求出。下面所介绍的方法只需要计算目标函数值，无需求其 导数，因此计算比较简单，其几何

40、概念也比较清晰，属于直 接法的无约束最优化方法。这类方法适用于不知道目标函数 的数学表达式而仅知其具体算法的情况。这也是直接法的一 个优点。一、基本思想单纯形替换法也是一种不使用导数的求解无 约束极小化问题的直接搜索方法，与前面几种方 法不同的是，单纯形替换法不是利用搜索方向从 一个点迭代到另一个更优的点，而是从一个单纯 形迭代到另一个更优的单纯形。定义：单纯形门维空间中的恰好有门+1个顶点（极点）的有界的凸多体称之为一个单纯形。根据定义，可知，一维空间中的单纯形是线段，二维空间 中的单纯形是三角形，而三维空间中的单纯形则是四面体。在单纯形替换算法中，从一个单纯形到另一个单纯形的迭 代主要通过

41、反射、扩张、收缩和缩边这4个操作来实现。下面 以二维问题为例来对4种操作进行说明（参见下图）。如图4J9所示，在刃-Q平面上取不在同一直线上的三点刁、乃、乃,以它们为 顶点组成一单纯形（即三角形）。计算各顶点函数值，设/（xj） > /（X2）> /（x3）这说明点最好，却点最差。为了寻找极小点，一般说来，应向最差点的反对称方向进行 搜索，即通过站并穿过乞的中点池的方向进行搜索°在此方向上取点g使X5 = X4 +（*4 - X J = 2*4 - *1班点称作Xi M对于知点的反射点,计算反射点的函数值/（X5）,可能出现以下几种情形。1) /(x5) < f(x3)即反射点比最好点还好，说明搜索方向正确，还可以往前迈进一步， 也就是可以扩张e.这时取扩张点兀6 =兀4十么(玄4 一 *1)式中a扩张因子，一般取“ =1220。如果f (祐)</ (心)，说明扩张有利，就以必代替Xi构成新单纯形x2x3x6o否则说明 扩张不利，舍弃X6,仍以*5代替耳构成新单纯形*2工3巧。2) /(x3)</(x5) < f(x2)即反射点比最好点差，但比次差点好说明反射可行，则以 反射点代替最差点，仍构成新单纯形X