最优化方法复习

第1章最优化问题的基本概念§1.1最优化的概念最优化就是依据最优化原理和方法，在满足相关要求的前提下，以尽可能高的效率求得工程问题最优解决方案的过程。§1.2最优化问题的数学模型1.最优化问题的一般形式qvxxxhpuxxxgtsxxxfxxxfindnvnunn,,2,10),,,(,,2,10),,,(..),,,(min,,,212121212.最优化问题的向量表达式0)(0)(..)(minXHXGtsXfXfind式中：TnxxxX],,,[21TpXgXgXgXG)](,),(),([)(21TpXhXhXhXH)](,),(),([)(213.优化模型的三要素设计变量、约束条件、目标函数称为优化设计的三要素！设计空间：由设计变量所确定的空间。设计空间中的每一个点都代表一个设计方案。§1.3优化问题的分类按照优化模型中三要素的不同表现形式，优化问题有多种分类方法：1按照模型中是否存在约束条件，分为约束优化和无约束优化问题2按照目标函数和约束条件的性质分为线性优化和非线性优化问题3按照目标函数个数分为单目标优化和多目标优化问题4按照设计变量的性质不同分为连续变量优化和离散变量优化问题第2章最优化问题的数学基础§2.1n元函数的可微性与梯度一、可微与梯度的定义1.可微的定义设)(Xf是定义在n维空间nR的子集D上的n元实值函数，且DX0。若存在n维向量L，对于任意n维向量P，都有0)()(lim000PPLXfPXfTP则称)(Xf在0X处可微。2.梯度设有函数)(XF，TnxxxX],,,[21，在其定义域内连续可导。我们把)(XF在定义域内某点X处的所有一阶偏导数构成的列向量，定义为)(XF在点X处的梯度。记为：TnkxFxFxFXF,,,)(21梯度有3个性质：⑴函数在某点的梯度方向为函数过该点的等值线的法线方向；⑵函数值沿梯度方向增加最快，沿负梯度方向下降最快；⑶梯度描述的只是函数某点邻域内的局部信息。§2.2极小点及其判别条件一、相关概念1.极小点与最优解设)(Xf是定义在n维空间nR的子集D上的n元实值函数，若存在DX*及实数0，使得)(),(**XXDXNX都有)()(*XfXf，则称*X为)(Xf的局部极小点；若)()(*XfXf，则称*X为)(Xf的严格局部极小点。若DX，都有)()(*XfXf，则称*X为)(Xf的全局极小点，若)()(*XfXf，则称*X为)(Xf的全局严格极小点。对最优化问题0)(0)(..)(minXHXGtsXfXfind而言满足所有约束条件的向量TnxxxX],,,[21称为上述最优化问题的一个可行解，全体可行解组成的集合称为可行解集。在可行解集中，满足：)(min)(*XfXf的解称为优化问题的最优解。2.凸集和凸函数凸集：设nRD，若对所有的DXX21、，及]1,0[，都有DXX21)1(，则称D为凸集。凸函数：设1:RRDfn，D是凸集，如果对于所有的DXX21、，及]1,0[，都有)()1()(])1([2121XfXfXXf，则称)(Xf为D上的凸函数。二、局部极小点的判别条件驻点：设)(Xf是定义在n维空间nR的子集D上的n元实值函数，*X是D的内点，若0)(*Xf，则称*X为)(Xf的驻点。局部极小点的判别：设)(Xf是定义在n维空间nR的子集D上的n元实值函数，具有连续的二阶偏导数。若*X是)(Xf的驻点，且)(*2Xf是正定矩阵，则*X是)(Xf的严格局部极小点。第3章无约束优化方法§3.1下降迭代算法及终止准则一、数值优化方法的基本思想基本思想就是在设计空间内选定一个初始点kX，从该点出发，按照某一方向kS（该方向的确定原则是使函数值下降）前进一定的步长k，得到一个使目标函数值有所下降的新设计点1kX，然后以该点为新的初始点，重复上面过程，直至得到满足精度要求的最优点*X。该思想可用下式表示：kkkkSXX1二、迭代计算的终止准则工程中常用的迭代终止准则有3种：⑴点距准则相邻两次迭代点之间的距离充分小时，迭代终止。数学表达为：kkXX1⑵函数下降量准则（值差准则）相邻两次迭代点的函数值之差充分小，迭代终止。数学表达为：)()(1kkXfXf⑶梯度准则目标函数在迭代点处的梯度模充分小时，迭代终止。数学表达为：)(1kXf三、算法的收敛速度对于某一确定的下降算法，其优劣如何评价？人们通常采用收敛速度来评价。下面给出度量收敛速度的几个概念。1.P阶收敛设序列kX收敛于解*X，若存在常数0P及L、0k，使当0kk时下式：pkkXXLXX**1成立，则称kX为P阶收敛。2.线性收敛设序列kX收敛于解*X，若存在常数0k、L及)1,0(，使当0kk时下式：kkLXX*1成立，则称kX为线性收敛。3.超线性收敛设序列kX收敛于解*X，若任给0都存在00k，使当0kk时下式：**1XXXXkk成立，则称kX为超线性收敛。§3.2一维最优化方法一、确定初始区间的进退法任选一个初始点0x和初始步长h，由此可确定两点01xx和hxx12，通过比较这两点函数值)(1xf、)(2xf的大小，来决定第三点3x的位置。比较这三点函数值是否呈“高——低——高”排列特征，若是则找到了单峰区间，否则向前或后退继续寻求下一点。进退法依据的基本公式：01xxhxx12hxx23具体步骤为：⑴任意选取初始点0x和恰当的初始步长h；⑵令01xx，取hxx12，计算)(1xf、)(2xf；⑶若)()(21xfxf，说明极小点在2x右侧，应加大步长向前搜索。转⑷；若)()(21xfxf，说明极小点在1x左侧，应以1x点为基准反向小步搜索。转⑹；⑷大步向前搜索：令hh2，取hxx23，计算)(3xf；⑸若)()(32xfxf，则)(1xf、)(2xf、)(3xf呈“高——低——高”排列，说明],[31xx即为所求的单峰区间；若)()(32xfxf，说明极小点在3x右侧，应加大步长向前搜索。此时要注意做变换：舍弃原1x点，以原2x点为新的1x点，原3x点为新的2x点。转⑷，直至出现“高——低——高”排列，则单峰区间可得；⑹反向小步搜索（要注意做变换）：为了保证3x点计算公式的一致性，做变换：将原2x点记为新1x点，原1x点记为新2x点，令hh41，取hxx23，转⑸例：用进退法确定函数96)(2xxxf的单峰区间[a，b]，设初始点00x，1h。解：①100hx②4)(9)(10211201xfxfhxxxx③)()(21xfxf说明极小点在2x点右侧，应加大步长向前搜索④令2122hh，取32123hxx则0)(3xf⑤)()(32xfxf说明极小点在3x点右侧，应加大步长向前搜索舍弃原01x的点，令3121xx，则0)(4)(21xfxf令4222hh，取74323hxx则0)(16)(23xfxf)(1xf、)(2xf、)(3xf呈“高——低——高”排列],[31xx为单峰区间，即区间[1，7]即为所求二、黄金分割法黄金分割法是基于区间消去思想的一维搜索方法，其搜索过程必须遵循以下的原则：⑴对称取点的原则：即所插入的两点在区间内位置对称；⑵插入点继承的原则：即插入的两点中有一个是上次缩减区间时的插入点；⑶等比收缩的原则：即每一次区间消去后，单峰区间的收缩率保持不变。设初始区间为[a，b]，则插入点的计算公式为：)(382.01abax)(618.02abax黄金分割法的计算步骤如下：①给定初始区间[a，b]和收敛精度；②给出中间插值点并计算其函数值：)(382.01abax)(1xf)(618.02abax)(2xf；③比较)(1xf、)(2xf，确定保留区间得到新的单峰区间[a，b]；④收敛性判别：计算区间[a，b]长度并与比较，若ab，输出)(21*bax否则转⑤；⑤在保留区间内继承一点、插入一点，转②。例：使用黄金分割法求解优化问题：2.0532)(min2xxxxf，。解：①115.0)(056.0)35(382.03)(382.011xfabax②667.7)(944.1)35(618.03)(618.022xfabax③∵)()(12xfxf∴舍弃（1.944，5]，保留[-3，1.944])3(944.1；④继承原1x点，即115.0)(056.022xfx插入987.0)(111.1)3944.1(382.03)(382.011xfabax∵)()(12xfxf∴舍弃（0.056，1.944]，保留[-3，0.056])3(056.0；继承原1x点，即987.0)(111.122xfx插入306.0)(832.1)3056.0(382.03)(382.011xfabax∵)()(12xfxf∴保留[-1.832，0.056])832.1(056.0；继承原2x点，即987.0)(111.111xfx插入888.0)(665.0)832.1056.0(618.0832.122xfx∵)()(12xfxf∴保留[-1.832，-0.665]如此迭代，到第8次，保留区为[-1.111,-0.940]171.0)111.1(940.0∴999.0)(0255.1)940.0111.1(21**xfx§3.3梯度法一、基本思想对于迭代式kkkkSXX1，当取搜索方向)(kkXfS时构成的寻优算法，称为求解无约束优化问题的梯度法。二、迭代步骤⑴给定出发点kX和收敛精度；⑵计算kX点的梯度)(kXF，并构造搜索方向)(kkXFS；⑶令kkkkSXX1，通过一维搜索确定步长k，即：)(minkkkSXF求得新点1kX⑷收敛判断：若)(1kXF成立，输出1*kXX、)()(1*kXFXF，寻优结束；否则令1kk转⑵继续迭代，直到满足收敛精度要求。三、梯度法的特点梯度法寻优效率受目标函数性态影响较大。若目标函数等值线为圆，则一轮搜索就可找到极致点；若当目标函数等值线为扁椭圆时，收敛速度则显著下降。梯度法中相邻两轮搜索方向相互垂直。§3.4牛顿法牛顿法分为基本牛顿法和阻尼牛顿法两种。对于迭代式kkkkSXX1，当取1k且搜索方向)()]([12kkkXfXfS时构成的寻优算法，称为求解无约束优化问题的基本牛顿法；对于迭代式kkkkSXX1，取搜索方向)()]([12kkkXfXfS，k为从kX出发、沿牛顿方向做一维搜索获得的最优步长，所构成的寻优算法，称为求解无约束优化问题的阻尼牛顿法。搜索方向)()]([12kkkXfXfS称为牛顿方向。这里需要注意的是会求海塞阵的逆矩阵。§3.5变尺度法我们把具有)(1kkkkkXfAXX迭代模式的寻优算法称为变尺度法。其搜索方向表达式为：)(kkkXfAS，称为拟牛顿方向，其中kA称为变尺度矩阵。在迭代开始的时候，IA0；随着迭代过程的继续，)()]([12kkkXfXfA。因此，变尺度法从梯度法出发，随着迭代过程的继续最终趋向于牛顿法。§3.6共轭梯度法一、共轭方向的概念设H为对称正定矩阵，若有两个n维向量1S和2S，满足021SHST，则称向量1S与2S关于矩阵H共轭，共轭向量的方向称为共轭方向。若有一组非