最优化方法复习

1、.第 1 章 最优化问题的基本概念§1.1 最优化的概念最优化就是依据最优化原理和方法，在满足相关要求的前提下，以尽可能高的效率求得工程问题最优解决方案的过程。§1.2 最优化问题的数学模型1. 最优化问题的一般形式findx1 , x2 , xnmin f ( x1 , x2 , xn )s.t. gu ( x1, x2, xn )0u1,2, phv ( x1 , x2, xn )0v1,2, q2. 最优化问题的向量表达式findXmin f ( X )s.t. G ( X )0H(X)0式中： X x1 , x2 , xn TG( X ) g1 ( X ), g2

2、( X ), g p ( X ) TH ( X )h1 ( X ), h2 ( X ), hp ( X ) T3. 优化模型的三要素设计变量、约束条件、目标函数称为优化设计的三要素！设计空间：由设计变量所确定的空间。 设计空间中的每一个点都代表一个设计方案。§1.3 优化问题的分类按照优化模型中三要素的不同表现形式，优化问题有多种分类方法：1 按照模型中是否存在约束条件，分为约束优化和无约束优化问题2 按照目标函数和约束条件的性质分为线性优化和非线性优化问题3 按照目标函数个数分为单目标优化和多目标优化问题4 按照设计变量的性质不同分为连续变量优化和离散变量优化问题第 2 章最优化问

3、题的数学基础§2.1n 元函数的可微性与梯度.一、可微与梯度的定义1. 可微的定义设 f ( X ) 是定义在 n 维空间 Rn 的子集 D 上的 n 元实值函数，且 X 0D 。若存在 n 维向量 L ，对于任意 n 维向量 P ，都有limf ( X 0P) f ( X 0 ) LT P0P0P则称 f ( X ) 在 X 0 处可微。2. 梯度设有函数 F(X) ，X x1 , x2 , , xn T ，在其定义域连续可导。我们把 F ( X ) 在定义域某点 X 处的所有一阶偏导数构成的列向量，定义为F ( X ) 在点 X 处的梯度。记为：TF ( X k )F,F, ,F

4、x1 x2xn梯度有 3 个性质：函数在某点的梯度方向为函数过该点的等值线的法线方向；函数值沿梯度方向增加最快，沿负梯度方向下降最快；梯度描述的只是函数某点邻域的局部信息。§2.2 极小点及其判别条件一、相关概念1. 极小点与最优解设 f ( X ) 是定义在 n 维空间 Rn的子集 D 上的 n 元实值函数，若存在X *D 及实数0，使得XN(X*, )D ( XX * ) 都有 f ( X * ) f ( X ) ，则称 X *为 f ( X ) 的局部极小点；若f ( X * )f ( X ) ，则称 X * 为 f ( X ) 的严格局部极小点。若 XD ，都有 f ( X

5、* )f ( X ) ，则称 X * 为 f ( X ) 的全局极小点，若 f ( X * ) f ( X ) ，则称 X * 为 f ( X ) 的全局严格极小点。findX对最优化问题minf ( X )而言s.t. G ( X )0H(X) 0满足所有约束条件的向量X x , x, xT 称为上述最优化问题的一个可行解， 全12n体可行解组成的集合称为可行解集。在可行解集中，满足：*.2. 凸集和凸函数凸集：设 DRn ，若对所有的 X 1、 X 2D ，及0,1 ，都有X 1(1) X 2D ，则称 D 为凸集。凸函数：设 f : D R nR1 ，D 是凸集，如果对于所有的 X 1、

6、 X 2D ，及0,1 ，都有 f X 1(1)X 2f ( X 1 ) (1) f ( X 2 ) ，则称 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 ) 的驻点，且2 f ( X * ) 是正定矩阵， 则 X * 是 f ( X ) 的严格局部极小点

7、。第 3 章 无约束优化方法§3.1 下降迭代算法及终止准则一、数值优化方法的基本思想基本思想就是在设计空间选定一个初始点X k ，从该点出发，按照某一方向Sk （该方向的确定原则是使函数值下降）前进一定的步长k ，得到一个使目标函数值有所下降的新设计点 X k 1 ，然后以该点为新的初始点， 重复上面过程， 直至得到满足精度要求的最优点 X* 。该思想可用下式表示： X k 1X kk Sk二、迭代计算的终止准则工程中常用的迭代终止准则有3 种：点距准则相邻两次迭代点之间的距离充分小时，迭代终止。数学表达为：X k 1X k函数下降量准则（值差准则）相邻两次迭代点的函数值之差充分小

8、，迭代终止。数学表达为：f ( X k 1 )f ( X k )梯度准则.目标函数在迭代点处的梯度模充分小时，迭代终止。数学表达为：f ( X k 1 )三、算法的收敛速度对于某一确定的下降算法，其优劣如何评价？人们通常采用收敛速度来评价。下面给出度量收敛速度的几个概念。1. P 阶收敛设序列 X k收敛于解 X *，若存在常数 P0 及 L 、 k0 ，使当 kk0 时下式：X k 1X *L X kX *p成立，则称 X k为 P 阶收敛。2. 线性收敛设序列 X k收敛于解 X * ，若存在常数 k0 、 L 及( 0,1) ，使当 kk0 时下式：X k 1X *L k成立，则称X k

9、 为线性收敛。3. 超线性收敛设序列 X k收敛于解 X * ，若任给0 都存在 k00 ，使当 kk0 时下式：X k 1X *X k X *成立，则称X k为超线性收敛。§3.2 一维最优化方法一、确定初始区间的进退法任选一个初始点x0 和初始步长 h ，由此可确定两点x1x0 和 x2x1h ，通过比较这两点函数值f ( x1 ) 、 f ( x2 ) 的大小，来决定第三点x3 的位置。比较这三点函数值是否呈“高低高”排列特征，若是则找到了单峰区间，否则向前或后退继续寻求下一点。进退法依据的基本公式：x1x0x2x1hx3x2h具体步骤为：任意选取初始点x0 和恰当的初始步长

10、h ；令 x1x0 ，取 x2x1h ，计算 f ( x1 ) 、 f ( x2 ) ；若 f ( x1)f (x2 ) ，说明极小点在x2 右侧，应加大步长向前搜索。转 ；若 f ( x1)f (x2 ) ，说明极小点在x1 左侧，应以 x1 点为基准反向小步搜索。转 ；.大步向前搜索：令h2h ，取 x3x2h ，计算 f (x3 ) ；若 f ( x2 ) f ( x3 ) ，则 f (x1 ) 、f (x2 ) 、f ( x3 ) 呈“高低高” 排列，说明 x1 , x3 即为所求的单峰区间；若 f ( x2 ) f ( x3 ) ，说明极小点在 x3 右侧，应加大步长向前搜索。 此时

11、要注意做变换：舍弃原 x1 点，以原 x2 点为新的 x1 点，原 x3 点为新的 x2 点。转 ，直至出现“高 低高”排列，则单峰区间可得；反向小步搜索（要注意做变换） ：为了保证 x3 点计算公式的一致性，做变换：将原 x2 点记为新 x1 点，原 x1 点记为新 x2点，令 h1 h ，取 x3x2 h ，转 4例：用进退法确定函数 f ( x)x 26x9的单峰区间 a， b ，设初始点 x00 ， h 1。解： x00h 1 x1x0 0x2x1 h1f (x1 ) 9f (x2 ) 4f ( x1 )f (x2 )说明极小点在 x2 点右侧，应加大步长向前搜索令 h2h212，取

12、x3x2h123则 f (x3 )0 f ( x2 ) f ( x3 )说明极小点在 x3 点右侧，应加大步长向前搜索舍弃原 x10 的点，令 x11 x23，则 f ( x1 )4 f ( x2 ) 0令 h 2h2 2 4 ，取 x3x2h3 4 7则 f ( x3 ) 16 f ( x2 ) 0f ( x1 ) 、 f (x2 ) 、 f (x3 ) 呈“高低高”排列 x1 ,x 3 为单峰区间，即区间 1 ，7 即为所求二、黄金分割法黄金分割法是基于区间消去思想的一维搜索方法，其搜索过程必须遵循以下的原则：对称取点的原则：即所插入的两点在区间位置对称；插入点继承的原则：即插入的两点中有

13、一个是上次缩减区间时的插入点；等比收缩的原则：即每一次区间消去后，单峰区间的收缩率保持不变。.设初始区间为 a ，b ，则插入点的计算公式为：x1a0.382( ba)x2a0.618(ba)黄金分割法的计算步骤如下：给定初始区间 a ， b 和收敛精度；给出中间插值点并计算其函数值：x1a0.382(ba)f (x1 )x2a0.618(ba)f (x2 ) ；比较 f ( x1 ) 、 f (x2 ) ，确定保留区间得到新的单峰区间 a，b ；收敛性判别：计算区间a，b长度并与比较，若ba，输出x*1 (ab)2否则转 ；在保留区间继承一点、插入一点，转。例：使用黄金分割法求解优化问题：m

14、in f(x)x22x，3 x50.2 。解： x1a0.382(ba)30.382(53)0.056f ( x1 )0.115x2a0.618(ba)30.618(53)1.944f ( x2 )7.667 f ( x2 )f ( x1 )舍弃（ 1.944 ，5 ，保留 -3，1.9441.944(3)；继承原 x1 点，即 x20.056f ( x2 ) 0.115插入 x1a0.382(ba)3 0.382(1.9443)1.111f ( x1 )0.987 f ( x2 )f (x1 )舍弃（ 0.056 ，1.944，保留 -3 ，0.0560.056( 3)；继承原 x1 点，即

15、 x21.111f ( x2 )0.987插入 xa0.382(ba)3 0.382( 0.0563)1.832fx1 )0.3061( f ( x2 )f (x1 )保留 -1.832，0.0560.056(1.832)；继承原 x2 点，即 x11.111f (x1 )0.987插入 x21.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 x*1( 1.1110.940)1.0255f ( x* )

16、0.9992§3.3 梯度法一、基本思想对于迭代式 X k 1X kk Sk ，当取搜索方向 Skf ( X k ) 时构成的寻优算法， 称为求解无约束优化问题的梯度法。二、迭代步骤给定出发点 X k 和收敛精度；计算 X k 点的梯度 F ( X k ) ，并构造搜索方向 SkF ( X k ) ；令 X k 1X kk Sk ，通过一维搜索确定步长k ，即：min F ( X kk Sk )求得新点 X k1收敛判断：若F ( X k 1 )成立，输出 X *X k 1 、 F ( X * )F ( X k 1 ) ，寻优结束；否则令 kk 1转 继续迭代，直到满足收敛精度要求。

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

18、为求解无约束优化问题的阻尼牛顿法。搜索方向 Sk2 f ( X k ) 1f ( X k ) 称为牛顿方向。.这里需要注意的是会求海塞阵的逆矩阵。§3.5 变尺度法我们把具有 X k 1X kk Ak f ( X k ) 迭代模式的寻优算法称为变尺度法。其搜索方向表达式为： SkAkf ( X k ) ，称为拟牛顿方向，其中 Ak 称为变尺度矩阵。在迭代开始的时候， A0I ；随着迭代过程的继续， Ak2 f ( X k ) 1 f ( X k ) 。因此，变尺度法从梯度法出发，随着迭代过程的继续最终趋向于牛顿法。§3.6 共轭梯度法一、共轭方向的概念设 H 为对称正定矩阵

19、， 若有两个 n 维向量 S1 和 S2 ，满足 S1THS20 ，则称向量 S1与 S2 关于矩阵 H 共轭，共轭向量的方向称为共轭方向。若有一组非零向量 S1 ， S2 ， ， Sn 满足 SiT H Sj 0 (ij ) ，则称这组向量关于矩阵 H 共轭。对于 n 元正定二次函数，依次沿着一组共轭方向进行一维搜索，最多n 次即可得到极值点。二、共轭方向的形成对于函数 f ( X )f ( x1 , x2 , xn )1XTHX BTX C2沿任意方向X2，令 S1X 2三、共轭梯度法对于迭代式其中： S0S0 在设计空间上任意做两条平行线，分别与目标函数等值线切于点X 1 、X 1 ，则

20、 S0 、 S1关于矩阵 H 共轭。X k 1X kk Sk ，取搜索方向 Sk 1f ( X k 1 )k Skf ( X k21 )f ( X 0 ) ， k2f ( X k)共轭梯度法相邻两轮搜索方向是一对共轭方向。§3.7 鲍威尔法基本迭代公式仍旧是：X k 1X kk Sk基本鲍威尔法每轮搜索分为两步：一环的搜索 +在该环搜索完毕后生成的新方向上的一维搜索。对于基本鲍威尔法，相邻两轮搜索生成的搜索方向是共轭的。修正鲍威尔法与基本鲍威尔法类似，所不同的是每环搜索后生成的新方向要利用鲍.威尔条件判别其可用性。注意掌握鲍威尔条件的表达式和应用！每环搜索方向组的生成：1 第一环的搜

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

22、为本轮的搜索终点，也是下一轮的搜索起点。这里需要注意的是反射点的计算：X nk2 2X nkX 0k式中： X nk2 是本环起点 X 0k 相对于本环终点 X nk 沿新生成方向的反射点。例：对于无约束目标函数minf ( X )x122x224x12x1 x2，利用修正 Powell法从X 01出发求最优解。1解：令 X01 X 01P1P0(e1 , e2 )1X 11X 011101令 f ( X11 ) 0得：2 则： X1131X 21X 110311令 f ( X 21 ) 0得：0.5 则： X 2131.5该环生成的新搜索方向为：S1X 21X 013121.510.5.对

23、S1 进行有效性判别：反射点 X 412X21X 013152121.5f 1f ( X 01 )3f 2f ( X 21 )7.5f 3f (X 41 )71f ( X 01 )f ( X 11 )3 (7)4 ，2 f ( X 11 )f ( X 21 )7 ( 7.5) 0.5故最大下降量m14故： f3f1 和 ( f12 f 2f 3 )( f1f 2m )21m ( f1f 3 ) 2 均成立2方向 S1 可用以 X 12 为起点，沿 S1 方向作一维搜索：X 31X 21S132321.50.51.50.5由 min f ( X 31 )f ( X 21S1)得2 / 50.4故

24、，本轮寻优的终点为： X 1X 313.81.7做收敛性判别：X 1X 02.820.7 2，应继续搜索下一轮寻优过程的起点为： X 02X 313.81.7下一轮寻优过程的搜索方向组为：(e2 , S1 )第 4 章约束优化方法约束优化方法要求大家重点掌握惩罚函数法，包括点法、外点法、混合法。一、外点法构造惩罚函数：pmax gu ( X ),0 2qmin ( X , r k ) f ( X ) r kr k hv ( X )2u 1v1外点法既可以处理不等式约束优化问题，又可以处理等式约束优化问题。.需要注意的是：惩罚因子 r k随迭代次数的增加是递增的，当 r k时得到的解就是原问题的

25、最优解。例：用外点法求解min f ( X )x12x222x11s.t. 3 x20解：构造惩罚函数( X , r k )x12x222x1 1 r kmax 3x2 ,0 2( X , r k)x12x222x11 r k (3 x2 ) 2当3 x20 时x12x222x11当 3 x20时令2x1 2 0 x12x22r k (x23) 0x13r k*1*lim x2 3*)9得： x1 1 x2kx1x2f ( x1rk二、点法构造惩罚函数：p1p( X , r k ) f ( X ) r k或： ( X , r k )f ( X )r kln gu (X )u1 gu ( X )

26、u1点法只能处理不等式约束优化问题，不能处理等式约束优化问题。需要注意的是：惩罚因子r k 随迭代次数的增加是递减的，当r k0 时得到的解就是原问题的最优解。例：用点法求解约束优化问题min f ( X )x1x2s.t.x12x20x10解：构造惩罚函数( X , r k )x1x2 r k ln x2 x12 r k ln x1令1rk2x1rk1x2x120x1x11r kx210x2x12.得 x11 8r k1， x2( 1 8r k1) 2r k416当 r k0 时，得 x*0f ( x* )00三、混合法构造惩罚函数：p1q( X , r k )f ( X ) r1kr2kh

27、v ( X ) 2u1 gu ( X )v 1pq或： ( X , r k )f ( X )r1klngu ( X )r2khv ( X ) 2u 1v1混合法的特点是：对于不等式约束按照点法构造惩罚项，对于等式约束按照外点法构造惩罚项。混合法既可以处理不等式约束优化问题，也可以处理等式约束优化问题。例：用混合惩罚函数法求解约束优化问题min f ( X )x123x2x22s.t.1x10x20解：构造惩罚函数( X , r k )x123x2x22r k ln 1 x1 1k x22r2x1r k1令( X ,r k )1x1032x22x2r k得：x111 2r k， x23211)2(kr当 r k0 时，得 x*1f ( x* )10第 5章遗传算法本章要求重点掌握遗传算法的5 个要素、遗传算法的寻优机制。一、遗传算法的5 个要素.1. 编码将优化问题的解编码，用以模拟生物个体的基因组成；2. 初始种群生成将优化问题多个随机可行解汇成集合，用以模拟进化的生物种群；3. 个体适应度评估将优化问题目标函数加以变换，生成适应度函数来评价种群个体的适应度，用以模拟生物个体对环境的适应能力；4. 遗传操作包含选择、交叉、变异选择：一种使适应度函数值大的个体有更大的存活机会的机制，用以模拟环境对