04 无约束优化方法

《04 无约束优化方法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、1第四章无约束优化方法24.1概述尽管工程实际中的问题几乎都是约束优化问题，但无约束优化方法仍是优化方法中最基本的组成部份，因为解约束问题的一些有效方法就是将约束问题转化为无约束问题求解。何况还有很多问题本身就是无约束问题，人们对无约束优化方法研究也比较成熟。解无约束优化问题的一类方法是需利用函数的一阶或二阶导数，它们要充分利用函数的解析式子故称为解析法(间接法)。另一类方法在迭代过程中只需计算函数值，故称直接法。相对直接法而言解析法又称间接法。因为解析法充分利用了函数的解析性质，所以它们的收敛速度多数比直接法快，但可靠性一般较低。34.2最速下降法(GradientMethod)一.基

2、本思想梯度方向是函数值变化率最大的方向：沿着梯度方向函数值上升最快;沿负梯度方向函数值下降最快。用负梯度方向作为搜索的方向，即:或用单位负梯度矢量来表示这种方法是用函数变化率最大的方向作为搜索方向，又称最速下降法。二、迭代公式4或式中，步长λk可以任选，只要保证f(X(k+1))

3、初始点要求不高，即使从一个不太好的初始点出发，往往也能收敛到局部极小点。缺点：收敛的速度慢。原因：最速下降是函数值在某一点的变化率而言，是一个局部的性质，从全局来看并不是最速下降方向。因此梯度法的搜索路线呈直角锯齿形状，所得到的搜索点为绕道逼近最优点的，除非目标函数是圆。s64.3牛顿类法(Newton’sMethod)一.迭代公式及特点1.迭代公式f(X)在迭代点X(k)具有一阶、二阶的连续偏导数，则可将其展开成Taylor级数，并略去高于二次的项，得到：二次函数φ(X)的极值点如果将X作为一个逼近点X(k+1),牛顿法的一般迭代公式式中如果f(X)是正定二次函数，则H(X)是个常数矩

4、阵，逼近式X(k)=X*是准确的，由X(k)出发只要迭代一次可得到极小点。72.特点(1).收敛的速度快，即使到了最优点邻域时也很快收敛于函数的局部最优点。(2).采用定步长迭代，因而就不能保证每次迭代中目标函数是下降的。原因：φ(X)仅为目标函数f(X)在X(k)点附近的近似表达式。X(k+1)点是φ(X)在牛顿方向上的极小点，而非原函数的极小点。解决办法：阻尼牛顿法。123450123-1-2FCDABE8二.阻尼牛顿法1.迭代公式沿牛顿方向-[H(X(k))]-1f(X(k))作一维搜索,迭代公式：其中λk使在f(X)的Hessian矩阵H(X(k))处处正定的情况下，阻尼牛顿法能

5、保证每次迭代函数值有所下降。即保持了牛顿法收敛快的特性，又不要求初始点选得很好。2.程序框图三、有关牛顿法的讨论1.不能保证每次迭代函数值都下降。原因：Hessian矩阵不定。92.若Hessian矩阵奇异,其逆阵不存在,就不能构成牛顿方向，迭代无法进行。3.构造牛顿方向较困难。是否能找到另一种更好的方法？a.能像梯度法那样，只需计算目标函数的一阶导数，对初始点的要求不高，能较好的突破函数的非二次性而迅速趋近于极值点；b.同时又像牛顿法那样，一但迭代点进入极值点的邻近区域时很快地收敛于最优点。104.4坐标轮换法(CyclicCoordinateMethod)一.基本思想降维的思想，将一

6、个n维问题转化为一系列的一维优化问题来求解。每次将n-1个变量固定，只对一个变量作一维搜索。进行一维搜索找到X1(1)进行一维搜索找到X2(1)进行一维搜索找到Xn(1)到此完成一轮迭代，X的上角标表示迭代的轮次，下角标表示坐标轴的序号。每次都是以前一次搜索的终点作本次一维搜索的起点，一轮迭代完后又重头开始直至收敛，故此法又称变量轮换法(AlternatingVariableMethod)。二、步长的确定1、随机选取法，保证函数值下降。112、最优步长Xi=Xi-1+λiEi3、加速步长法在每次一维搜索中,都是以λ=λ0开始,随后在函数值下降的情况下2λ0,4λ0,…倍增的速度加大步长，

7、直至函数值不再下降，取其前步长为最终步长。12三.迭代过程及框图13四.坐标轮换法的讨论1、坐标轮换法具有程序简单，易于掌握的优点，但它的计算效率较低，因此它虽然步步在登高，但相当于沿两个垂直方向在爬山，路途迂迴曲折，收敛很慢，因此它适用于维数较低(一般n<10)的目标函数求优。2、有“脊线”的目标函数等值线的情形,沿坐标轴方向函数值不一定下降。0pA脊线14五、练习用最优步长法求解f(X)=(x1-2)4+(x1-2x2)2的极小