机械优化设计之无约束优化办法课件

1、机械优化设计何军良2016年9月2208:19Shanghai Maritime University190919121958200408:19Q优化设计概述0优化设计的数学基础働一维搜索方法ME无约束优化方法CONTENTS働线性规划约束优化方法机械优化设计中的几个问题第四章 无约束优化方法坐标轮换法共觇梯度法071变尺度法08鲍威尔方法091单形替换法08:194.7变尺度法（1）问题提出1)梯度法 XXjgk)*简单,开始时目标函数值下降较快,但趣来趣慢。2)阻尼牛顿法Xk+1 = Xk-aky2f(Xk)Yl7f(Xk)*目标函数值在最优点附近时收敛快”但要用到二阶导数和矩阵求逆。能否

2、克服各自的缺点,综合发挥其优点?变尺度法也称拟牛顿法,它是基于牛顿法的思想而又作了重大改进的一 类方法。我们所介绍的变尺度法是由Davidon于1959年提出又经 Fletcher和Powell加以发展和主善的一种变尺度法,故称为DFP变尺 度法。08:194.7变尺度法梯度法：x=x-agk牛顿法：严）"約-/戏九变量的尺度变换是放大或缩小各个坐标。通过尺度变换可以把函数的 偏心程度降到最低限度。这种算法仅用到梯度，不必计算海赛阵及其逆矩阵，但又能使搜索方 向逐渐逼近牛顿方向,具有较快的收敛速度。尺度变换技巧能显著地改进几乎所有极小化方法的收敛性质。例如在用最速下降法求/（%，%）

3、 =北了 +25上：极小值时，需要进行10 次迭代才能达到极小点。(2 )基本思想对于二次函数：/(x)二xTGx+bTx+c进行尺度变换“ 5目的：减少二次项的偏心在新的坐标系中，函数/仗)的二次项变为:-xrGx-xrQrGQx2 2如G是正定,则总存在矩阵0 ,使得:QtGQ = I1108:194.7变尺度法用矩阵O'右乘等式两边,得：QTG = Q1用矩阵0左乘等式两边,得：QQTG = I所以 Q0 =G-'上式说明：二次函数矩阵G的逆阵,可以通过尺度变换 矩阵4 = QQT来求得。1108:194.7变尺度法x(k+i) =xw -a(k)Akgk去为构造的&qu

4、ot;阶对称矩阵,它随迭代点的位置变化而变化,对梯 度起到改变尺度的作用,又称为变尺度矩阵。 Ak =1,上式为梯度法的迭代公式若念=Hk i ,上式为阻尼牛顿法的迭代公式(2)当矩阵去不断地迭代而能很好地逼近V7(x)-*时,就可以不再需要计算二阶导数。(3)变尺度法的搜索方向:S= -Akgk ,称为拟牛顿方向。 变尺度法的关键在于尺度矩阵绻的产生。(4)变尺度矩阵的产生拟牛顿方向S二血必须具有下降性、收敛性和 计算的简便性。下降性一妾求变尺度矩阵为对阵正定矩阵；收敛性-華求变尺度矩阵逐渐逼近砒,满足拟牛顿条件；简便性r望变尺度矩阵有如下递推形式: Ar+1 =k +k1108:194.7

5、变尺度法下降性:要求S与济之间的夹角小于90。f即：S伙)TgQO将拟牛顿方向带入上式,得：4S切Tg厂AkgkVgk=妆弘皿 > 0所以只要为对阵正定矩阵,S就是下降方向。(4)变尺度矩阵的产生简便性:变尺度矩阵是随迭代过程的推进而逐次改变的,因而它是一种矩阵序列念, k=l, 2,选取初始矩阵4。,并以梯度方向快速收敛,通常取单位矩阵E作为 初始矩阵,BPA0=Eo而后的矩阵均是在前一构造矩阵的基础上校正 得到,令勺讹+心。(.矩阵序列的推广到一般的反+1次构造矩阵/J基本迭代式J Ak称为校正矩阵1108:194.7变尺度法构造矩阵仏+1应该满足一个重要条件一J以牛顿条 件变尺度法

6、采用构造矩阵来代替牛顿法中海赛矩阵的逆阵 主要目的之一就是为了避免计算二阶偏导数和逆矩阵 力图仅用梯度和其他一些易于获得的信息来确定迭代方向 因此 拟牛顿条件是关于海赛矩阵和梯度之间的关系。(5 )拟牛顿条件设F3)为一般形式"阶的目标函数，并具有连续的一、二阶偏导。在点 工处的二次泰勒近似展开F(x)心 F(f) +心该近似二次函数的梯度为:VF(x) « gk +Hkx式中=，若令x = x('+i),则有k+igkHk(x(k+l)严)H k' (g k+ g Q(5 )拟牛顿条件上式中 ，无仗+1)X 称之为位移矢量,并简化书写:ak =x(k+l)

7、-x(k)而gk+1 - gk是前后迭代点的梯度矢量差 > 简化书写:儿=g 5 g k自以上三式得:bkHk海赛矩阵与梯度间的关系式1108:194.7变尺度法(5 )拟牛顿条件按照变尺度法产生构造矩阵的递推思想,期望能够借助前一次迭代的某些结果来计算下一个构造矩阵,因此可以根据上式,用第k+l次构造矩阵Ak+i近似代替<则上式即产生构造矩阵Ak+i应满足的一个重要条件 > 通常称为拟牛顿 条件或拟牛顿方程2108:194.7变尺度法(6)变尺度矩阵的构造拟牛顿条件% = Aui九 可写成(4 + AAJ %二空或4儿DFP算法中的校正矩阵 取为下列形式:将代入：yk +儿

8、=6 &几两边对比得：&川申；几=6， 0严":几=4取 uk =(Jkvk= A yk回代到(2)得：厶4 S 人几几4 A E儿丈4儿则：aFA=-1乂4儿DFP变尺度法的迭代式为：k+l =Xk -akAkVf(Xk)由上式可以看出，构造矩阵如+1的确定取决于第k次迭代中的下列 信息：上次的构造矩阵：Ak迭代点的位移矢量:6 = *2) _兀迭代点的梯度增量：儿因此 不必作二阶导数矩阵及其求逆的计算S儿儿4儿1708:194.7变尺度法(7) DFP变尺購法的特点 DFP算法的收敛速度介于梯度法和牛顿法之间。 DFP法具有二次收敛性(搜索方向的共觇性)。对于二次

9、函数F(x) , DFP法所构成的搜索方向序列S®, S，S(2)，为一组关于海赛矩阵H共辘的矢量，即DFP法属于共辘方向法f具有二次收敛性。在任何情况下f这种方法对于二次目标函数都将在步内搜索到目标函数的最优点 而且最后的构造矩阵A必等于海赛矩阵H。1.关于算法的稳定性 数值计算稳定性较差。算法的稳定性是指算法的每次迭代都能使目标函数值单调下降。2.构造矩阵正定性从理论上肯定了DFP法的稳定性，但实际上f 由于每次迭代的一维搜索只能具有一定的精确度,且存在机器 运算的舍入误差，构造矩阵的正定性仍然有可能遭到破坏；3为了提高实际计算中的稳定性,_方面应对一维搜索提出较高 的精度要求,

10、另一方面,当发生破坏正定性时,将构造矩阵重 置为单位矩阵E重新开始,通常采用的简单办法是在«次迭代 后重置单位矩阵1908:194.7变尺度法（8） DFP变尺度算法的计算步骤1.任取初始点卅）给出迭代精度£计算初始点精度g。商（八）及其 模Iloilo若血卜碍专步骤（7），否则进行下一步2.置氐0 ,取 Ak-E3计算迭代方向S=-AkgklQS方向做一维搜索求优化步长 a,使Fx（k）+a（k）S伙）= min F（x +&S伙）确定下一个迭代点严）=F）+/）s 2108:194.7变尺度法（8） DFP变尺度算法的计算步骤4计算泌+】）的梯度+1及其模ll+

11、i|，若I以+§ £则转步骤, 否则转下一步5计算位移矢量6和梯度矢量儿6 =兀（2）兀伙）儿=孤+1一孤按DFP公式计算构造矩阵4+14.Ak yk yTk AAk *rTyk $k A 儿6.豊k-Z 若k<n （n为优化问题的维数）返步骤 >否则返步骤7输出最优解（兀*，”*），终止计算22n8:1923n8:19D F p算法流程图输入:k jO A计算：g(0)(O)JI I.F (x(o)A")yy% A“+i) a(«)+ m _ N伙+1)S伙+】）x(0) J x(ul)(+1)(斤+1)X*F* J F(x*)Sj_f)g

12、min F(x(/:) + a(k)S(k) > ak)严)Sg 伙+1）jVF（兀伙+1）<?出口2308:194.7变尺度法(9) DFP算例例：用DFP算法求下列问题的极值：/(x“2)= 4jT - lxxx2解：1 )取初始点X0 = 1 1；为了按DFP法构造第一次搜 寻方向別,需计算初始点处的梯度Vf(x°) =4x2 2兀-423108:194.7变尺度法3108:194.7变尺度法取初始变尺度矩阵为单位矩阵4。訂f则第一次搜寻方向为rf0=-A0Vf(x°) = -0_-41_ 4_12-210(9) DFP算例沿別方向逬行一维搜索,得11x1

13、 = x° + a odQ4-2+仏。2%3108:194.7变尺度法3108:194.7变尺度法得：勺=0.25 疋2 ）再按DFP法构造点0处的搜寻方向/ ,需计算_维搜索最佳步长应满足/(x1) = min/(x° + cif0J0) = min(40cif()2 20a()-3)aa2 10.53108:194.7变尺度法3108:194.7变尺度法巧（丄）=3108:194.7变尺度法(9) DFP算例Ag°=gl-g°Ax° = x1 -x°代入校正公式0 _ Ax°Ax° r A0Ag0Ag°

14、;rA0 "Ax°rAg° Ag°rA°Ag01-0.51 -0.5丁-43 -41 -0.5'3 '-43 -4_ 3 _-4(9) DFP算例3108:194.7变尺度法3108:194.7变尺度法9-12A110-1216第二次搜寻方向为dl=-Algl =866521251950195041Too3108:194.7变尺度法3108:194.7变尺度法2 + a.5 1n c 60.5 H of5 1再沿 1进行一维搜索"得x2 = X1 + axd1 =3108:194.7变尺度法(9) DFP算例匕为一维搜

15、索最佳步长,应满足/(x2) = min/Cx1 +a/T) = min(-4al)52a得52伶 a= x14梯度：Vf(x2) =海赛矩阵:V2/(x2) =2兀一 2兀44x2 2xx2 -2-24X23 )判断妒是否为极值点因此为极小点。2808:194.7变尺度法K'S梯度为零向量，海赛矩阵正定。可见满足极值充要条件因此为极小点。2808:194.7变尺度法(9) DFP算例例:用DFP变尺度法求目标函数F(x) = 4(“ 5严 +(£ -6)2的最优解。已知初始点严=89丁 ,迭代精度沪0.01_24_8_24列) -6 |_9 6cif(0)解:第一次迭代:g

16、o = VF(x(0)=8(%| 5)2(x2 6)(8,9)'24_6g°| =24.3>gs(°)=A)go =-24_-6MM(1)JO)Q+ 9 *-8.21538gl=VF(x(1) =-0.107844.43076(9) DFP算例式中最优步长应用一维搜索方法在计算机上求解。为了说明问题,又因为此例目标函数简单,所以用解析法来求:F(x(1) = f(a) = 4(8 - 24a) - 5+ (9 -6a- 6)2得：a(0) =0.13077为求极小 > 将上式对疣求导 < 并令厂盘）=0于是：%(1)4.861521g =4.567

17、16£(9) DFP算例第二次迭代: 确赶点的拟牛顿方向Scr0 = xx(0)=-3.13848-0.78462y()= gigo =- 25.10784-1.56924按DFP公式计算构造矩阵刍F+寧聖产5)X) y0 A)X)316U808寸Z8寸寸 -2n<IHr ZJO8ZOf-111N<urla)sss匡mCHa (6) ss卜寸4.7 ss(9) DFPW0U2IIX2II一4.9999才6.00014_-0.00016'0.00028H 0.00032 A m4.999900!600014908:194.7变尺度法(9) DFP算例讨论:o按DFP

18、搜索方向为共辘的性该题的理论最优点是质,本题为二元二次函数在两次迭代后即达到最优点,本题计算 结果稍有误差，这是由于一维搜索的不精确性产生的。若在已知A】的基础上f再用DFP公式递推下一次的构造矩阵f可计算得0.12500A =200.5000而计算目标函数海赛矩阵的逆阵有J.804.7变尺度法(9) BFGS变尺度法DFP算法由于舍入误差和_维搜索的不精确,有可能导致奇异,而使数值稳定性方面不够理想。所以1970年,Broyden、Fletcher、Goldstein、Sharnio等人提出一种更稳定的算法,称为BFGS算法。其校正公式为:4.8鲍威尔方法（1）概述I基本思想：基于坐标轮换法

19、,不用求导数,在迭代中逐次 产生共辘搜索方向。收敛效果：对于正定（有极小值）二次函数,经过兀轮迭代 后求得极小点；对于非二次函数,一般也具有较高的收敛 速度。Powell法是求解无约束优化问题的最好方法。将其与惩罚 函数法结合,可以处理有约束优化问题。3408:194.8鲍威尔方法（2 ）共辘方向的生成xxk+i为两个极小点根据梯度与等值面之间关系可知（刃）1 =0（刃丁（氣1一緞）=°（/） gk+ o(2 )共辘方向的生成384.8鲍威尔方法(2 )共觇方向的生成（刃X+i-gQ = （结论：从不同的点出 发沿某一方向分别对9k函数作两次一维搜索,得到两个极小点 那么这两个极小点

20、的 连线方向与该方向对G共觇08:193908:19TG(xk+l-xk) = OdJ9k+idk3908:194.8鲍威尔方法4008:194.8鲍威尔方法（3 ）基本算法鲍威尔基本算法的搜索过程（二维）X）任选一初始点0 再 选两个线性无关的向量 如坐标轴单位向量 匂二1,0卩和乞二0，1卩作为 初始搜索方向。（3 ）基本算法鲍威尔基本算法的搜索过程（二维）2）从0出发，顺次沿珀乞 作一维搜索f得城，扃点， 两点连线得一新方向加4008:194.8鲍威尔方法（3 ）基本算法鲍威尔基本算法的搜索过程（二维）用/代替匂形成两个线性无关向量/岛作为下一轮迭代的 搜索方向。再从城出发沿/作一维搜索

21、得点兀罷作为下一轮迭代的初始点。3 ）从球岀发,» e2?> d1作一维搜索,得到 点x；, 两点连线得一新 方向：d = x2 xo从現沿/作一维搜索得点X2 O即是二维问题的极小点疋(3 )基本算法鲍威尔基本算法的搜索过程(二维)方法的基本迭代格式包括共辘方向产生和方向替换两主要步骤。° 4308:194.8鲍威尔方法(3 )基本算法鲍威尔基本算法的搜索过程(三维)1.第一轮基本方向组取单位坐标矢量系 % g e“ ,沿这些方向依次作一维 搜索,然后将始末两点相连 作为新生方向。轮的基本方向组是将上轮的第一个方向淘汰,上轮的新生方向补入本轮的最后而构成：d2k,

22、d3k, dk2.再沿新生方向作一维搜索， 完成第一轮的迭代。以后每4908:194.8鲍威尔方法4908:194.8鲍威尔方法(4)基本算法示例4908:194.8鲍威尔方法4908:194.8鲍威尔方法例 用Powell方法求解下列问题;min/(x) (Xi +> +(4 1)*解 取初始点和初始搜索方向分别为4908:194.8鲍威尔方法4908:194.8鲍威尔方法4908:194.8鲍威尔方法(4 )基本算法示例第1轮迭代置<1>0)下面用解析法求*x)沿直线的极小点.先沿边°作一维搜索，min yXF®基本算法示例令卩(入)=兀*5+加小“)

23、=(3+A)2 +<1+A)S 如=2C3+A) +2(1+入)=0, dA得到 Ai = -2,x<1*n = (0,1)T再从出发，沿出m作一维搜索:4908:194.8鲍威尔方法4908:194.8鲍威尔方法min /(xGU,十疋J, X4908:194.8鲍威尔方法4908:194.8鲍威尔方法令爭 GO = /(xu-n + 人护 2) = (1+A)2 + 1, 学=2( 1 + A) 0,dA47得到九=U" =(0,0)T.(4 )基本算法示例令方向 就“=x(1,2> x(K<>> = *.作一维tn搜索:min 彳(算门+屈&

24、quot;3八A令甲=y(x<K2) + W約)=(3A)2 + ( 2A I)2. 霑=1%-4(-24 1) = 0,得到山=_邑4908:194.8鲍威尔方法(4 )基本算法示例经第1轮迭代，得到最好点4908:194.8鲍威尔方法4908:194.8鲍威尔方法- 2人-A13213=一卸494.8鲍威尔方法(lf2>(2+2)(4 )基本算法示例第2轮迭代+第2轮的搜索方向为(2.1>初始点为斗=兀08:194132135008:194.8鲍威尔方法(4 )基本算法示例下面仍用解析方法求八工)在直线上的极小点.先沿占?小搜索:min 心“ +加)，A5108:194.

25、8鲍威尔方法5108:194.8鲍威尔方法得到Ai =鲁及点算仁.1)= x(2,0> + 入if 门"4 "r4 _13_ 6'O'13213 1.413OX!_13 J5108:194.8鲍威尔方法5108:194.8鲍威尔方法(4 )基本算法示例再沿搜索:min /(x<2a)+加3亠A5108:194.8鲍威尔方法5108:194.8鲍威尔方法得到a2 = -18169及点x(2> =工宀小十&"> =13r 88 -169_ 34厂而一5108:194.8鲍威尔方法(4 )基本算法示例5108:194.8鲍

26、威尔方法_兀(20)4-'361316926013_一 169-8816934169r 8旷-361699169l n+ V344,60-1 -169MB169A最后，从屮岀发，沿出门作一维搜索: min /(x(2'2) +Arf(2>).AQ得到入严才及极小点文=±22> +和肝)514.8鲍威尔方法(4 )基本算法示例I08:190町2#08:194.8鲍威尔方法(5)基本算法缺陷况。如第k轮中f产生新的方向:可能在某一轮迭代中出现基本方向组为线性相关的矢量系的情Jk=xnk-xok=a1kJ1k+ a2kJ2k + + anMnk式中 £

27、叱砒.心*为第k轮基本方向组矢量，5508:194.8鲍威尔方法(5)a2 禺*为各方向的最优步长。若在第k轮的优化搜索过程中出现,则方向小表示为姑. d3 血啲线性组合，以后的各次搜索将在降维的空间 逬行,无法得到维空间的函数极小值,计算将失败。#08:194.8鲍威尔方法(5)基本算法缺陷56鲍威尔基本算法的退化如图所示为一个 三维优化问题的 示例,设第一轮 中咕0 ,则新 生方向与巧、e3 共面,随后的各 环方向组中,各 矢量必在该平面 内,使搜索局限 于二维空间,不 能得到最优解。08:194.8鲍威尔方法(5)（5 ）基本算法缺陷例用Powell方法求解卜列问题：min （4 + 工

28、3）+（ Hi 十 + 並）'+（Q + 孔一工3）2 +取初始点才' = （*",*），搜索方向基本算法缺陷解用Powell方法求解.首先置丘“），从0】小出发，沿川“搜索: min /（x（1-0> +洌小），"in211AJ+A1丄护（入）=y）十=（i-a）2+a2 +（i+a>5908:194.8鲍威尔方法(5)基本算法缺陷令 /(A)=0,即 一 2(1人)+2入+ 2( 1+4) = 0.由此得到Ai =0,因此有#08:194.8鲍威尔方法(5)#08:194.8鲍威尔方法(5)LTJ#08:194.8鲍威尔方法(5)#08:19

29、4.8鲍威尔方法(5)从0Z岀发沿肝搜索:T 1 -TVT1+ A11 +入101石己小+ W)=616U80無曲5!吴羈鮒 ou(K+I)z+Q+s 戢6"(0*令 (K + I) + 人YI) + = K+ I) " ( £二PK+ =【>)、=:Q)38G08:194.8鲍威尔方法（5 ）基本算法缺陷再从Qg出发，沿於心搜索:6108:194.8鲍威尔方法#08:194.8鲍威尔方法x(r23 +=O'0丄T丄T_i+A令屛（入=0号即2（扌+入）+2（* +入）一2厂入=0,#08:194.8鲍威尔方法6308:194.8鲍威尔方法(5)基本

30、算法缺陷#08:194.8鲍威尔方法#08:194.8鲍威尔方法得到入产_壬及点#08:194.8鲍威尔方法#08:194.8鲍威尔方法xu,3> = x<ls2> 十 Aid丄2"1T_18.#08:194.8鲍威尔方法(5 )基本算法缺陷第1阶段迭代的最后一步是从疋z出发，沿方向丄181T1丄T0一2_2_9作一维搜索:min+0Z 人(5 )基本算法缺陷min /（x<n3?6508:194.8鲍威尔方法#08:194.8鲍威尔方法丄T518O'3L184a6708:194.8鲍威尔方法#08:194.8鲍威尔方法爭（入）=/（x（n3>

31、+0"）#08:194.8鲍威尔方法(5)基本算法缺陷令“)= 0.即5)-由此得到局=寺及点8丄X*1® +姑旷X)=丄1#08:194.8鲍威尔方法(6 )修正算法#08:194.8鲍威尔方法(6 )修正算法(5)基本算法缺陷#08:194.8鲍威尔方法(6 )修正算法#08:194.8鲍威尔方法(6 )修正算法由第1轮搜索结果可知.在第2轮搜索时，前3个方向占1线性相关,#08:194.8鲍威尔方法(6 )修正算法#08:194.8鲍威尔方法(6 )修正算法继续作下去，所得点的第一个分量恒为此永远达不到极小点x=(0,0,0>T,#08:194.8鲍威尔方法(6

32、 )修正算法#08:194.8鲍威尔方法(6 )修正算法可见：如果在某轮迭代中,#08:194.8鲍威尔方法(6 )修正算法#08:194.8鲍威尔方法(6 )修正算法个搜索方向线性相关或近似线性相关,#08:194.8鲍威尔方法(6 )修正算法#08:194.8鲍威尔方法(6 )修正算法会给Powell方法的收敛性带来严 重后果口选取个线性无关且尽可能共辘的方向作为下一轮搜索的方向组。做法：形成新的搜索方向组时,不是定的去掉前一次搜索方向组中的第一个方向 < 而是首先根据Powell条件f判断原方向组是否需要替换f 若需要,则进一步判断原方向组中哪个方向最坏 <并以前一轮新生成的

33、 搜索方向替换本轮中的这个最坏方向。*根据Powell条件判定是否需换方向；如需换向,则换掉函数值下降量最大的方向。方向组的构造在第吃轮的搜索中 < 祁为初始点 > 搜索方向为上 兮 心J产 生的新方向为冰 > 此方向的极小点为兀b沿冰方向移动得到点上2旺上 X0k <称之为k对的反射点。计Xj . Xn水各点的函数值f记作:F0=F(x/)F2=F(x/)F3=F(Xn+lk)企Am = max Az = Fm_x<i<n/是第花昶方向组中,依次沿各方向搜索函数下降值7108:194.8鲍威尔方法鲍威尔算法的方向淘汰7308:19为了构造第加J轮基本方向组

34、 < 采用如下判别式:F3 < F。9 A9（F0-2F2+F3XF0-F2-AJ2 V（化耳）2按照以下两种情况处理:1)上式中至少一个不等式不成立 < 则第疋+1轮的基本方向仍用老 方向组人d2 心k。疋+7轮的初始点取xok+1=xnkF2<F3#08:19f2>f37508:194.8鲍威尔方法(6 )修正算法2 )两式均成立,则淘汰函数值下降最大的方向,并用第花轮的新生方向补 入氐+7轮基本方向组的最后,即反+7轮的方向组为上J2k 血J、盅、护。吃+7轮的初始点取:兀严$ 卅是第吃轮沿'方向搜(F0)#08:194.8鲍威尔方法(7 )修正算法

35、步骤Powell算法的步骤如下：任选初始迭代点轴选定迭代精度S取初始基本方向组为单位坐标矢量系di =勺其中,i=l, 2n然后令氐=1 (轮数)开始迭代沿d：诸方向依次逬行次一维搜索,确定各步长F + oc： d： ) = min F)得到点阵X- -d. i=l , 2 n构成新生方向dk=xkn-x沿dk方向逬行一维搜索求得优化步长/k k .k jkx =xn+a d(3)计算各迭代点的函数值F(灯找岀相邻点函数值差最大者A/n = maxtFC) - F(x：) = Fm_x - Fm ( l<m<n )及与之相对应的两个点4-iin 4,并以 必表示两点 的连线方向。7

36、908:194.8鲍威尔方法(7 )修正算法步骤(4 )反射点函数值尤+i二2疋-点F严 F%F2=Fx）耳"（监）(5 )判断是否满足迭代终止条件。 Xq W £则可结束迭代,最优解为 兀* = 尸=F(x*) 停止计算。否则,继续逬行下步。8108:194.8鲍威尔方法（7 ）修正算法步骤检验鲍威尔判别条件是否成立（化2耳+九）（化笃AJ2 V（化耳尸若至少其中之一不成立转下步f否则转步骤确定k+1轮的基本方向组和起始点盗1 J古（即取老方向组）08:194.8鲍威尔方法（7 ）修正算法步骤08:194.8鲍威尔方法（7 ）修正算法步骤步骤< I 当 F2VF3&

37、lt; I 当F2NF3令k<-k+l f7508:194.8鲍威尔方法（7 ）修正算法步骤（7）确定k+1轮的方向组和起始点#08:194.8鲍威尔方法（7 ）修正算法步骤#08:194.8鲍威尔方法（7 ）修正算法步骤+1 <9，返回ik必”久）7708:194.8鲍威尔方法(8)算例丨的极小值例 用鲍威尔法求函数/ W *2 ) = Eg +兀2 - 5)2 + g “2 F解：选取初始点X冷0 of ,初始搜索方向亦"1 = 1 0r d、e2 = 0 1T 初始点处的函数值% = f0 = /(x；)= 250第一轮迭代:1)沿岸 方向进行一维搜索,得：苗 &#

38、163;卜彳: 其中务为一维搜索最佳步长,应满足fl = /(X°)= min + axd= min(l laj 100«)250)4.54550得：=50/11=4.5455 X；=所以，/I = /(云°)= 22.727A, =/0-f1 = 250-22.727 =227.2737908:194.8鲍威尔方法(8)算例4.54550+ a24.5455a22)再沿 此方向逬行一维環索，得：X? =X :+也？=其中为一维搜索最佳步长，应满足：得:所以，f2 = /(X； ) = min f(x + a2d= min(l la22 200a2/11 + 25

39、0/11n 4.5455a。= 0.8264X。=220.8264F2=f2 = f(x)= 15.214 A2 = /1-/2 = 22.727 -15.214 = 7.513=227.273“=/(X?)=385.24取沿曲搜索的函数值増量的最大者=max人1亠=人1 终点理的反射点和函数值为:9.09 r1.6528所以 f /I = /（X；）= 10.185$ =/0-/1 = 15.21410.185 =5.0298108:194.8鲍威尔方法（8）算例3 ） Powell条件判断：F3>F0 ,不满足判别条件”因而下轮迭代应继续使用原来的搜索方向说#2 因为巧< ”所

40、以取卍为下轮迭代起始点X；.4.5455化=/0 =心）=15.214第二轮迭代:+ a4.54550.82644.5455 +Q0.82640.82641 ）沿d方向进行一维搜索，得：X； =其中为一维搜索最佳步长，应满足/1 = /（X；）二 min /曲+讹）二 01山（1站+14.8762少+15.2148倚. = 0.6762 X；=3.8693_0.8264所以 f /I = /（X；）= 10.185$ =/0-/1 = 15.21410.185 =5.0298308:194.8鲍威尔方法(8)算例_3.8693_0.8264+ OC-,'O' 3.8693 _0

41、.8264+ c（212 )再沿d；方向逬行一维搜索,得:其中a2为一维搜索最佳步长,应满足：/2 = /（X；） = min /（X； + a.d）= min（l la22 -12.1718a2 +10.18523.8693'1.3797X = X + oc2d =X；得：oc2 = 0.5533所以 > 耳= /2 = /（X；）=6.818 A2 =/1-/2 = 10.185 -6.818 =3.367取沿 几鸥搜索的函数值増量的最大者=吋终点罔的反射点和函数值为:3.19311.9330X： = 2X； - X；耳=/区）=1747A】A2 = A! =5.029所以

42、f /I = /（X；）= 10.185$ =/0-/1 = 15.21410.185 =5.0298508:194.8鲍威尔方法pl(8)算例满足3 ) Powell条件判断：-0.67620.5533(从2巧+血X佗一耳, J < 0.5，” (九一血尸用新方向必替换d = e ,下轮搜索方向为e2,d 冷X；-X冷下轮起始点X为从X；出发f沿百搜索的极小点:3.8693 06762勺13797 + 05533勺-0.67620.5533其中«3为一维搜索最佳步长，应满足/0 = /（X： ） = min f（x + a3d） = min（1.6627«32 67

43、34勺 +6.81812.49952.5059X j = X； + otd 3.86931.3797+ °3得：如=2.0257x j =化=/0 = /（X；）= 0.000808:194.8鲍威尔方法08:194.8鲍威尔方法81已足够接近极值点2.5 25卩。08:204.9单型替换法（1）基本原理单形替换法是利用对简单几何图形各顶点的目标函数值作相互比较,在 连续改变几何图形的过程中,逐步以目标函数值较小的顶点取代目标函 数值最大的顶点,从而进行求优的一种方法,属于直接法之一。现以求二元函数的极小点为例,说明单形替换法形成原理.设二元函数/（X） = /（"X2）在

44、习-兀郢面上取不在同一条直线上的三个点X| ,x2和忑，并以它们为顶点构成一单纯三角形。算出各顶点的函数值&2）（冷），比较其大小，现假定比较后有/(X1)>/(X2)>/(X3)这说明点/最差,点心最好,点心次差。为了寻找极小点,一般来说应向最差点的反对称方向进行搜索(1)基本原理以X4记为X2X3的中点(如图所示),在XX4的延长线上取 点X®使x5 -X4+(X4-X1)-2X4-X1算岀的函数值TUG)，可能出现以下几种情形:称为X 5是X(1)基本原理(1)f(x5)<f(x3)这说明搜索方向正确,可逬一步扩大效果,继续沿X1X5向前搜索,也就是向

45、前扩张。这时取x6 =X4+g(X4X)其中oc为扩张因子,般取a = 1.2 2.00如果/(X6) < /(X5),说明扩张有利,就可以点X6代替 点X构成新的单纯形X2,X36o如果f(X6) > /(X5),说明扩张不利,舍去点X6,仍以点X5代替X1构成新的单纯形X?, X3, X5 。(1)基本原理(2) /(X3)</(X5)</(X2)这说明搜索方向正确，但无须扩张,以X5代替X构成新的单纯 形X2, X3,X5。(3) /(X2)</(X5)</(X1)这表示X 5点走得太远，应缩回一些。若以0表示压缩因子,则有X7 =X4 +0(X5 X4)P常取为05。以X7代替x 1 构成新的单纯形X2, X3, X?(1)基本原理 f(X5)>f(Xi)这时应压缩更多一些,将新点压缩至X X4之间，令X8 = X4 _0(%4 _XJ = X4 +0(X1 _乙) 如果/(X8)</(X1)则以X*代替X构成新的单纯形 X2,X3,X8否则认为X1X4方向上的所有点的函数弩(X)都大于/(XJ,不能沿此方向搜索。这时,可以以X巾中心逬行缩边,使顶点X和X2向X3移近一半距 离,得新单纯形X3, x9, X10.以此单纯形为基础再逬行寻优。(2 )计算步骤(1)令X产X°+辰丿= 1,2,”构造单纯形X