最优化方法复习

1、第1章最优化冋题的基本概念.1最优化的概念最优化就是依据最优化原理和方法，在满足相关要求的前提下，以尽可能高的效率 求得工程问题最优解决方案的过程。1.2最优化问题的数学模型1. 最优化问题的一般形式f i n dx1,X2,Xnm i nf (X1,X2,Xn)s.t. gu(X1,X2,，Xn) 0 u =1,2,p hv(X1,X2,，Xn) =0 v=1,2，q2. 最优化问题的向量表达式? i n d Xm i nf(X)s.t. G(X) 0，使得 YX 己 N(X*P)c D(X HX*)都有 f(X*) f(X)，则称 X* 为 f (X)的局部 极小点；若f(X*)f(X),

2、则称X*为f(X)的严格局部极小点。, , * * *若VX D，都有f(X ) f(X)，则称X为f(X)的全局极小点，若f (X ) f (X)， 则称X*为f(X)的全局严格极小点。find X对最优化问题n f (X)而言st. G(X) 0H(X)=0满足所有约束条件的向量X =Xi，X2，XnT称为上述最优化问题的一个可行解，全 体可行解组成的集合称为可行解集。在可行解集中，满足：f(X*) =mi nf(X)的解称为优化问题的最优解。2.凸集和凸函数凸集：设D匸Rn，若对所有的X1、X2迂D，及a C 0,1，都有aX1 +(1a)X2壬D，则称D为凸集。凸函数：设f : D U

3、 RnT R1，D是凸集，如果对于所有的X1、X2壬D，及a 0,1，都有 fktX(a)X2Uaf(X1H(a)f(X2),则称 f(X)为 D 上的凸函数。、局部极小点的判别条件驻点：设f(X)是定义在n维空间Rn的子集D上的n元实值函数，X是D的内点， 若7 f(X*) =0，则称X*为f(X)的驻点。局部极小点的判别：设f(X)是定义在n维空间Rn的子集D上的n元实值函数，具 有连续的二阶偏导数。若X*是f (X)的驻点，且V2f(X*)是正定矩阵，则X*是f(X)的 严格局部极小点。三、全局极小点的判别1.凸规划对于优化问题：盯叢爲.1.-,p若f(X)、gi(X)都是凸函数，贝U称

4、该优化问题为凸规划。2.全局极小点的判别若优化问题为凸规划，贝U该优化问题的可行集为凸集，其任何局部最优解都是全局 最优解。(能否证明)第3章无约束优化方法3.1下降迭代算法及终止准则一、数值优化方法的基本思想方向的确定原则是使函数值下降）前进一定的步长 降的新设计点Xk半，然后以该点为新的初始点， 的最优点X* 0基本思想就是在设计空间内选定一个初始点Xk，从该点出发，按照某一方向S（该 a k，得到一个使目标函数值有所下 重复上面过程，直至得到满足精度要求该思想可用下式表示：Xk=Xk+akSk、迭代计算的终止准则工程中常用的迭代终止准则有3种:点距准则相邻两次迭代点之间的距离充分小时，迭

5、代终止。 数学表达为：Xk*-Xk|8函数下降量准则（值差准则）相邻两次迭代点的函数值之差充分小，迭代终止。 数学表达为：f(x5)- f (Xk) 梯度准则目标函数在迭代点处的梯度模充分小时，迭代终止。 数学表达为：Vf(Xk*) 0及L、ko，使当k k。时下式:|xk X*| ko时下式:|xk+-X*|kLTk成立，则称&k 为线性收敛。3.超线性收敛设序列k 收敛于解X*，若任给P 0都存在ko 0，使当k ko时下式:|xM-x*卜 P|xk x*|成立，则称&k 为超线性收敛。3.2 一维最优化方法一、确定初始区间的进退法任选一个初始点x0和初始步长h，由此可确定两点Xj = x

6、0和X2 =为+ h，通过比较 这两点函数值f(xi)、f (X2)的大小，来决定第三点X3的位置。比较这三点函数值是否 呈“高一一低一一高”排列特征，若是则找到了单峰区间，否则向前或后退继续寻求下 一点。进退法依据的基本公式:Xj =X0X3 =X2 +h具体步骤为：任意选取初始点Xo和恰当的初始步长h ；f(Xi)、X2右侧,f(X2)；应加大步长向前搜索。转;令 为=x0，取X2 = x1 + h，计算若f(Xi)f(X2),说明极小点在若f(Xi) C f(X2)，说明极小点在X1左侧,应以Xi点为基准反向小步搜索。转;高”排列，说明Xi, X3大步向前搜索：令h= 2h，取XXh，计

7、算f(x3)； 若 f(X2) f(X3),说明极小点在X3右侧，应加大步长向前搜索。此时要注意做变 换：舍弃原X1点，以原X2点为新的X1点，原X3点为新的X2点。转，直至出现“高一 低一一高”排列，则单峰区间可得；反向小步搜索(要注意做变换)：为了保证X3点计算公式的一致性，做变换：将 原x2点记为新xi点，原xi点记为新x2点，令h U -丄h，取X3 = X2 + h，转41。例：用进退法确定函数f(x)=x2-6x+9的单峰区间a，b,设初始点X0=O, h =解：寫X0 =0 h =1；.Xj =x0 =0X2 =*4 +h =1 f (xj =9 f (x2)= 4寫 f(Xi)

8、f(X2)说明极小点在X2点右侧，应加大步长向前搜索令 hu 2h =2咒1 =2，取 x3 =X2 +h =1 +2=3则 f(X3)=0常 f(X2)A f(X3)说明极小点在X3点右侧，应加大步长向前搜索舍弃原x1 =0的点，令Xj = 1 X2 = 3，则f (x1)=4 f(X2)= 0令 hu2h=2%2=4，取 x3=X2+h=3+4 = 7则 f(X3)=16 A f(X2)=0、f(X2)、f(X3)呈“高一一低一一高”排列/.Xi,X3为单峰区间，即区间1，7即为所求、黄金分割法黄金分割法是基于区间消去思想的一维搜索方法，其搜索过程必须遵循以下的原则：对称取点的原则：即所插

9、入的两点在区间内位置对称；插入点继承的原则：即插入的两点中有一个是上次缩减区间时的插入点;等比收缩的原则：即每一次区间消去后，单峰区间的收缩率A保持不变。设初始区间为a，b，则插入点的计算公式为:x1 =a +0.382(b-a)X2 =a +0.618(b a)黄金分割法的计算步骤如下： 给定初始区间a，b和收敛精度名; 给出中间插值点并计算其函数值：Xj =a+0.382(ba)f (X1)X2 = a+0.618(b-a) f (x2).?比较f(Xi)、f(x2)，确定保留区间得到新的单峰区间a, b；收敛性判别：计算区间a, b长度并与s比较，若b-a s ;继承原 x1 点，即 X

10、2 =0.056 f(X2)=0.115插入 xa +0.382(b -a) = 3 +0.382x(1.944 + 3) = 1.111 f (xj = -0.987V f(X2) f (xj舍弃(0.056 , 1.944，保留-3 , 0.0560.056-(3)名;继承原 X1 点，即 X2=1.111f(X2)=0.987插入 为=a +0.382(b -a) = -3+0.382 咒(0.056 +3) = -1.832f (x1H -0.306V f(x2 f (x1)保留-1.832 ,0.0560.056(1.832) s ;继承原 X2 点，即 X1=-1.111f(X1)

11、=-0.987插入 X2 = -1.832 +0.618x(0.056 +1.832) = -0.665f (x2H -0.888 f(X2) f(X1)保留-1.832 , -0.665如此迭代，到第8次，保留区为-1.111,-0.940_0.940 -(1.111) =0.171 8 X* 二丄咒匸行“ +0.940) = -1.0255f(x*) =0.99923.3梯度法、基本思想对于迭代式Xk=Xk+akSk，当取搜索方向Sk =Xf(Xk)时构成的寻优算法，称 为求解无约束优化问题的梯度法。、迭代步骤给定出发点xk和收敛精度计算Xk点的梯度F(Xk)，并构造搜索方向S-VF(Xk

12、)；令X心=xk乜kSk，通过一维搜索确定步长ak，即: L /k . k k .min F (X S )2成立，输出X* =Xk*、F(X*) =F(X心)，寻优结求得新点收敛判断：若IVF(Xk)|束；否则令k= k+1转继续迭代，直到满足收敛精度要求。三、梯度法的特点梯度法寻优效率受目标函数性态影响较大。若目标函数等值线为圆，则一轮搜索就 可找到极致点；若当目标函数等值线为扁椭圆时，收敛速度则显著下降。梯度法中相邻两轮搜索方向相互垂直。(是否会证明) 3.4牛顿法牛顿法分为基本牛顿法和阻尼牛顿法两种。= -2f(xk)-Vf(xk)时对于迭代式xk+ = xk +ksk，当取k三1且搜索

13、方向Sk构成的寻优算法，称为求解无约束优化问题的基本牛顿法；对于迭代式XkP=Xk+akSk，取搜索方向Sk =-W2f(Xk)d可f(Xk)，k为从xk出发、沿牛顿方向做一维搜索获得的最优步长，所构成的寻优算法，称为求解无约束优 化问题的阻尼牛顿法。搜索方向Sk =TV2f(xk)dVf(xk)称为牛顿方向。这里需要注意的是会求海塞阵的逆矩阵。3.5变尺度法我们把具有Xk屮=Xk-akAf(Xk)迭代模式的寻优算法称为变尺度法。2其搜索方向表达式为:在迭代开始的时候,sk = Apf(xk)，称为拟牛顿方向，其中Ak称为变尺度矩阵。A0=l ;随着迭代过程的继续，AkT J于f(Xk)L叭(

14、Xk)。因此，变尺度法从梯度法出发，随着迭代过程的继续最终趋向于牛顿法。3.6共轭梯度法一、共轭方向的概念设H为对称正定矩阵，若有两个n维向量S1和S2,满足SiTS2 = 0 ,则称向量S与S关于矩阵H共轭，共轭向量的方向称为共轭方向。若有一组非零向量Si，S2，Sn满足ST H ”Sj =0(i工j)，则称这组向量关于 矩阵H共轭。对于n元正定二次函数，依次沿着一组共轭方向进行一维搜索，最多n次即可得到极值点。、共轭方向的形成1对于函数 f(X f(x1,x2 ,xn) =-XThX +bTx +C2沿任意方向S0在设计空间上任意做两条平行线，分别与目标函数等值线切于点 X1、X2，令S1

15、 = x2 -X1，则S0、S1关于矩阵H共轭。(能否给出证明)三、共轭梯度法对于迭代式Xk+ = xk +aksk，取搜索方向Sk+ =Xf(Xk+) + PkSk其中：s0=Xf(X0)，Pk =可(Xk + ) Ff(xk)共轭梯度法相邻两轮搜索方向是一对共轭方向。3.7鲍威尔法基本迭代公式仍旧是：xk十=X k +aksk基本鲍威尔法每轮搜索分为两步：一环的搜索 +在该环搜索完毕后生成的新方向上的一维搜索。对于基本鲍威尔法，相邻两轮搜索生成的搜索方向是共轭的。修正鲍威尔法与基本鲍威尔法类似，所不同的是每环搜索后生成的新方向要利用鲍 威尔条件判别其可用性。注意掌握鲍威尔条件的表达式和应用

16、!每环搜索方向组的生成:1第一环的搜索方向组就是各坐标轴方向2 .下一环的搜索方向组由本环搜索方向组和本环生成的新方向共同确定，方法是： 若本环的搜索结果满足鲍威尔条件， 则将本环搜索方向组中使目标函数下降量最大的方 向去掉，并将本环生成的新方向递补进去，就形成下一环的搜索方向组；若本环的搜索 结果不满足鲍威尔条件，则下一环的搜索方向组仍旧沿用本环搜索方向组不变。下一环搜索起点的确定:下一环搜索起点由本环搜索结果确定，方法是：若本环的搜索结果满足鲍威尔条件, 则以本环搜索终点为起点，沿新生成的方向作一维搜索，得到的新点作为本轮的搜索终点，也是下一轮的搜索起点；若本环的搜索结果不满足鲍威尔条件，

17、则取本环搜索终点 和反射点中目标函数值小的点作为本轮的搜索终点，也是下一轮的搜索起点。这里需要注意的是反射点的计算：X爲=2Xnk -Xok式中：Xk七是本环起点Xok相对于本环终点Xk沿新生成方向的反射点。例:对于无约束目标函数 minf (X)+2x2 -4xi -2xX2，利用修正 Powell 法从X0=出发求最优解。解:令 x0=x0 _1 _ 0p= P=(e,e2)X； =x0 乜0令 f (xl) -。得：a =2则：xl=【3令 f X 2)=0 得：a = 0.5 贝U: x21h5该环生成的新搜索方向为：S1 = x2-x(1435引尤对s1进行有效性判别:反射点X1 =

18、2X2 -x0-*1511.512f1 =f(x0)=3f2= f(x2) = 7.5f3 = f(x4)=7Ai = faOlfMi1)二3 (7) =4，也 2 = f (Xi1) - f(x2) =7-(7.5) =0.5故最大下降量im =d =4故：f3f1 和(f1-2f2+f3)(f1-f2m)2m(f1-f3)2 均成立方向S1可用以x2为起点，沿S1方向作一维搜索:x3 =x2 + J31+订2 13 21.5卜丄3 + 2 I0.51.5 + 0.50由 min f(x3)= f(X2 + aS1)得=2/5 =0.4故，本轮寻优的终点为：X1 = x3 =；.；做收敛性判别：=丿2.82 +0.72，应继续搜索x x0下一轮寻优过程的起点为：x2 - x3 = F8!L1.7下一轮寻优过程的搜索方向组为：2, S1) 继续依样搜索直至满足收敛精度解：构造惩罚函数*(X,rk)(X,rki ；:台+X2k-2X, +1+r (3-X2)-2% +1令旦cx1=2捲-2 =0cx1= 2x2