最优化方法复习.doc

1、第 1 章 最优化问题的基本概念1.1 最优化的概念最优化就是依据最优化原理和方法，在满足相关要求的前提下，以尽可能高的效率求得工程问题最优解决方案的过程。1.2 最优化问题的数学模型1.最优化问题的一般形式qvxhpugtsfindnvun,210),(,.m,2121 2.最优化问题的向量表达式0)(.inXHGtsfd式中： Tnx,21 TpXgg)(,)()(2 hXh,13.优化模型的三要素设计变量、约束条件、目标函数称为优化设计的三要素！设计空间：由设计变量所确定的空间。设计空间中的每一个点都代表一个设计方案。 1.3 优化问题的分类按照优化模型中三要素的不同表现形式，优化问题有

2、多种分类方法：1 按照模型中是否存在约束条件，分为约束优化和无约束优化问题2 按照目标函数和约束条件的性质分为线性优化和非线性优化问题3 按照目标函数个数分为单目标优化和多目标优化问题4 按照设计变量的性质不同分为连续变量优化和离散变量优化问题第 2 章 最优化问题的数学基础2.1 元函数的可微性与梯度n一、可微与梯度的定义1.可微的定义设 是定义在 维空间 的子集 上的 元实值函数，且 。若存在)(XfnnRDnDX0维向量 ，对于任意 维向量 ，都有nLP0)()(lim00Lff TP则称 在 处可微。)(Xf02.梯度设有函数 ， ，在其定义域内连续可导。我们把 在定)(FTnxX,2

3、1 )(XF义域内某点 处的所有一阶偏导数构成的列向量，定义为 在点 处的梯度。记)(XF为： TnkxFxXF,)(21梯度有 3 个性质：函数在某点的梯度方向为函数过该点的等值线的法线方向；函数值沿梯度方向增加最快，沿负梯度方向下降最快；梯度描述的只是函数某点邻域内的局部信息。2.2 极小点及其判别条件一、相关概念1.极小点与最优解设 是定义在 维空间 的子集 上的 元实值函数，若存在 及实数)(XfnnRDnDX*，使得 都有 ，则称 为 的局部0 )(),(*XN)(*ff)(f极小点；若 ，则称 为 的严格局部极小点。)fff若 ，都有 ，则称 为 的全局极小点，若D)(*f*)(X

4、f，则称 为 的全局严格极小点。)(*Xff对最优化问题 而言0)(.minXHGtsfd满足所有约束条件的向量 称为上述最优化问题的一个可行解，Tnx,21全体可行解组成的集合称为可行解集。在可行解集中，满足：的解称为优化问题的最优解。)(min)(*Xff2.凸集和凸函数凸集：设 ，若对所有的 ，及 ，都有nRDDX21、 1,0，则称 为凸集。X21)(凸函数：设 ， 是凸集，如果对于所有的 ，及1:fnDX21、，都有 ，则称 为 上的凸函1,0 )(1)()( 221 fXfX )(f数。二、局部极小点的判别条件驻点：设 是定义在 维空间 的子集 上的 元实值函数， 是 的内点，)(

5、fnnRDn*XD若 ，则称 为 的驻点。0)(*Xf*)(Xf局部极小点的判别：设 是定义在 维空间 的子集 上的 元实值函数，具nn有连续的二阶偏导数。若 是 的驻点，且 是正定矩阵，则 是*)(f )(*2Xf*的严格局部极小点。)(f第 3 章 无约束优化方法3.1 下降迭代算法及终止准则一、数值优化方法的基本思想基本思想就是在设计空间内选定一个初始点 ，从该点出发，按照某一方向kX（该方向的确定原则是使函数值下降）前进一定的步长 ，得到一个使目标函数值kS k有所下降的新设计点 ，然后以该点为新的初始点，重复上面过程，直至得到满足1kX精度要求的最优点 。*该思想可用下式表示： kk

6、kS1二、迭代计算的终止准则工程中常用的迭代终止准则有 3 种：点距准则相邻两次迭代点之间的距离充分小时，迭代终止。数学表达为： kkX1函数下降量准则（值差准则）相邻两次迭代点的函数值之差充分小，迭代终止。数学表达为： )()(1kkXff梯度准则目标函数在迭代点处的梯度模充分小时，迭代终止。数学表达为： )(1kf三、算法的收敛速度对于某一确定的下降算法，其优劣如何评价？人们通常采用收敛速度来评价。下面给出度量收敛速度的几个概念。1. 阶收敛P设序列 收敛于解 ，若存在常数 及 、 ，使当 时下式：kX*0PL0k0kpkXL*1成立，则称 为 阶收敛。kP2.线性收敛设序列 收敛于解 ，

7、若存在常数 、 及 ，使当 时下式：kX*0kL)1,0(0kkL1成立，则称 为线性收敛。k3.超线性收敛设序列 收敛于解 ，若任给 都存在 ，使当 时下式：kX*00k0k*1Xk成立，则称 为超线性收敛。k3.2 一维最优化方法一、确定初始区间的进退法任选一个初始点 和初始步长 ，由此可确定两点 和 ，通过比较0xh01xh12这两点函数值 、 的大小，来决定第三点 的位置。比较这三点函数值是否)(1f)(2f 3呈“高低高”排列特征，若是则找到了单峰区间，否则向前或后退继续寻求下一点。进退法依据的基本公式： 01xh23具体步骤为：任意选取初始点 和恰当的初始步长 ；0xh令 ，取 ，

8、计算 、 ；01xh12)(1xf)(2f若 ，说明极小点在 右侧，应加大步长向前搜索。转 ；)(21xff2x若 ，说明极小点在 左侧，应以 点为基准反向小步搜索。转11x；大步向前搜索：令 ，取 ，计算 ；hhx23)(3f若 ，则 、 、 呈“高低高”排列，说明)(32xff )(1f)(f)(3f即为所求的单峰区间；,31x若 ，说明极小点在 右侧，应加大步长向前搜索。此时要注意做)(32ff3x变换：舍弃原 点，以原 点为新的 点，原 点为新的 点。转，直至出现“高12x12x低高”排列，则单峰区间可得；反向小步搜索（要注意做变换）：为了保证 点计算公式的一致性，做变换：3将原 点记

9、为新 点，原 点记为新 点，令 ，取 ，转2x1x12xh41hx23例：用进退法确定函数 的单峰区间a，b，设初始点 ， 。96)(2f 01解： 0hx 4)()(12121 xfxfhx )(fxf说明极小点在 点右侧，应加大步长向前搜索2令 ，取 则1h32123hx0)(3xf )(32xff说明极小点在 点右侧，应加大步长向前搜索舍弃原 的点，令 ，则01x312x0)(4)(21xfxf令 ，取 则42h73h)(1623xf、 、 呈“高低高”排列)(1xf)(f)(xf为单峰区间，即区间1，7即为所求,3二、黄金分割法黄金分割法是基于区间消去思想的一维搜索方法，其搜索过程必须

10、遵循以下的原则：对称取点的原则：即所插入的两点在区间内位置对称；插入点继承的原则：即插入的两点中有一个是上次缩减区间时的插入点；等比收缩的原则：即每一次区间消去后，单峰区间的收缩率 保持不变。设初始区间为a，b，则插入点的计算公式为： )(382.01abax62黄金分割法的计算步骤如下：给定初始区间a，b和收敛精度 ；给出中间插值点并计算其函数值：)(382.01abax)(1xf；62 2比较 、 ，确定保留区间得到新的单峰区间a，b；)(1xf)(2f收敛性判别：计算区间a，b长度并与 比较，若 ，输出ab)(21*bax否则转；在保留区间内继承一点、插入一点，转。例：使用黄金分割法求解

11、优化问题： 。2.0532)(minxxf，解： 1.)(056.382.03)(382.01 fabax 67941)(66 22 x 舍弃（1.944，5，保留-3，1.944 ；)(1xff )3(94.继承原 点，即 5.0)(05.22xf插入 87.0)(1.)394138.)(38.0 11 xfabax 舍弃（0.056，1.944，保留-3，0.056 ；)(12ff )3(56继承原 点，即x 7.0)(.22xf插入 0.)(832.1)5638.)(38.0 11 xfaba 保留-1.832，0.056 ；)(12xff (.继承原 点，即2x 987.0)(1.1x

12、f插入 8.0)(6532.056(83.1 2xf 保留-1.832，-0.665)(2xff如此迭代，到第 8 次，保留区为-1.111,-0.940 17.).(94. 0)(025.1)94.1.(2* xfx3.3 梯度法一、基本思想对于迭代式 ，当取搜索方向 时构成的寻优算法，kkkSX1 )(kkXfS称为求解无约束优化问题的梯度法。二、迭代步骤给定出发点 和收敛精度 ；k计算 点的梯度 ，并构造搜索方向 ；kX)(kXF)(kkXFS令 ，通过一维搜索确定步长 ，即：kS1 )(min求得新点 1kX收敛判断：若 成立，输出 、 ，寻优结)(1kF1*kX)()(1*kXF束；

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

14、。)()(12kkk XffS这里需要注意的是会求海塞阵的逆矩阵。3.5 变尺度法我们把具有 迭代模式的寻优算法称为变尺度法。)(1kkkkfAX其搜索方向表达式为： ，称为拟牛顿方向，其中 称为变尺度XS kA矩阵。在迭代开始的时候， ；随着迭代过程的继续，I0。)()(12kkk XffA因此，变尺度法从梯度法出发，随着迭代过程的继续最终趋向于牛顿法。3.6 共轭梯度法一、共轭方向的概念设 为对称正定矩阵，若有两个 维向量 和 ，满足 ，则称向量Hn1S2021SHT与 关于矩阵 共轭，共轭向量的方向称为共轭方向。1S2若有一组非零向量 ， ， 满足 ，则称这组向量关于1S2n )(0ji

15、jTi 矩阵 共轭。对于 元正定二次函数，依次沿着一组共轭方向进行一维搜索，最多 次即可得到n n极值点。二、共轭方向的形成对于函数 CXBHxfXf TTn21),()21沿任意方向 在设计空间上任意做两条平行线，分别与目标函数等值线切于点 、0S 1X，令 ，则 、 关于矩阵 共轭。2X12101S三、共轭梯度法对于迭代式 ，取搜索方向kkkX1 kkk SXfS)(11其中： ，)(00fS21)(kkXf共轭梯度法相邻两轮搜索方向是一对共轭方向。3.7 鲍威尔法基本迭代公式仍旧是： kkkS1基本鲍威尔法每轮搜索分为两步：一环的搜索+在该环搜索完毕后生成的新方向上的一维搜索。对于基本鲍

16、威尔法，相邻两轮搜索生成的搜索方向是共轭的。修正鲍威尔法与基本鲍威尔法类似，所不同的是每环搜索后生成的新方向要利用鲍威尔条件判别其可用性。注意掌握鲍威尔条件的表达式和应用！每环搜索方向组的生成：1第一环的搜索方向组就是各坐标轴方向2下一环的搜索方向组由本环搜索方向组和本环生成的新方向共同确定，方法是：若本环的搜索结果满足鲍威尔条件，则将本环搜索方向组中使目标函数下降量最大的方向去掉，并将本环生成的新方向递补进去，就形成下一环的搜索方向组；若本环的搜索结果不满足鲍威尔条件，则下一环的搜索方向组仍旧沿用本环搜索方向组不变。下一环搜索起点的确定：下一环搜索起点由本环搜索结果确定，方法是：若本环的搜索

17、结果满足鲍威尔条件，则以本环搜索终点为起点，沿新生成的方向作一维搜索，得到的新点作为本轮的搜索终点，也是下一轮的搜索起点；若本环的搜索结果不满足鲍威尔条件，则取本环搜索终点和反射点中目标函数值小的点作为本轮的搜索终点，也是下一轮的搜索起点。这里需要注意的是反射点的计算： knknX02式中： 是本环起点 相对于本环终点 沿新生成方向的反射点。knX2kX0例：对于无约束目标函数 ，利用修正 Powell 法从21214)(minxxf出发求最优解。10解：令 0X),(2101eP10令 得： 则：)(1Xf 213X3012令 得： 则：)(12Xf 5.5.132X该环生成的新搜索方向为：

18、 5.021.31021XS对 进行有效性判别：1S反射点 251.321024X3)(101f .7)(22f 7)(143Xf，41f 5.0)(212 故最大下降量 1m故： 和 均成立13f 2312132 )()( fff m方向 可用S以 为起点，沿 方向作一维搜索：12X1S5.0123.5.31213由 得)()(min1213Sff 4/故，本轮寻优的终点为： 7.831X做收敛性判别：，应继续搜索2017.8.X下一轮寻优过程的起点为： 7.18320X下一轮寻优过程的搜索方向组为： ),(2Se第 4 章 约束优化方法约束优化方法要求大家重点掌握惩罚函数法，包括内点法、外点法、混合法。一、外点法构造惩罚函数：