现代设计方法5 优化设计

1、优优 化化 设设 计计第五章第五章 优优 化化 设设 计计传统机械设计中，存在选优的思想，受时间、条件的限制，计算机应用前用数学极小化处理简单问题。随着1946年第一台计算机问世，传统设计转化为优化设计方法。优化设计是以数学规划理论为基础，以计算机为工具优选设计参数的一种现代设计方法。5.1 优 化 设 计 的 数 学 模 型v下面举例说明： 用薄钢板制造一体积为5m3，长度不小于4m不带上盖的货箱，要求该货箱的钢板耗费量最小，试确定货箱的长X1，宽X2，高X3。X2X1X3v解：钢板的耗费量与货箱的表面积成正比，优化设计的目标是钢板的耗费量最少，即货箱的表面积S最小，不带盖的货箱表面积vS=

2、X1*X2+2(X2*X3+X1*X3)vS是X1、X2和X3的函数，称为目标函数。v参数X1、X2和X3称为设计变量。v优化设计就是恰当地选择这些参数(设计变量)，使货箱表面积S(目标函数)达到最小。v选择这些参数受到货箱体积和长、宽、高限制：vX1*X2*X3=5， X14,X2 0,X3 0v以上限制设计变量X1,X2,X3的表达式，称为约束条件。v已知：传动比i, 转速n, 传动功率P，大小齿轮的材料，设计该齿轮副，使其重量最轻。v分析：(1) 圆柱齿轮的体积(V)与重量(W)的表达；v (2)设计参数确定：模数(m)，齿宽(b)，齿数(z)。v (3)设计约束条件：v(a)大齿轮满足

3、弯曲强度要求；v(b)小齿轮满足弯曲强度要求；v(c)齿轮副满足接触疲劳强度要求；v(d)齿宽系数要求；v(e)最小齿数要求。例 问题的数学表达v设计变量： x = m z bTv设计目标：min W=rpb(mz)2+(miz)2/4v约束条件： g1(x)=sF1sF10v g2(x)=sF2 sF20v g3(x)=sH sH10v g4(x)=b 1.2mz0v g5(x)=17 z0建立优化设计问题的数学模型步骤v1)根据设计要求，应用专业范围内的现行理论和经验等，对优化对象进行分析分析。必要时，需要对传统设计中的公式进行改进，并尽可以反映该专业范围内的现代技术进步的成果。v2)对结

4、构诸参数进行分析，以确定设计的原始参数、设计常数和设计变量设计变量v3)根据设计要求，确定并构造目标函数和相应的约束条约束条件件，有时要构造多目标函数v4)必要时对数学模型进行规范化规范化，以消除诸组成项间由于量纲不同等原因导致的数量悬殊的影响5.1.1. 数学模型的一般形式：优化设计的数学模型由设计变量、目标函数和约束条件三部分组成。统一形式： 求变量： x1, x2, , xn使极小化函数： f (x1, x2, xn)满足约束条件：gu(x1, x2, , xn)0 (u=1,2, ,m) 不等式约束条件 hv(x1, x2, , xn)=0 (v=1,2, ,p) 等式约束条件 v设计

5、变量可用向量表示：v X= x1, x2, , xnTv XRn 向量X属于n维实欧氏空间v s.t. (subject to)表示 “满足于” 。v优化设计的数学模型可表达为如下的标准形式： min f (X ) XRns.t. gu(X )0 (u=1,2, ,m) hv(X ) = 0 (v=1,2, ,p)v求极大时将目标函数写为f(X)即可。同样，当不等式约束条件中的不等号为“0”时，只要将不等式两端同时乘以“1”，即可得到上述标准形式。 v最优化问题也称数学规划问题，若目标函数和约束函数均为设计变量的线性函数时，称此设计问题为线性优化问题或线性规划问题。说明：(1) 设计变量与设计

6、空间v选择与目标函数、约束函数密切相关，能表达设计对象特征的独立参数和尺寸。vn个设计变量x1, x2, , xn，相互独立，形成向量X=x1, x2, , xnT的全体集合构成一个n维实欧氏空间，称设计空间xn，n称为设计空间的维数。n=2时设计空间为二维平面。5.1.2. 优化设计的基本要素： 约束条件：对设计变量取值时的限制条件。分为：等式约束： hv(X)=0 (v=1,2, ,p) 不等式约束：gu(X)0 (u=1,2, ,m) 约束边界所包围的区域是设计空间中满足所有不等式约束条件的部分，在这个区域中所选择的设计变量是允许的，称为设计可行域。 由是否满足约束条件将设计点分为可行点

7、(内点)和非可行点(外点)。(2)约束条件与可行域vg1(X)=x1+x220vg2(X)=x12x2+10vg3(X)=x10例：x1x2可行域可行域g2(x)g2(x) = 0g3(x) = 0g1(x) = 0将所追求的设计目标用设计变量的形式表达出来，称为建立目标函数。一组设计变量值在设计空间确定一个设计点，对应这一点有确定的函数值。反之，当函数为某一定值时，如f (X ) = c,则可有无限多组设计变量X1, X2, , Xn值与之对应，即有无限多个设计点时对应着相同的函数值。因此这些点在设计空间中将组成一个点集，将此点集称为等值曲面或等值超曲面(若为二维设计空间则称为等值域)。(3

8、)目标函数与等值域v简单二维问题，在平面内作出约束可行域，画出目标函数的等值域，找出最优点。v步骤：确定设计空间约束可行域目标函数等值线最优点v例： min f(X)=x12+x224x1+4 s.t. g1(X) = x1+x220 g2(X) = x12x2+10 g3(X) = x105.1.3 优化问题的图解法图解法vmin f (X )=x12+x22 4x1+4v s.t. g1(X) = x1+x220v g2(X) = x12x2+10v g3(X) = x10 x1x20123451234f (X ) = 16f (X ) = 1g3(x)g2(x)g1(x)f (X ) =

9、 9X* = 0.58, 1.34T65.2 优化方法的数学基础5.2.1 梯度(求解出数的最速下降方向)v定义下列向量： 为函数f(X)在X(k)点的梯度，简记为f，也可记作grad f(X(k)。TnkkkkxXfxXfxXfXf)(,.,)(,)()()(2)(1)()(v(1)函数在一点的梯度是对设计变量Xi(i=1, 2, n)一阶偏导组成的列向量。表示函数在X(k)点的最陡上升方向，是函数的一种局部性质。反映X(k)邻近函数的性质，梯度大小是其模长。v(2)梯度向量f (X(k)与过X(k)点的等值线(或等值面)的切线是正交的。函数的梯度f具有如下几个性质：函数的梯度f具有如下几个

10、性质：v(3)负梯度向量f (X(k)是函数在X(k)点的最速下降方向。v例：求二元函数f (x1, x2)= x12+x224x1+2x2+5在 X0=2，2T处的梯度及梯度的模。vf(X) 的泰勒二阶近式。v其中2f(X(k)是由函数在点X(k)的所有二阶偏导组成的矩阵，称为函数f(X)在点X(k)的二阶导数矩阵或Hessian矩阵H(X(k)。( )( )( )( )2( )( )()()() )1)()2kkTkkTkkf Xf Xf XXXXXf XXX 5.2.2 多元函数的泰勒展开(函数的近似表达式)v函数的二阶偏导值对于变量的偏导次序无关，是一nn阶实对称矩阵。取其前二项，可得

11、函数的泰勒线性近似式：v f(X)f(X(k)+f(X(k)TXX(k)2( )2( )2( )211212( )2( )2( )2( )221222( )2( )2( )212()()()()()()()()()()kkknkkkknkkknnnf Xf Xf Xxx xx xf Xf Xf Xf Xx xxx xf Xf Xf Xxxxxx v 解：f (X(1) = 3211(1)212213690()336xxf Xxx 12(1)12166 012 0()0660 0 xf Xx 11(1)221111xxXXxx 例：用泰勒展开将函数f(X)=x13x23+3x12+3x229x1

12、在点X(1)=1，1T 简化成线性函数和二次函数。v代入得简化的线性函数：二次项：(1)(1)(1)122()()()130 3136Tf Xf Xf XXXxxx (1)2(1)(1)1122211()2112011110026(1)TXXfXXXxxxxx v 简化的二次函数：vf(X)=3x26+6(x11)2=6x1212x1+3x2vX(1)=1,1T代入线性二次函数都等于3，与原函数相等。5.2.3.二次函数：v形式：f (X ) = X T H X / 2 + B X + CvH22阶常数矩阵vC常数向量vXTHX称为二次型，H称二次型矩阵，相当于函数的二阶导数矩阵。v对于非零向

13、量X： 若 XTHX 0 H 正定 XTHX0 H 半正定 XTHX0v各阶主子式大于0是正定矩阵。*20()02H x20002v在 X*处取得极值，其必要条件是:v即在极值点处函数的梯度为n维零向量。v为了判断从上述必要条件求得的 X*是否是极值点，需建立极值的充分条件。v根据函数在 X*点处的泰勒展开式，考虑上述极值必要条件，可得相应的充分条件。12()0TXnffff Xxxxv即要求H(X*)各阶主子式均大于零。2*2*2*211212*2*2*2*221222*2*2*212()()()()()()()()()()nnnnnf Xf Xf Xxx xx xf Xf Xf Xf Xx

14、 xxx xf Xf Xf Xxxxxx 正定(1)概念：v对于多变量、多约束非线性优化问题，采用数值迭代法；对于极小化问题，采用下降迭代法。初始X(0)产生点列： X(0), X(1), X(2), X(k), X(k+1)v对应目标函数： f(X(0) f(X(1) f(X(k) f(X(k+1) (下降) 且 lim X(k)= X*(目标函数极小点)满足此条件的下降迭代算法具有收敛性，称点列收敛于极小点X*。5.2.4 下降迭代法：v 优化迭代算法格式： X (k+1) = X (k) + a S(k)式中 S(k)搜索方向 a 步长因子 (2)格式：vX(k+1)取S(k)上的一维极

15、小点，对应于最优步长因子ak。(1)给定初始点 X(k) 和收敛精度e；(2)选取搜索方向S(k);(3)确定步长因子ak得到X(k+1);(4)收敛判断 X(k+1)满足收敛精度， X(k+1)作为最优点终止，否则重复(2)。故迭代算法的核心在于：v(1)确定搜索方向S(k) ;v(2)确定步长因子a；v(3)给定收敛准则。5.3 一 维 搜 索 法 v求解一维目标函数f(a)的极小点和极小值的数值迭代方法称为一维搜索方法。v从点X(k)出发，在方向S(k)上的一维搜索数学表达式： min f(X(k)+ a S(k) ) =f(X(k) +ak S(k) ) X(k+1)=X(k)+ ak

16、 S(k) X(k)akS(k)X(k+1)v一维优化目的是在既定的X(k)和S(k)下寻求最优步长a(k)使迭代产生新点X(k+1)的函数值最小。v一维优化一般分为两大步：(1).确定初始搜索区间a,b,该区间应是包括一维函数极小值点的单峰区间。(2).在搜索区间a,b内寻找极小点。v进退法思路： 由单峰函数性质可知，在极小点a*左边函数值应严格下降，在极小值点右边函数值应严格上升。由此，可以某一个给定的初始点x0出发，以初始步长h0沿着目标函数值下降方向，逐步前进(或后退)，直至找到相继的3个试点的函数值按大小大变化为止。5.3.1.确定搜索区间的方法：进退法进退法确定搜索区间的步骤如下：

17、(1)给定初始点x0和初始步长h；(2)令x1=x0 , x2=x1+h 得两试点x1，x2计算函数值 f1=f(x1) f2=f(x2);(3)比较f1和f2 ，存在两种情况：F f1 f2F f1f2若存在f1f2 ，取第3个试点x3=x2+h ，计算函数值 f3=f(x3)，比较f2 与f3 ：若f2 f3 ，则找到了x1，x2，x3的函数值按大小大变化的要求。故有搜索区间a, b= x1, x3；f3x1xf(x)0hhf2f1x3x2 若f2 f3，将步长加倍，令h=2h ，x1=x2 , x2=x3 , x3=x2+h ，如此重复该过程，总能找到相继3试点的函数值符合“大-小-大”

18、变化的要求。取左端点为a,右端点为b,从而找到搜索区间a, b。f3x1xf(x)0hhf2f1x3x22h 若f2 f3，将步长加倍，令h=2h ，x1=x2 , x2=x3 , x3=x2+h ，如此重复该过程，总能找到相继3试点的函数值符合“大-小-大”变化的要求。取左端点为a,右端点为b,从而找到搜索区间a, b。f3x1xf(x)0hhf2f1x3x22h若f2f1 作后退计算。令h=h,将x1，f1 与x2 ，f2 对调，并取第3个试点x3=x2+h ，计算其函数值f3= f(x3),比较对调后的f2 与f3 ：x1xf(x)0hf2f1x2f3hx3v若f2f3，a,b= x3,

19、 x1;v若f2 f3，将步长加倍，继续作后退运算，令h=2h，x1=x2, x2=x3, x3=x2+h，继续比较f2与f3，直到相继3个试点的函数值按“大-小-大”变化为止，相应的区间为x3, x1。f3x1xf(x)0hhf2f1x3x22h找到搜索区间后，便可运用一维优化算法在区间内找到极小点。例： 用进退法确定f(x)=x27x+10 的初始搜索区间。设初始点x0=0 ,初始步长h=1。解： x1=x0=0 f1= f(x1)=10 x2=x1+h=1 f2= f(x2)=4 比较f1 ，f2 ，因f2 f3 ,作前进运算 h=21=2 x1=x2=1 f1 = f2 =4 x2=x

20、3=2 f2 = f3=0 x3=x2+h=4 f3= f(x3) = 2 比较f2 ，f3 ，因f2 f3 ,作前进运算 h=22=4 x1=x2=2 f1 =f2=0 x2=x3=4 f2 =f3=2 x3=x2+h=8 f3=f(x3)=18 此时：x1, x2, x3 三点的函数值出现了大小的变化，故a=x1=2, b=x3=8 求得初始搜索区间a,b=2,8v是通过不断缩短搜索区间的长度来寻求一维函数f(x)的极小点。v原理是：在搜索区间a,b内取两点x1和x2 (x1 x2)： f(x1) f(x2)，极小点在x1和b间，消去区间a, x1，得到缩小后新区间x1,bv不断重复上述过

21、程，当区间长度baf2 。极小点必在区间x1 ,b内，消去区间a,x1,令a=x1，产生新区间x1,b，区间收缩了一次。新区间的x1点与原区间x2点重合，令x1=x2，f1=f2 ，这样可节省一次函数计算。ax1bf1f2x2 (2) 若f1f2。极小值点在区间a,x2内，消去区间x2,b，令b=x2产生新区间a,b，区间缩短一次。同时，新区间x2点与原区间的x1点重合，令x2=x1，f2 =f1。当缩短的新区间长度小于等于某一精度e，即bae 时取为近似极小点x*=(a+b)/2。ax1bx2f1f2L(1l)LlLabx1x2(1l)LLabx1x2lLLabx1x2(II) 黄金分割法的

22、区间收缩率lv每次缩小所得的新区间长度与缩小前区间长度之比，称为区间收缩率，以l表示。v黄金分割法收缩率保持不变，0.618v0.618n(ba)ev 解： (1)采用上节所求初始区间a,b=2,8取两计算点并计算出数值。 x1=a+0.382(ba)=4.292 f1= f(x1)=1.622736 x2=a+0.618(ba)=5.708 f2= f(x2)=2.625264 (2)比较函数值，缩短搜索区间 f1e不满足，继续缩短区间。 各次缩短区间有关计算数据如下表：abx1 x2f1f2ba0284.292 5.708 1.6227 2.6253 6125.708 3.416 4.29

23、2 2.24302 1.623 3.708 224.292 2.976 3.416 1.975 2.243 2.29232.975544 4.292 3.414 3.789 2.243 2.166 1.31642.975544 3.7891143.286 3.416 2.2043 2.243 0.813653.286328 3.789114 3.416 3.597 2.2430 2.241 0.502863.286328 3.59705 3.405 3.416 2.24098 2.243 0.3107(3)判断迭代终止条件 可见，区间缩短6次后： 区间长度为：ba=0.3107f2 加大步长向

24、前探测。令 x3=x0+2h=2 f3= f(x3)=18 f2f3，初始区间找到a,b=0,2。 (2) 用黄金分割法缩小区间 1) 第一次 x1=0+0.382(20)=0.764 f1=0.282 x2=0+0.618(20)=1.236 f2=2.72 由于f10.2 应继续缩小。 2) 第二次 x2=x1=0.764 f2 =f1=0.282 x1=0+0.382(1.2360)=0.472 f1=0.317 由于f1 f2 ， a,b=x1 ,b=0.472,1.236 ba=1.2360.472=0.7640.2 应继续缩小。3) 第三次 f1f2 x1=x2=0.764 f2

25、=f1=0.28 x2=0.472+0.618(1.2360.472)=0.944 f2=0.747 f10.2 4) 第四次 x2=x1=0.764 f2 =f1=0.282 x1=0.472+0.382(0.9440.472)=0.652 f1=0.223 f10.2 5 )第五次 x2=x1=0.652 f2 =f1=0.223 x1=0.472+0.382(0.7640.472)=0.584 f1=0.262 f1f2 故a,b=x1, b=0.584, 0.764 ba=0.7640.584=0.18f2 f2xpx2x1x3f pf 2x1fp f2(1)确定初始搜索区间a,b和精

26、度e； (2)在区间a,b内取3点：x1=a, x2=0.5(a+b), x3=b计算它们的函数值f1= f(x1), f2= f(x2), f3= f(x3)构成 3个插值点p1(x1, f1), p2(x2, f2)和p3(x3, f3)。(3)计算二次插值函数的极小值点xp，计算fp= f(xp)。若本步骤为第一次插值或x2点为初始给定点时，说明x2和xp不代表前后两次插值函数的极小点，不能进行终止判断，进行下一步；否则转(5)。(II)二次插值法的迭代过程(4)缩小搜索区间v比较f2 、fp ，取其小者所对应点为新的x2点，以此点左右邻点为新的x1 、x3 ，构成新的搜索x1, x3x

27、3xpx2x1f pf 2x2x3fpf2xpx2x1x3f pf 2x1x2fpf2(a)xpx2x1x3f pf 2x3fp f2xpx2x1x3f pf 2x1fp f2(b)(5)判断是否满足精度要求v|x2 xp |e , |f2 fp|e停止，取x2与xp 中原函数值较小的点作为极小点，否则返回(4)缩短区间直至满足要求。v例：用二次插值法求f(x)=x27x+10的最优解，已知初始区间为2, 8，取终止迭代点距精度e =0.01。 解: (1)确定初始插值结点 x1=a=2， f1= f(x1)=0 x3=b=8, f3= f(x3)=18 x2=4, f2= f(x2)=2 (

28、2) 计算插值函数极小点 xp=0.5(x1+ x3c1/c2)=3.5 fp= f(xp) =2.25 |xp x2|e (需要再次迭代)v(3)缩短搜索区间 由于f2 fp , xp x2 故x3=x2=5 f3 =2 x2=xp=3.5 f2=2.25 x1=2 f1=0 计算xp=3.5 fp=2.25 xp x2=0e x*= xp=3.5 f*= f(xp)=2.25 二次函数用二次插值，只需一次计算。v 收敛速度快，有效性好，程序复杂，可靠性差，适应于多值优化的一维搜索迭代。v例5.6 用二次插值法求解f(x)=3x34x+2的极小点，x0=0, h=1, e =0.2 解：(1

29、)初始区间0, 2，另取中点x2=1。 (2)用二次插值法逼近最小点。 x1=0, x2=1, x3=2 得： f1= 2, f2= 1, f3=18得 xp=0.555 fp=0.292 ：v fpf2 , xp0.2, 作二次插值。 在新的区间内: x1=0, x2=0.555, x3=1, f1= 2, f2=0.292, f3=1 将其代入得： xp=0.607 fp=0.243 fpx2 a, b=x2, b=0.555, 1 |x2xp| = |0.5550.607|=0.0520.2 故极小值和极小值点为： x*= xp=0.607 f*=0.243 二次插值的收敛速度比黄金分割

30、快得多。5.4 多 维 优 化 方 法v多维优化方法是进行多变量优化设计的数值迭代法，有无约束优化和约束优化两方面内容。v无约束优化方法可分为两类：利用目标函数的一阶和二阶导数的信息构造搜索方向的算法，称为导数法，如梯度法、共轭梯度法。另一类是通过已知点上函数值的比较构造搜索方向的算法，称为模式法，如Powell法 v约束优化方法分为直接法和间接法： 迭代过程逐点考察约束，使迭代点始终局限于可行域内的算法称为直接法，如可行方向法、复合形法等； 将约束条件引入目标函数，将约束优化问题转化为无约束问题求解的算法称为间接法，如惩罚函数法。5.4.1 梯 度 法 vI.基本原理v 在迭代过程的某一点X

31、(k)处，目标函数的负梯度方向f(X(k)是函数的最速下降方法，利用这一性质，将n维无约束极小化问题转化为一系列沿目标函数负梯度方向进行一维搜索寻优的一种方法，即是在每一迭代点X(k)，选取搜索方向S(k)为负梯度方向： S(k)=f(X(k)或)()()()()(kkkXfXfSv沿S(k)进行一维搜索，以确定步长因子a(k)，找到新的设计点X(k+1)=X(k)+a(k)S(k)v梯度法的迭代公式可写成：v X(k+1) = X(k)a(k) f(X(k)v 或v按照上述迭代公式进行一维搜索；每次迭代的初始点取上次迭代的终点，即可使迭代点逐步逼近目标函数极小点。)()()()()()()1

32、(kkkkkXfXfXXaII.梯度法的特点)0(X)1(X)2(X)3(X*X*x)()0(xf)0(x v每次沿迭代点函数值下降最快的方向搜索，称最速下降法。v缺点：曲折，收敛速度慢。v 对于圆一次可达。v 不是圆时，负梯度方向不指向圆心，迭代次数增加，偏心严重，迭代次数多，形成“锯齿现象”，开始步长大，愈接近极小点步长小，收敛慢。v优点：迭代过程简单，对初始点要求不高，只要计算导数，只求一阶，存储单元少。5.4.2 共 轭 梯 度 法 vI. 共轭方向的概念与性质v 设H为一正定对称矩阵，若有一组非零向量S1 , S2 , Sn满足：SiTHSj=0称这组向量关于矩阵H共轭。若H为单位阵

33、，SiTSj=0 (ij)称向量Si (i=1,2,n)正交。v X=x1 , x2T 任选初始点X(0)并沿梯度方向S(0)作一维搜索得： X(1)= X(0)+a0 S(0) X(1)的梯度与S(0)垂直，故： f(X(1)T S(0)=0 (1) 求式(1)点X(1)的梯度 f(X(1)=HX(1)+B 从X(1)沿某一下降方向S(1)作一维搜索，同理可得： X(2)= X(1)+a1S(1) f(X(2)=HX(2) +BCXBHXXxfTT21)(例v欲使X(2)成为极小点，则根据极值必要条件，有： f(X(2)=HX(2)+B=0 H(X(1)+a1S(1)+B=0 f(X(1)+

34、 a1HS(1)=0 上式左乘 S(0)Tf(X(1)+ a1S(0)T HS(1)=0 由a10得： S(0)T HS(1)=0 即要使迭代点X(2)成为正定二元二次函数的极小点，只需使两次一维搜索方向S(0)和S(1)关于函数的二阶导数矩阵H为共轭。v(1)若S(i) (i=1,2,n)是以H共轭的n个向量，则对于正定二次函数以任意初始点X(0)出发，依次沿n个方向进行一维搜索，最多n次即可达到极小点。 v(2)以任意两个点X1(0) 与X2(0)出发，沿同一方向S(0)进行一维搜索，可得到两个一维极小点X1(1)与X2(1) ，则两点构成向量v S(1)= X1(1) X2(1)与原方向

35、S(0)关于该函数的二阶导数共轭。 共轭方向性质：共轭方向性质：a0 S(0)X(1)S(1)a1S(1)f(X(1)S(1)S(0)X(0)v由X(k)出发，负梯度方向作一维搜索:v S(k) = f(X(k) v X(k+1) = X(k) + akS(k)v设与S(k)共轭的一个方向S(k+1)由S(k)和X(k+1)的负梯度方向的线性组合而成，故有：v S(k+1)=f(X(k+1)+ bkS(k) (3)令 f (X) = XTHX/2+BTX+C为函数的二次展开式。 II. 共轭梯度方向v则： f(X(k)=HX(k)+Bv f(X(k+1)=HX(k+1)+B （4）v相减代入

36、X(k+1)= X(k) + akS(k)，得：v akHS(k)= f(X(k+1)f(X(k)v 将(3)式与上式两边相乘，由共轭条件得：vf(X(k+1)+ bk f(X(k)Tf(X(k+1)f(X(k)=0v展开由相邻两点梯度的正交关系，整理得：v共轭梯度法迭代基本式v以相邻两点的梯度可以构造一个共轭方向。以这种方式产生共轭方向并进行迭代运算的算法称为共轭梯度法。2)(2)1()()()1()1()()()()()()(kkkTkkTkkXfXfXfXfXfXfb(1)( )( )2(1)2( )(1)(1)( )()()()kkkkkkkkkkkXXSf Xf XSf XSabb

37、v(1)给定初始点给定初始点X(0)和收敛精度和收敛精度e e。 v(2)取取X(0)的负梯度作为搜索方向的负梯度作为搜索方向S(0)= f(X(0)，置置k = 0。 v(3)沿方向沿方向S(k)作一维搜索得：作一维搜索得：v X(k+1)= X(k)+ a akS(k)v(4)收敛判断：若收敛判断：若 f(X(k+1)e e 则令：则令：v X*= X(k+1), f(X*)=f(X(k+1) v结束迭代；否则转结束迭代；否则转(5)。III. 共轭梯度法的迭代步骤(5)若若k+1=n(检验迭代次数，对于检验迭代次数，对于n值目标函数，值目标函数，理论上通过理论上通过n次可得最优点，由于计

38、算机舍入误次可得最优点，由于计算机舍入误差及目标函数性态的特殊性。往往迭代差及目标函数性态的特殊性。往往迭代n次达不次达不到精度要求。此时将到精度要求。此时将X(n)作为作为X(0)返回从第一步计返回从第一步计算，有助于消除累积计算误差的影响，并且对非算，有助于消除累积计算误差的影响，并且对非二次目标函数值保证具有良好的收敛性二次目标函数值保证具有良好的收敛性)，则令，则令X(0)= X(k+1)转转(2)，否则转，否则转(6)。v v S(k+1)= f(X(k+1)+b bkS(k)v 令令k=k+1 转转(3)。2)(2)1()()(kkkxfxfb(6)构造新的共轭构造新的共轭 例：用

39、共轭梯度法求解下列无约束优化问题X(0)=1,1T，e =0.1v min f(X)=x12 +2x22 2x1x2 4x1v解：2424422)()0(1221) 0(XxxxxXf24)()0()0(XfS aaa2141)0()0()0()1(SXXv第一次沿S(0)方向进行一维搜索，求近似极值点v代入f(X)=(1+4a(0)2+2(12a(0)22(1+4a(0)(12a(0)4(1+4a(0) v令df(a(0)/da(0)=0，得a(0)=0.25。v由此得：5 . 02)1(X2124422)()1(1221)1(XxxxxXf进行第二次搜索的共轭方向为：41205)()(2)

40、0(2)1(0 xfxfbv再沿S(1)方向进行一维搜索得：5 . 12244121)()0()0()1()1(SXfSb)1()1()1()1()1()1()2(5 . 15 . 0225 . 125 . 02aaaaSXXv代入f(x) ，令df(a(1)/da(1)=0，得a(1)=1 0024442)(24)2(1221)2()2(XxxxxXfXv因f(X(k+1)e， X(2)满足极值条件，X(2)是极小点， f(X*)=8v共轭梯度法两次迭代可求得二元二次优化问题极小点。5.4.3 鲍鲍 威威 尔尔 法法v 两次平行搜索产生一个共轭方向，Powell法就是利用平行搜索逐渐构造共轭

41、方向和共轭方向组的方法，能在有限步长内极小化一个二次函数，是直接搜索方法中使用效果最佳的一种方法。对于维数n20的目标函数求最优化问题。此法可获得满意效果。v 原始的Powell法是沿着逐步产生的共轭方向进行一维搜索的。v 以二维二次目标函数为例来说明。选定初始点X0(1)，初始方向e(0)=1,0T, e(1)= 0,1T，从X0(0)出发依次沿e(0)、e(1)进行一维搜索，求得各自方向上的极值点X0(1)，X0(2)，连接点X0(0)和最后一个极值点X0(2) ，构成第三个新方向： S(0)= X0(2)X0(0)I.基本迭代格式、原理：S(1)S(0)e(1)S(0)e(1)e(0)x

42、1x2X0(1)X0(2)X0(3)X1(0)X1(1)X1(2)X1(3)X0(0)vS(0)称为模式方向称为模式方向，再沿，再沿S(0)方向进行一维搜方向进行一维搜索得该方向上的近似极值点索得该方向上的近似极值点X0(3) ，搜索过程，搜索过程就完成了一个循环。就完成了一个循环。v以第一循环迭代的终点以第一循环迭代的终点X0(3)作为第二循环迭作为第二循环迭代的起点代的起点X1(0) ，弃去上一个循环向量组中的弃去上一个循环向量组中的第一个方向第一个方向e(0)，将新方向，将新方向S(0)补在最后，构成补在最后，构成第二个循环的搜索方向组第二个循环的搜索方向组e(1), S(0)。v分别沿

43、分别沿e(1), S(0)一维搜索一维搜索求得近似极值点求得近似极值点X1(1), X1(2) ，连接连接X1(0)与与X1(2)，构成第二个循环的一个新方向：，构成第二个循环的一个新方向： S(1)= X1(2)X1(0)v沿沿S(1) 方向作一维搜索所得的近似极值点方向作一维搜索所得的近似极值点X1(3)即为即为第二循环的最终迭代点，也是下一次迭代的起始点。第二循环的最终迭代点，也是下一次迭代的起始点。由由图可知点图可知点X0(3)(X1(0)，X1(2)是先后两次沿是先后两次沿S(0)方向方向一维搜索的极小点。由共轭性质知：连接一维搜索的极小点。由共轭性质知：连接X1(0) ，X1(2)

44、构成的矢量构成的矢量S(1) 与与S(0)相共轭。相共轭。v 经过二次循环后，迭代点由初始点经过二次循环后，迭代点由初始点X0(0)依依次沿次沿S(0) ，S(1)方向一维搜索，经方向一维搜索，经X0(3)(X1(0)到到达达X1(3) ，从理论上讲，二维二次正定函数经，从理论上讲，二维二次正定函数经过这组共轭方向的一维搜索，迭代点已达到过这组共轭方向的一维搜索，迭代点已达到函数的极小点函数的极小点X*。将此结构推广至。将此结构推广至n维二次正维二次正定函数，即依次沿定函数，即依次沿n个个(S(0) ，S(1)，S(n1)共轭方向一维搜索就能达到极小点。共轭方向一维搜索就能达到极小点。Pk:e

45、(k)e(k+1)e(k+2)e(n-1)S(0)S(0)S(k-1)Pk+1: e(k+1)e(k+2)e(n-1)S(0)S(0)S(k-1)S(k)e(1)e(2)e(3)X0(2)X0(0)X0(1)X0(3)S(0)e(1)e(2)e(3)X0(2)X0(0)X0(1)X0(3)S(0)退化原始Powell法存在的问题：v 目前使用目前使用修正算法修正算法，和原始，和原始Powell法的法的主要区别：主要区别：在构成第在构成第k+1次循环方向组时，不用淘汰前一循环中次循环方向组时，不用淘汰前一循环中的第一个方向的第一个方向S1(k)的办法，而是首先解决是否要替换的办法，而是首先解决是

46、否要替换和替换哪个方向的问题。和替换哪个方向的问题。v为此，在得到新方向为此，在得到新方向v Sk(n)= Xk(n)Xk(0) 后后v沿沿Sk(n)找出找出Xk(0) 的的反射点反射点Xk(n+2)： Xk(n+2)=2Xk(n) Xk(0)Xk(0)f3D2Xk(1)Xk(n)Xk(n+2)f2f1x1Sk(n)x2D1v计算三点的函数值：计算三点的函数值：f1=f(Xk(0)；f2=f(Xk(n)；f3=f(Xk(n+2)v找出前一轮迭代法中找出前一轮迭代法中函数值下降最多的方向函数值下降最多的方向m及及下降下降量量m，即：即： vm = max f(Xk(i) f(Xk(i+1) =

47、f(Xk(m1) f(Xk(m)v可以证明：若可以证明：若 f3f1 与与 (f12f2+f3)(f1f2m)20.5m(f1f3)2同时成立。同时成立。则表明方向则表明方向Sk(n)与原方向组成线性无关，与原方向组成线性无关，可可以用来替换以用来替换。替换对象就是替换对象就是m所对应的方向所对应的方向Sk(m)。Xk(0)f3D2Xk(1)Xk(n)Xk(n+2)f2f1x1Sk(n)x2D1Pk:Sk(0)Sk(1)Sk(m-1)Sk(m)Sk(m+1)Sk(n-1)Pk+1:Sk+1(0)Sk+1(1)Sk+1(m-1)Sk+1(m)Sk+1(n-2)Sk(n)v替换算式替换算式: Sk

48、+1(i)= Sk(i) (im) Sk+1(i-1)= Sk(i) (i=m+1, m+2, n-1,) Sk+1(n-1)= Sk(n)v新一轮迭代起点：新一轮迭代起点： Xk+1(0) = Xk(n+1)Sk+1(n-1)Xk(0)f3D2Xk(1)Xk(n)Xk(n+1)Xk(n+2)f2f1X1Sk(n)X2D1v上述两个条件上述两个条件不不成立，则表明与原方向组中某些方成立，则表明与原方向组中某些方向线性相关，因此向线性相关，因此不不进行方向替换。此时仍用原方进行方向替换。此时仍用原方向组进行第向组进行第k+1轮搜索。轮搜索。v Sk+1(i)= Sk(i) (i=0, 1, n-

49、1,)v第第k+1轮搜索初始点的取法？轮搜索初始点的取法？ 若若 f2f3，Xk+1(0) = Xk(n)； 否则，否则，Xk+1(0) = Xk(n+2)；v步骤：步骤：P177页页Xk(0)f3D2Xk(1)Xk(n)Xk(n+2)f2f1X1Sk(n)X2D1v例：试用Powell法求f(X)=x12+2x22 4x1 2x1x2的最优解。X0=1,1T ,收敛精度e =0.05。 110111) 0(0) 0(0) 0() 0(0) 0(0) 1 (0aaaeXX110)0(0XXv解： f1=f(X0(0)=3 v第一次循环：沿坐标轴方向e(0)进行一维搜索：v代入f(X), f(X

50、)=(1+a0(0)2+24(1+a0(0)2(1+a0(0)v令df(X)/da0(0)=0，得a0(0)=2 则有 v f(X0(1)=713)1(0X1013) 1 (0) 1 () 1 (0) 1 (0)2(0aaeXXv以X0(1)为起点，沿坐标轴方向e(1)进行一维搜索：v代入f(X)， f(X)=32+2(1+a0(1)24323(1+a0(1)v令df(X)/da0(1)=0,得a0(1)=0.5, 则有5 . 13)2(0Xf(X0(2)=7.5F计算各个方向的函数下降量： 1= f(X0(0) f(X0(1)=3(7)=4 2= f(X0(1) f(X0(2)=7(7.5)

51、=0.5 m=max1, 2=1=425115 . 1322)0(0)2(0)4(0XXX映射点：f1=f(X0(0)=3;f2=f(X0(2)=7.5f3=f(X0(4)=7;v检验是否满足终止迭代条件替换条件：f3 f1; (f12f2+f3)(f1f2m)2=1.25f1, 替换条件不成立，继续迭代时取搜索方向仍为原方向e(1), S(0)。由于f2 f3，取X2(0)=X1(2)=3.96, 1.94T 以X2(0)为新起点，方向 e(1), S(0)，进行第三循环迭代。 f(X2(0)=7.996=f198. 196. 3)1(2X沿e(1)方向进行一维搜索，得以X2(1)为起点沿S

52、(0)方向进行搜索，得988. 19992. 3)2(2X9997. 7)()2(22Xffe0620. 0)0(2)2(2XX收敛判定：不收敛，继续迭代。f(X2(1)=7.9992036. 20384. 42)0(2)2(2)4(2XXX996. 7;9987. 7)(13)4(2ffXf映射点： 1= f(X2(0) f(X2(1)=7.996(7.9992)=0.00322= f(X2(1) f(X2(2)=7.9992(7.9997)=0.0005m=max1, 2=1=0.0032判断搜索方向是否替换： f3f1(f12f2+f3)(f1f2m)2=1.17510-90时，设计点违时，设计点违反了约束，在目标函