整理最优化方法复习

1、第1章最优化问题的根本概念1.1 最优化的概念最优化就是依据最优化原理和方法,在满足相关要求的前提下,以尽可能高的效率求得工程问题最优解决方案的过程.1.2 最优化问题的数学模型1 .最优化问题的一般形式阡indxLXnminf(x,X2,Xn)s.t.gu(X1,X2,Xn)-0u=1,2,p儿国国,Xn)=0v-1,2,q2 .最优化问题的向量表达式?indXminf(X)s.t.G(X)0,使得VX=N(X,6)CD(X#X)都有f(X)f(X),那么称X为f(X)的局部极小点;假设f(X*)f(X),那么称X*为f(X)的严格局部极小点.假设VXwD,都有f(X*)wf(X),那么称X

2、*为f(X)的全局极小点,假设f(X*)f(X),那么称X*为f(X)的全局严格极小点.findX口八、八、口工minf(X)一对取优化问题(而百st.G(X)0H(X)=0满足所有约束条件的向量X=xX2,*称为上述最优化问题的一个可行解,全体可行解组成的集合称为可行解集.在可行解集中,满足：f(X)=minf(X)的解称为优化问题的最优解.2.凸集和凸函数凸集：设DuRn,假设对所有的X1、X2wD,及口w0,1,都有uX1+(1o()X2wD,那么称D为凸集.凸函数：设f:DuRnTR1,D是凸集,如果对于所有的X1、X2wD,及aw0,1,都有f/X1+(1-a)X2af(X1)+(1

3、-a)f(X2),那么称f(X)为D上的凸函数.二、局部极小点的判别条件驻点：设f(X)是定义在n维空间Rn的子集D上的n元实值函数,X*是D的内点,假设Vf(X*)=0,那么称X*为f(X)的驻点.局部极小点的判别：设f(X)是定义在n维空间Rn的子集D上的n元实值函数,具有连续的二阶偏导数.假设X是f(X)的驻点,且V2f(X)是正定矩阵,那么X是f(X)的严格局部极小点.三、全局极小点的判别1.凸规划对于优化问题:minf(X)s.t.gi(X)0i=1,2,p假设f(X)、g/X)都是凸函数,那么称该优化问题为凸规划.2.全局极小点的判别假设优化问题为凸规划,那么该优化问题的可行集为凸

4、集,其任何局部最优解都是全局最优解.(能否证实)第3章无约束优化方法3.1 下降迭代算法及终止准那么一、数值优化方法的根本思想根本思想就是在设计空间内选定一个初始点Xk,从该点出发,根据某一方向Sk(该方向确实定原那么是使函数值下降)前进一定的步长k,得到一个使目标函数值有所下降的新设计点Xk书,然后以该点为新的初始点,重复上面过程,直至得到满足精度要求的最优点X*.该思想可用下式表示：Xk1=XkkSk二、迭代计算的终止准那么工程中常用的迭代终止准那么有3种：点距准那么相邻两次迭代点之间的距离充分小时,迭代终止.数学表达为：Xk1-xk:函数下降量准那么(值差准那么)相邻两次迭代点的函数值之

5、差充分小,迭代终止.数学表达为：|f(Xk*)-f(Xk)|金梯度准那么目标函数在迭代点处的梯度模充分小时,迭代终止.数学表达为：|Bf(Xk*)|ww三、算法的收敛速度对于某一确定的下降算法,其优劣如何评价人们通常采用收敛速度来评价.下面给出度量收敛速度的几个概念.1 .P阶收敛设序列kk收敛于解X*,假设存在常数P圭0及L、k0,使当k之k0时下式：Xk1-X*LXk-Xip成立,那么称xk为P阶收敛.2 .线性收敛设序列Kk收敛于解X*,假设存在常数k.、L及ew(0,1),使当k之ko时下式：Xk1-X*|0都存在k00,使当k2k0时下式：Xk1-X*-Xk-X*成立,那么称为超线性

6、收敛.3.2 一维最优化方法一、确定初始区间的进退法任选一个初始点x0和初始步长h,由此可确定两点x1=x0和x2=x1+h,通过比拟这两点函数值f(xj、f(x2)的大小,来决定第三点x3的位置.比拟这三点函数值是否呈“高一一低一一高排列特征,假设是那么找到了单峰区问,否那么向前或后退继续寻求下一点.进退法依据的根本公式：xi=x0x2=x1hx3=x2h具体步骤为：任意选取初始点x0和恰当的初始步长h；令x1=x0,取x2=x1+h,计算f(x1)、f(x2);假设f(x1)之f(x2),说明极小点在x2右侧,应加大步长向前搜索.转；假设f(x1)f(x2),说明极小点在X左侧,应以X点为

7、基准反向小步搜索.转；大步向前搜索：令hu2h,取x3=x2+h,计算f(x3);假设f(x2)f(x2)=0f(xi)、f(x2)、f(x3)呈“高一一低一一高排列,X1,X3为单峰区间,即区间1,7即为所求二、黄金分割法黄金分割法是基于区间消去思想的一维搜索方法,其搜索过程必须遵循以下的原那么：对称取点的原那么：即所插入的两点在区间内位置对称；插入点继承的原那么：即插入的两点中有一个是上次缩减区间时的插入点；等比收缩的原那么：即每一次区间消去后,单峰区间的收缩率九保持不变.设初始区间为a,b,那么插入点的计算公式为：x1=a0.382(b-a)x2=a0.618(b-a)黄金分割法的计算步

8、骤如下：给定初始区间a,b和收敛精度注；给出中间插值点并计算其函数值：x1=a0.382(b-a)f(x1)x2=a0.618(b-a)f(x2).比拟f(x1)、f(x2),确定保存区间得到新的单峰区间a,b;收敛性判别：计算区间a,b长度并与名比拟,假设b-aW名,输出x*=1(a+b)2否那么转；在保存区间内继承一点、插入一点,转.例：使用黄金分割法求解优化问题：minf(x)=x2+2x,-3xf(xi).舍弃(1.944,5,保存-3,1.9441.944(3)?名；继承原x1点,即x2=0.056f(x2)=0.115插入x=a0.382(b-a)=-30.382(1.9443)=

9、-1.111f(x1)=-0.987.f(x2)f(xi).舍弃(0.056,1.944,保存-3,0.0560.056(3)；继承原Xi点,即X2=1.111f(X2)=0.987插入x1=a0.382(ba)=30.382(0.0563)二1.832f(x1)二一0.306f(x2);继承原x2点,gpx1=-1.111f(x1)=-0.987插入x2-1.8320.618(0.0561.832)-0.665f(x2)-0.888.f(x2)f(x1)保存-1.832,-0.665如此迭代,到第8次,保存区为-1.111,-0.9400.940(1.111)=0.171名d.x=1(-1.

10、1110.940)-1.0255f(x)=-0.99923.3 梯度法一、根本思想对于迭代式Xk+=Xk+skSk,当取搜索方向Sk=-f(Xk)时构成的寻优算法,称为求解无约束优化问题的梯度法.二、迭代步骤给定出发点Xk和收敛精度名；计算Xk点的梯度VF(Xk),并构造搜索方向Sk=-F(Xk);令Xk书=Xk十akSk,通过一维搜索确定步长口;即：minF(Xk二kSk)求得新点Xk1收敛判断：假设|pF(Xkw名成立,输出X*=XkTF(X*)=F(Xk41),寻优结束；否那么令kuk+1转继续迭代,直到满足收敛精度要求.三、梯度法的特点梯度法寻优效率受目标函数性态影响较大.假设目标函数

11、等值线为圆,那么一轮搜索就可找到极致点；假设当目标函数等值线为扁椭圆时,收敛速度那么显著下降.梯度法中相邻两轮搜索方向相互垂直.(是否会证实)3.4 牛顿法牛顿法分为根本牛顿法和阻尼牛顿法两种.对于迭代式Xk44=Xk+akSk,当取k三1且搜索方向Sk=-V2f(Xk)Vf(Xk)时构成的寻优算法,称为求解无约束优化问题的根本牛顿法；对于迭代式Xk41=Xk+skSk,取搜索方向Sk=-W2f(Xk)Vf(Xk),.为从Xk出发、沿牛顿方向做一维搜索获得的最优步长,所构成的寻优算法,称为求解无约束优化问题的阻尼牛顿法.搜索方向Sk=v2f(Xk)vf(Xk)称为牛顿方向.这里需要注意的是会求

12、海塞阵的逆矩阵.3.5 变尺度法我们把具有Xk41=Xk-akAkVf(Xk)迭代模式的寻优算法称为变尺度法.其搜索方向表达式为：Sk=-Af(Xk),称为拟牛顿方向,其中Ak称为变尺度矩阵.在迭代开始的时候,A=I;随着迭代过程的继续,AkT-V2f(Xk),Vf(Xk).因此,变尺度法从梯度法出发,随着迭代过程的继续最终趋向于牛顿法.3.6 共腕梯度法一、共腕方向的概念设H为对称正定矩阵,假设有两个n维向量和S2,满足S；旧$2=0,那么称向量S1与&关于矩阵H共腕,共腕向量的方向称为共腕方向.假设有一组非零向量Si,S2,Sn满足STH=0(i0j),那么称这组向量关于矩阵H共腕.对于n

13、元正定二次函数,依次沿着一组共腕方向进行一维搜索,最多n次即可得到极值点.二、共腕方向的形成1对于函数f(X)-f(x1,x2,xn)=-XtHXBtXC沿任意方向S0在设计空间上任意做两条平行线,分别与目标函数等值线切于点XX；=X；I、X2,令S1=X2-X1,那么S、S1关于矩阵H共腕.(能否给出证实)三、共腕梯度法对于迭代式Xk+=Xk+akSk,取搜索方向Sk*=-Wf(Xk由)十PkSk其中：S=-Vf(X0),久=忸9)Llf(Xk)|共腕梯度法相邻两轮搜索方向是一对共腕方向3.7 鲍威尔法根本迭代公式仍旧是：Xk1=XkkSk根本鲍威尔法每轮搜索分为两步：一环的搜索+在该环搜索

14、完毕后生成的新方向上的一维搜索.对于根本鲍威尔法,相邻两轮搜索生成的搜索方向是共腕的.修正鲍威尔法与根本鲍威尔法类似,所不同的是每环搜索后生成的新方向要利用鲍威尔条件判别其可用性.注意掌握鲍威尔条件的表达式和应用!每环搜索方向组的生成：1 .第一环的搜索方向组就是各坐标轴方向2.下一环的搜索方向组由本环搜索方向组和本环生成的新方向共同确定,方法是：假设本环的搜索结果满足鲍威尔条件,那么将本环搜索方向组中使目标函数下降量最大的方向去掉,并将本环生成的新方向递补进去,就形成下一环的搜索方向组；假设本环的搜索结果不满足鲍威尔条件,那么下一环的搜索方向组仍旧沿用本环搜索方向组不变.下一环搜索起点确实定

15、：下一环搜索起点由本环搜索结果确定,方法是：假设本环的搜索结果满足鲍威尔条件,那么以本环搜索终点为起点,沿新生成的方向作一维搜索,得到的新点作为本轮的搜索终点,也是下一轮的搜索起点；假设本环的搜索结果不满足鲍威尔条件,那么取本环搜索终点和反射点中目标函数值小的点作为本轮的搜索终点,也是下一轮的搜索起点.这里需要注意的是反射点的计算：X：.2=2X；-X0k式中：XL是本环起点X0k相对于本环终点X：沿新生成方向的反射点.例:对于无约束目标函数minf(X)=x1*2+2x24x1-2x1x2,利用修正Powell法从X01一=|出发求最优解解:令X0-X0=P0=(e,e2)令f(X；)=0得

16、：=2那么：X；XiX0L；3-iX2=Xlij+a令f(X；)=0得：a=0.5那么：X；=,31151该环生成的新搜索方向为：s1=X2-x0=3L1：1211.51忖句对S1进行有效性判别：反射点X：=2X2-X0=23-1.5一1.5_12f1=f(x0)=3f2=f(x2)=7.5f3=f(X：)=70.5.11._.114=f(X.)f(X1)=3(7)=4,2=f(X1)-f(X2)=-7-(-7.5)故最大下降量；：m-=4212r故：f3f1和(f1-2f2+f3)(f1f2-Am)2-Am(f1fs)2均成立2方向S1可用以x2为起点,沿s1方向作一维搜索:11_1X3=X

17、2+US；31；2113+密+Gt=1.5一0.5一11.5+0.5匕由minf(x3)=f(x2+OCS1)得a=2/5=0.4.38故,本轮寻优的终点为：x1=x3=8做收敛性判别：llx1-X0|=V2.82+0.72,应继续搜索一.38下一轮寻优过程的起点为：x2=x3=广8下一轮寻优过程的搜索方向组为：(e2,S1)继续依样搜索直至满足收敛精度第4章约束优化方法约束优化方法要求大家重点掌握惩罚函数法,包括内点法、外点法、混合法、外点法构造惩罚函数：pqmin(X,rk)=f(X)rk-：ma)(gu(X),0：rk-hv(X)2uz1Vz1外点法既可以处理不等式约束优化问题,又可以处

18、理等式约束优化问题.需要注意的是：惩罚因子rk随迭代次数的增加是递增的,当rkTg时得到的解就是原问题的最优解.例：用外点法求解22minf(X)=x1x2-2x11s.t.3-x20时当3-x2三0时令=2x12=0改1kk=2x22rk(x2-3)=0.x1X为内点时无约束最优解一一3rk故得：x1=1x2=k1r*x1=1x2=limx2=3f(x)=9、内点法构造惩罚函数:p(X,rk)=f(X)-rkvu衽1gucX)p或：(X,rk)=f(X)-r-lngu(X)u1内点法只能处理不等式约束优化问题,不能处理等式约束优化问题.需要注意的是：惩罚因子rk随迭代次数的增加是递减的,当r

19、kT0时得到的解就是原问题的最优解.例：用内点法求解约束优化问题minf(X)=x1x2,2S.t.X1-X2.0-X1.0解：构造惩罚函数4(X,rk)=X1k._2_k.X2-rlnX2-X1-rInX1令：:x1-U0X1=1-rk12X2-x1,18rk-1(18rk-1)x2=160时,得x二0_*f(x)=0三、混合法qrMX)2vm构造惩罚函数:p1(X,rk)=f(X)-rumgu(X)p或：(X,rk)=f(X)ln-gu(X)-rjvhv(X)2混合法的特点是：对于不等式约束根据内点法构造惩罚项,对于等式约束根据外点法构造惩罚项.混合法既可以处理不等式约束优化问题,也可以处

20、理等式约束优化问题.例：用混合惩罚函数法求解约束优化问题2-2minf(X)=x1-3x2-X2S.t.1-Xi02X2X2解：构造惩罚函数.(X,rk)=x；-3x2-x；-rkln1-x1-令(X,rk)2x1+rk-3-2x21X1,2x2:k-r4日彳寸：X11二12rk3,X2二-2(二-1)r当rkT0时,得xf(x*)=10第5章遗传算法本章要求重点掌握遗传算法的5个要素、遗传算法的寻优机制、遗传算法的5个要素1 .编码将优化问题的解编码,用以模拟生物个体的基因组成；2 .初始种群生成将优化问题多个随机可行解汇成集合,用以模拟进化的生物种群;3 .个体适应度评估将优化问题目标函数加以变换,生成适应度函数来评价种群个体的适应度,用以模拟生物个体对环境的适应水平；4 .遗传操作包含选择、交叉、变异选择：一种使适应度函数值大的个体有更大的存活时机的机制,用以模拟环境对生物个体的自然选择；交叉：不同个体间相互交换信息,用以模拟高级生物有性繁殖过程中的基因重组过程；编码变异：模拟生物在遗传过程中