最优化计算方法(工程优化)第4章

《最优化计算方法(工程优化)第4章》由会员分享，可在线阅读，更多相关《最优化计算方法(工程优化)第4章（164页珍藏版）》请在文档大全上搜索。

1、 最优性条件最优性条件 最速下降法最速下降法 牛顿法及其阻尼牛顿法牛顿法及其阻尼牛顿法 共轭方向法共轭方向法 共轭梯度法共轭梯度法 变尺度法（变尺度法（DFP算法和算法和BFGS算法）算法） 目的是找目的是找 中的一点中的一点 ，使对，使对 ，均有，均有 ，称，称 为为(1)的全局极小点。的全局极小点。 min( ):(1)nf xfRR无约束最优化问题：无约束最优化问题：*()( )f xf xnR*xnxR 求解求解 (1)的计算方法称为的计算方法称为无约束最优化方法无约束最优化方法。*x( ),min( )min( ),( ),.nx Dx Rf xxDf xF xF xothers其中

2、 无约束最优化方法应用广泛，理论也比较成熟；无约束最优化方法应用广泛，理论也比较成熟； 可将约束优化问题转化为无约束优化问题来处理；可将约束优化问题转化为无约束优化问题来处理；解析法无约束优化方法直接法：利用函数的一阶或二阶导数的方法：利用函数的一阶或二阶导数的方法收敛速度快，需要计算梯度或者收敛速度快，需要计算梯度或者Hesse矩阵矩阵：仅利用函数值的信息，寻找最优解：仅利用函数值的信息，寻找最优解不涉及导数，适用性强，但收敛速度慢不涉及导数，适用性强，但收敛速度慢可求得目标函数的梯度时使用解析法可求得目标函数的梯度时使用解析法在不可能求得目标函数的梯度或偏导数时使用直接法在不可能求得目标函

3、数的梯度或偏导数时使用直接法本章介绍解析法本章介绍解析法 所谓所谓最优性条件最优性条件，是指最优化问题的最优解所要满足的，是指最优化问题的最优解所要满足的必要条件或充分条件必要条件或充分条件。 这些条件对于最优化算法的建立和最优化理论的推导都是这些条件对于最优化算法的建立和最优化理论的推导都是至关重要的。至关重要的。 解析法要用到目标函数的梯度或者解析法要用到目标函数的梯度或者Hesse矩阵，容易想到矩阵，容易想到利用一阶必要条件将无约束优化问题转化成一个梯度为利用一阶必要条件将无约束优化问题转化成一个梯度为0 0确定确定的方程组。的方程组。 这里用到的一阶必要条件就是最优性条件。这里用到的一

4、阶必要条件就是最优性条件。 设设 ，若，若 为为 的局部极小点，且在的局部极小点，且在 内连续可微，则内连续可微，则 *()0.f x:nf RRx( )f x( *)Nx*x xf 若若 为为 的局部极小点，且在的局部极小点，且在 内内 二次连续二次连续可微，则可微，则 半正定。半正定。 *xN xf*2*()0,()f xf x 设设 ，若在，若在 内内 二次连续可微，且二次连续可微，且 正定，则正定，则 为为 的严格局部极小的严格局部极小 点。点。 如果如果 负定，则负定，则 为为 的严格局部极大点。的严格局部极大点。*()0,f x:nf RRx( )f x( *)Nx 2f x( )

5、f x 2f xx( )f x 设设 是凸函数且在是凸函数且在 处连续可微，则处连续可微，则 为为 的全局极小点的充要条件是的全局极小点的充要条件是 设设 是严格凸函数且在是严格凸函数且在 处连续可微，若处连续可微，若 则则 为为 的唯一全局极小点。的唯一全局极小点。*()0,f x:nf RRx( )f xxx( )f x*()0.f x:nf RRx利用最优性条件求解下列问题：利用最优性条件求解下列问题：令令即即：得到驻点：得到驻点：利用二阶条件利用二阶条件判断驻点是否判断驻点是否是极小点是极小点 332122111min33f xxxxx22122121,2,ffxxxxx 0,f x2

6、12221020 xxx 12341111,.0202xxxx 利用一阶条件利用一阶条件求驻点求驻点函数函数的的Hesse阵：阵：在点在点处的处的Hesse阵依次为：阵依次为：利用二阶条件利用二阶条件判断驻点是否判断驻点是否是极小点是极小点 f x234111,.202xxx 12220022xf xx1234,x x x x 2120,02f x22342020,.0202f xf x2220,02f x11,0 x 的行列式小于的行列式小于0 0； 2120,02f x232002f x222002f x242002f x是正定矩阵；是正定矩阵；是负定矩阵；是负定矩阵；是鞍点；是鞍点；14

7、,x x是极小点；是极小点；2x是极大点。是极大点。3x： 迭代点沿某方向产生根据迭代点是否沿某个方向产生信赖域方法： 迭代点在某区域内搜索产线搜索方法生 对某些较简单的函数，这样做有时是可行的；对某些较简单的函数，这样做有时是可行的； 但对一般但对一般n元函数元函数 f(x) 来说，由条件来说，由条件 得到的是一个得到的是一个非线性方程组，解它相当困难。非线性方程组，解它相当困难。 为此，常直接使用迭代法。为此，常直接使用迭代法。( )0f x:1kk(1) 选定某一初始点选定某一初始点，并令，并令(2) 确定搜索方向确定搜索方向(3) 从从出发，沿方向出发，沿方向求步长求步长，以产生下一个

8、迭代点，以产生下一个迭代点(4) 检查得到的新点检查得到的新点是否为极小点或近似极小点。是否为极小点或近似极小点。，转，转(2)继续进行迭代。继续进行迭代。 在以上步骤中，选取步长在以上步骤中，选取步长可选用精确一维搜索或者非精确一可选用精确一维搜索或者非精确一维搜索，维搜索， 下降方向的选取正是下面我们要介绍的，下降方向的选取正是下面我们要介绍的，下降方向选取的不下降方向选取的不同，得到不同的算法。同，得到不同的算法。若是，则停止迭代。若是，则停止迭代。否则，令否则，令1x:1.k .kdkxkdk+1.kx+1kx从而得到第从而得到第 k+1次迭代点，即次迭代点，即步长步长 由精确一维搜索

9、得到。由精确一维搜索得到。k负梯度方向负梯度方向 这是函数值减少这是函数值减少最快的方向最快的方向 假设假设 f 连续可微，连续可微，()kkdf x 0()min()kkkkkf xdf xd1+()kkkkkkkxxdxf x负梯度方向负梯度方向 是函数值减少最快的方向是函数值减少最快的方向 ？令令 是单位长度的向量，是单位长度的向量， P是什么方向时，函数值是什么方向时，函数值 下降最快？也就是下降最快？也就是p是什么方向时，是什么方向时， 取得最小值？取得最小值？ 当当 时，时， 最小，最小值为最小，最小值为 ，此时由，此时由 可得可得 ()kkdf x p1,0,p()( )+( )

10、( )Tf xpf xf xpo()f xp( )Tf xp( )( )cos( ),)Tf xpf xpf xp cos( ),)1f xp ( )Tf xp( )f x ( )( )Tf xpf x ( )( )f xpf x 最速下降法是求最速下降法是求多元函数极值多元函数极值的的最古老最古老的数值算的数值算法，早在法，早在1847年法国数学家年法国数学家Cauchy提出该算法，后来提出该算法，后来Curry作了进一步的研究。作了进一步的研究。 该方法直观，简单，计算方便，而且后来的一些新的该方法直观，简单，计算方便，而且后来的一些新的有效的方法大多数是对它的改进，或受它的启发而得到有效

11、的方法大多数是对它的改进，或受它的启发而得到的。的。1x:1k (), *kkf xxx()kkdf x (1) 选定某一初始点选定某一初始点， 并令并令(2) 若若 ，否则转（，否则转（3）；）； 由精确一维搜索确定步长步长由精确一维搜索确定步长步长 ，即由一个极小化，即由一个极小化问题求得最佳步长问题求得最佳步长0(3)kmin()kkf xd1,1,kkkkxxdkk令令 转（转（2）。）。算法框图算法框图x1, 0, k=1| f(xk ) |0得得 xk+1=x(k)+kdkk=k+12212121min( )224 ,f xxxx xx111+4+=12xd，11( )=+=1+4