最优化方法复习

1、第1章最优化问题的根本概念§1.1 最优化的概念最优化就是依据最优化原理和方法,在满足相关要求的前提下,以尽可能高的效率求得工程问题最优解决方案的过程.§1.2 最优化问题的数学模型1 .最优化问题的一般形式findX1,X2,Xnminf(x,X2,Xn)s.t.gu(X1,X2,Xn)0u1,2,phv(X1,X2,Xn)0v1,2,q2 .最优化问题的向量表达式findXminf(X)s.t.G(X)0H(X)0式中：XX1,X2,XnTG(X)gKX),g2(X),gp(X)TH(X)%(X),h2(X),hp(X)T3 .优化模型的三要素设计变量、约束条件、目标函

2、数称为优化设计的三要素！设计空间：由设计变量所确定的空间.设计空间中的每一个点都代表一个设计方案§1.3优化问题的分类根据优化模型中三要素的不同表现形式,优化问题有多种分类方法：1根据模型中是否存在约束条件,分为约束优化和无约束优化问题2根据目标函数和约束条件的性质分为线性优化和非线性优化问题3根据目标函数个数分为单目标优化和多目标优化问题4根据设计变量的性质不同分为连续变量优化和离散变量优化问题第2章最优化问题的数学根底21n元函数的可微性与梯度、可微与梯度的定义1 .可微的定义设f(X)是定义在n维空间Rn的子集D上的n元实值函数,且X0D.假设存在n维向量L,对于任意n维向量P

3、,都有.f(X0P)f(X0)ltp.lim0llP0p|那么称f(X)在X0处可微.2 .梯度设有函数F(X),XXi,X2,XnT,在其定义域连续可导.我们把F(X)在定义域某点X处的所有一阶偏导数构成的列向量,定义为F(X)在点X处的梯度.记为:X1X2TFXn梯度有3个性质：函数在某点的梯度方向为函数过该点的等值线的法线方向;函数值沿梯度方向增加最快,沿负梯度方向下降最快；梯度描述的只是函数某点邻域的局部信息.22极小点及其判别条件一、相关概念1.极小点与最优解设f(X)是定义在n维空间Rn的子集D上的n元实值函数,假设存在X*D及实数0,使得XN(X,)D(XXWRtf(X)f(X)

4、,那么称X为f(X)的局部极小点；假设那么称X假设f(X)f(X),那么称X为f(X)的严格局部极小点.XD,都有f(X)f(X),那么称X为f(X)的全局极小点,假设f(X)f(X),为f(X)的全局严格极小点.findX对最优化问题"(X)st.G(X)H(X)而百00满足所有约束条件的向量XXi,X2,XnT称为上述最优化问题的一个可行解,全体可行解组成的集合称为可行解集.在可行解集中,满足:f(X)minf(X)的解称为优化问题的取优解.2.凸集和凸函数凸集：设DRn,假设对所有的X1、X2D,及0,1,都有X1(1)X2D,那么称D为凸集.凸函数：设f:DRnR1,D是凸集

5、,如果对于所有的X1、X2D,及0,1,都有fX1(1)X2f(X1)(1)f(X2),那么称f(X)为D上的凸函数.二、局部极小点的判别条件驻点：设f(X)是定义在n维空间Rn的子集D上的n元实值函数,X*是D的点,假设f(X)0,那么称X为f(X)的驻点.局部极小点的判别：设f(X)是定义在n维空间Rn的子集D上的n元实值函数,具有连续的二阶偏导数.假设X*是f(X)的驻点,且2f(X*)是正定矩阵,那么X*是f(X)的严格局部极小点.第3章无约束优化方法§3.1 下降迭代算法及终止准那么一、数值优化方法的根本思想根本思想就是在设计空间选定一个初始点Xk,从该点出发,根据某一方向

6、Sk(该方向确实定原那么是使函数值下降)前进一定的步长;得到一个使目标函数值有所下降的新设计点Xk1,然后以该点为新的初始点,重复上面过程,直至得到满足精度要求的最优点X.该思想可用下式表示：Xk1XkkSk二、迭代计算的终止准那么工程中常用的迭代终止准那么有3种：点距准那么相邻两次迭代点之间的距离充分小时,迭代终止.数学表达为：Xk1Xk函数下降量准那么(值差准那么)相邻两次迭代点的函数值之差充分小,迭代终止.数学表达为：|f(Xk1)f(Xk)|梯度准那么目标函数在迭代点处的梯度模充分小时,迭代终止数学表达为：|fXk1|、算法的收敛速度对于某一确定的下降算法,其优劣如何评价人们通常采用收

7、敛速度来评价.下面给出度量收敛速度的几个概念.1 .P阶收敛设序列Xk收敛于解X*,假设存在常数P0及L、ko,使当kko时下式:成立,那么称Xk为P阶收敛.2 .线性收敛设序列Xk收敛于解X*,假设存在常数ko、L及0,1,使当kko时下式：Xk1X*Lk成立,那么称Xk为线性收敛.3 .超线性收敛设序列Xk收敛于解X*,假设任给0都存在ko0,使当kko时下式：Xk1X*XkX*成立,那么称Xk为超线性收敛.§3.2 一维最优化方法一、确定初始区间的进退法任选一个初始点Xo和初始步长h,由此可确定两点X1Xo和X2X1h,通过比拟这两点函数值fX1、fX2的大小,来决定第三点X3

8、的位置.比拟这三点函数值是否呈“高一一低一一高排列特征,假设是那么找到了单峰区问,否那么向前或后退继续寻求下进退法依据的根本公式:X2X3具体步骤为：任意选取初始点Xo和恰当的初始步长h；令X1Xo,取x2X1h,计算fX1、fX2;假设fX1fX2,说明极小点在X2右侧,应加大步长向前搜索.转；假设fX1fX2,说明极小点在X1左侧,应以X1点为基准反向小步搜索.转;大步向前搜索：令h2h,取X3x2h,计算fd);假设f(X2)f(X3),那么f(X1)、f(X2)、f(X3)呈“上下高排列,说明X1,X3即为所求的单峰区间；假设f(X2)f(X3),说明极小点在X3右侧,应加大步长向前搜

9、索.此时要注意做变换：舍弃原X1点,以原X2点为新的X1点,原X3点为新的X2点.转,直至出现“高一一低一一高排列,那么单峰区间可得；反向小步搜索(要注意做变换)：为了保证X3点计算公式的一致性,做变换：将1原X2点记为新X1点,原Xi点记为新X2点,令hh,取X3X2h,转4例：用进退法确定函数f(x)X26x9的单峰区间a,b,设初始点x00,h1.解：Xo0h1x1xo0x2x1h1f(x1)9f(x2)4“xjf(X2)说明极小点在X2点右侧,应加大步长向前搜索令h2h212,取x3x2h123那么f(x3)0f(X2)f(X3)说明极小点在X3点右侧,应加大步长向前搜索舍弃原X1o的

10、点,令X11X23,那么f(X1)4f(X2)o令h2h224,取X3X2h347那么f(x3)16f(X2)0f(x1)、f(X2)>f%)呈“上下高排列X1,X3为单峰区间,即区间1,7即为所求二、黄金分割法黄金分割法是基于区间消去思想的一维搜索方法,其搜索过程必须遵循以下的原那么：对称取点的原那么：即所插入的两点在区间位置对称；插入点继承的原那么：即插入的两点中有一个是上次缩减区间时的插入点；等比收缩的原那么：即每一次区间消去后,单峰区间的收缩率保持不变.设初始区间为a,b,那么插入点的计算公式为:xia0.382(ba)x2a0.618(ba)黄金分割法的计算步骤如下：给定初始区

11、间a,b和收敛精度；给出中间插值点并计算其函数值：x1a0.382(ba)f(x1)x2a0.618(ba)f(x2).比拟f(xj、f(xz),确定保存区间得到新的单峰区间a,b;收敛性判别：计算区间a,b长度并与比拟,假设*1,、x(ab)2否那么转;在保存区间继承一点、插入一点,转例：使用黄金分割法求解优化问题：minf(x)2x2x,0.2.解：x1a0.382(ba)30.382(53)0.056f(xi)0.1152)x2a0.618(ba)30.618(53)1.944f(x2)7.667f(x2)f(x1)舍弃(1.944,5,保存-31.9441.944继承原木点,即x20.

12、056f(x2)0.115插入xa0.382(ba)30.382(1.9443)1.111f(x1)0.987vf(x2)f(x1).舍弃(0.056,1.944,保存-3,0.0560.056(3)继承原木点,即x21.111f(x2)0.987插入x1a0.382(ba)30.382(0.0563)1.832f(x1)0.306:f(x2)f(x1).保存-1.832,0.0560.056(1.832);继承原x2点,即x11.111f(x1)0.987f(x2)0.888插入x21.8320.618(0.0561.832)0.665f(X2)f(Xi).保存-1.832,-0.665如此

13、迭代,到第8次,保存区为-1.111,-0.9400.940(1.111)0.171d.x1(1.1110.940)1.0255f(x)0.9992§3.3 梯度法一、根本思想对于迭代式Xk1xkkSk,当取搜索方向Skf(Xk)时构成的寻优算法,称为求解无约束优化问题的梯度法.二、迭代步骤给定出发点xk和收敛精度；计算xk点的梯度F(Xk),并构造搜索方向SkF(Xk);令Xk1Xkksk,通过一维搜索确定步长k,即：minF(XkkSk)求得新点Xk1收敛判断：假设JF(Xk1)|成立,输出X*Xk1、F(X*)F(Xk1),寻优结束；否那么令kk1转继续迭代,直到满足收敛精度要

14、求.三、梯度法的特点梯度法寻优效率受目标函数性态影响较大.假设目标函数等值线为圆,那么一轮搜索就可找到极致点；假设当目标函数等值线为扁椭圆时,收敛速度那么显著下降.梯度法中相邻两轮搜索方向相互垂直.§3.4 牛顿法牛顿法分为根本牛顿法和阻尼牛顿法两种.对于迭代式Xk1XkkSk,当取k1且搜索方向Sk2f(Xk)1f(Xk)时构成的寻优算法,称为求解无约束优化问题的根本牛顿法；对于迭代式Xk1XkkSk,取搜索方向Sk2f(Xk)1f(Xk),k为从Xk出发、沿牛顿方向做一维搜索获得的最优步长,所构成的寻优算法,称为求解无约束优化问题的阻尼牛顿法.搜索方向Sk2f(Xk)1f(Xk)

15、称为牛顿方向.这里需要注意的是会求海塞阵的逆矩阵§3.5 变尺度法我们把具有Xk1XkkAkf(Xk)迭代模式的寻优算法称为变尺度法.其搜索方向表达式为：SkAkf(Xk),称为拟牛顿方向,其中Ak称为变尺度矩库.在迭代开始的时候,A0I；随着迭代过程的继续,Ak2f(Xk)1f(Xk),因此,变尺度法从梯度法出发,随着迭代过程的继续最终趋向于牛顿法.§3.6 共腕梯度法一、共腕方向的概念设H为对称正定矩阵,假设有两个n维向量Si和S2,满足S1THS20,那么称向量Si与&关于矩阵H共腕,共腕向量的方向称为共腕方向.假设有一组非零向量S,S2,Sn满足STHSj0

16、(ij),那么称这组向量关于矩阵H共腕.对于n元正定二次函数,依次沿着一组共腕方向进行一维搜索,最多n次即可得到极值点.二、共腕方向的形成1对于函数f(X)f(X1,X2,Xn)-XtHXBtXC2沿任意方向S0在设计空间上任意做两条平行线,分别与目标函数等值线切于点X1、X2,令S1X2X1,那么S0、S1关于矩阵H共腕.三、共腕梯度法对于迭代式Xk1XkkSk,取搜索方向Sk1f(Xk1)kSk其中：S0f(X°),kf(Xk1)f(Xk)|2共腕梯度法相邻两轮搜索方向是一对共腕方向.§3.7鲍威尔法根本迭代公式仍旧是：Xk1XkkSk根本鲍威尔法每轮搜索分为两步：一环

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

18、下一环搜索起点确实定：下一环搜索起点由本环搜索结果确定,方法是：假设本环的搜索结果满足鲍威尔条件,那么以本环搜索终点为起点,沿新生成的方向作一维搜索,得到的新点作为本轮的搜索终点,也是下一轮的搜索起点；假设本环的搜索结果不满足鲍威尔条件,那么取本环搜索终点和反射点中目标函数值小的点作为本轮的搜索终点,也是下一轮的搜索起点.这里需要注意的是反射点的计算：x,2x；x0k式中：xk2是本环起点x0k相对于本环终点xk沿新生成方向的反射点.例:对于无约束目标函数minf(X)X122x24x12x1x2,利用修正Powell法从x01 ,出发求最优解解:令x0x0P1P0(72)x；x0(x；)自：

19、那么：x1x2X11令fx2行：0.5那么：x231.5该环生成的新搜索方向为：s1x2x01.50.51对S1进行有效性判别:反射点x42X2X0321.5f1f(X0)f2_1f(X2)7.5f3f(X4)71f(X0)f(X；)3(7)4,2f(X11)f(X2)7(7.5)0.5故最大下降量m故：f3%和(f12f2f3)(f1f2m(f1f3)2均成立方向S1可用以x2为起点,沿s1方向作一维搜索:x3x2s131.520.531.520.5由minf(X3)f(x2S1)得2/50.4故,本轮寻优的终点为:X113.8x31.7做收敛性判别:IV2.820.72,应继续搜索下一轮寻

20、优过程的起点为：x213.8x31.7下一轮寻优过程的搜索方向组为:(e2,S1)约束优化方法约束优化方法要求大家重点掌握惩罚函数法,包括点法、外点法、混合法.、外点法构造惩罚函数：pqk_k2k2min(X,r)f(X)rma)(gu(X),0rhv(X)u1v1外点法既可以处理不等式约束优化问题,又可以处理等式约束优化问题.需要注意的是:惩罚因子随迭代次数的增加是递增的,当时得到的解就是原问题的最优解.例:用外点法求解minf(X)x；s.t.3x20x22xi解:构造惩罚函数(X,rk)2x12x2行：(X,rk)2x1x1x1x11、点法2x2x2一12x12x122222x12x12

21、rk(x23)03rkkr*x1构造惩罚函数:(X,rk)f(X)11gu(X)2x1rk(3x2)22max3x2,0X2又2*乂2limx2k或：X点法只能处理不等式约束优化问题,需要注意的是：惩罚因子是原问题的最优解.例：用点法求解约束优化问题minf(X)x1X2_*3f(x)prk)f(X)rklnu1不能处理等式约束优化问题.随迭代次数的增加是递减的,当rkgu(X)0时得到的解就2s.t.x1x2x10解：构造惩罚函数(X,rk)x1x2k._2_k.rlnx2x1rlnx1一1x12x12x2x1一1x212x2x14日彳可x1,18rk14X2(18rk1)2rk16当rk0

22、时,得_*f(x)0三、混合法构造惩罚函数:(X,rk)f(X)krik或：(X,r)f(X)1gu(X)pk._rlnu1q2hv(X)21qk2gu(X)r2hv(X)v1混合法的特点是：对于不等式约束根据点法构造惩罚项,对于等式约束根据外点法构造惩罚项.混合法既可以处理不等式约束优化问题,也可以处理等式约束优化问题.例：用混合惩罚函数法求解约束优化问题-2minf(X)x123x2x2s.t.1x10x20解：构造惩罚函数(X,rk)x123x22X2k12rln1xjx2r2x1令(X,rk)2x2X2x2r得：x1k2rX2312(1)r_*f(x)10时,得x第5章遗传算法本章要求重点掌握遗传算法的5个要素、遗传算法的寻优机制、遗传算法的5个要素1.编码将优化问题的解编码,用以模拟生物个体的基因组成；2 .初始种群生成将优化问题多个随机可行解汇成集合,用以模拟进化的生物种群；3 .个体适应度评估将优化问题目标函数加以变换,生成适应度函数来评价种群个体的适应度,用以模拟生物个体对环境的适应水平；4 .遗传操作包含选择、交叉、变异选择：一种使适应度函数值大的个体有更大