《第7讲无约束优化方法.pdf》由会员分享，可在线阅读，更多相关《第7讲无约束优化方法.pdf（22页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第七讲无约束优化一阶方法 1.最速下降法的由来 最速下降法 考虑无约束问题 其中，函数具有一阶连续偏导数. ),(minxf, n Rx 人们在处理这类问题是，总希望从某一点出发， 选择一个目标函数值下降最快的方法，以利于尽快 达到极小点. 基于此愿望，1847年法国数学家 Cauchy提出了最速下降法. 后来，Curry等人作了 进一步的研究，得到现在众所周知的一种最基本的 方法. 2.最速下降法的方向选择 最速下降法利用负梯度为方向 作为搜索方向. 设在附近连续可微，为搜索方向 向量，由泰勒展开式得 那么目标函数在处沿着方向下 降的变化率如下所示： )( kk xfd )(xf k x k
2、 d )( kk xfg , 0),()()(odgxfdxf k T kkkk )(xf k xk d 2.最速下降法的方向选择 其中为与夹角. 要使得变化率最小， 只有当值为时才能达到，也就是 取得负梯度方向. )()( lim 0 kkk xfdxf )( lim 0 odg k T k cos k T kk T k dgdg k g k d k d1 )(xf )(xf cos 2.最速下降法的方向选择 事实上，最速下降方向也可以这样来考虑。因为 目标函数在处沿方向的变化率为， 故最速下降的单位方向是如下非线性规划问题 的解. 根据 Schwartz 不等式，有 去掉绝对值符号，可以得
3、到. 由上式知，当时等号成立. 因此负梯 度方向为最速下降方向. dg T k )(xf k xd d d min dg T k . .ts1d kk T k gdgdg k T k gdg kk ggd 3.最速下降法计算步骤 1. 给定初始点，容许误差，令 2. 计算搜索方向; 3. 若，则停止计算，输出作为近似 最优解；否则从出发，沿进行一维线搜 索，确定步长因子，使得 4. 令，令，转步骤2. n Rx 0 0 1:k )( kk xfd k d k x k x k d k kkkk dxx 11: kk 0 ()min() k kkkkkk f xdf xd 4.最速下降法的锯齿现象
4、 由步骤3，为求出从出发沿方向的极小点， 令 由此得出. 即方向与正交. 这表明迭代产生的序列所循路径是“之”字 形的。当接近极小点时，每次迭代移动的步长很 小，这样就出现了锯齿现象，因此影响了收敛速 率. k x k d ()()0 T kkkkk f xdd 0)()( 1 k T k xfxf )( 11 kk xfd )( kk xfd k x 5.最速下降法的总结 1. 初始点可任选，每次迭代计算量小，存储量少， 程序简短. 即使从一个不好的初始点出发，开 始的几步迭代，目标函数下降很快，然后慢慢 逼近局部极小点. 2. 任意相邻两点的搜索方向是正交的，它的迭代 路径为“之”字形逼近
5、. 6.例题（练习） 利用最速下降法求解问题 初始点，. 解：第1次迭代 . 目标函数在点处的梯 度为 令搜索方向为， 从出发，沿方向进行一维线搜 索，求步长，即 2 2 2 1 2)(minxxxf T x) 1 , 1 ( )1( 10 1 2 1 2 4 )( x x xf 2 4 )( )1()1( xfd 10 1 52 )1( d )(xfx T x) 1 , 1 ( )1( )1( d 1 6.例题（练习） 令，解得. 从而有 第2次迭代 .在点处的最速下降方向为 ， 从出发沿搜索方向进行一维搜索： )2( x 98 94 )( )2()2( xfd 10 1 5 5 4 )2(
6、 d )(xf )2( x )2( d 1 (1)(1) 11 0 min ()()f xd 1 ()0 18 5 1 94 91 )1( 1 )1()2( dxx 6.例题（练习） 令，解得. 从而有 第3次迭代 ， 再从出发，沿进行一维线搜索 ： )3( x 1 2 27 4 )( )3()3( xfd 10 1 5 27 4 )3( d )3( d 2 (2)(2) 22 0 min ()()f xd 2 ()0 12 5 2 1 1 27 2 )2( 2 )2()3( dxx 3 (3)(3) 33 0 min ()()f xd 6.例题（练习） 令，解得. 从而有 这时有 此时已经满
7、足精度要求，得到近似解 实际上，问题的最优解为. 10 1 5 243 8 )( )4( xf 3 ()0 18 5 3 4 1 243 2 )3( 3 )3()4( dxx 4 1 243 2 x T x0 , 0 * 共轭梯度法 1.共轭方向 设是对称正定矩阵，若中的两个方 向和满足 则称这两个方向关于共轭，或称它们关于 正交. A nn n R 1 d 2 d 0 21 Add T A A 无约束最优化方法的核心问题是选择搜索方向. 在这一节，我们讨论基于共轭方向的一种算法： 共轭梯度法. 为此先引入共轭方向的概念. 共轭梯度法 1.共轭方向 若是中个方向，它们两 两关于共轭，既满足 则
8、称这组方向是共轭的，或者它们为的 个共轭方向. k ddd， , 21, n Rk A kjijiAdd j T i , 2 , 1, 0 AAk 在上述定义中，如果是单位矩阵，则两个方 向关于共轭等价于两个方向正交. 因此共轭是 正交概念的推广. 实际上如果是一般的对称正 定矩阵，与关于共轭，也就是方向与 正交 . A A A A i d i d j d j Ad 共轭梯度法 2.Fletcher-Reeves共轭梯度法（FR法） 共轭梯度法的基本思想是把共轭性与最速下降法 相结合，利用已知点处的梯度构造一组共轭方向， 并沿这组方向进行搜索，求出目标函数的极小点， 根据共轭方向的基本性质，这
9、种方法具有二次终止 性. 在此我们主要讨论对于二次凸函数的共轭梯度法， 推广到极小化一般函数的情形与此类似. 考虑问题 其中， 是对称正定矩阵， 是常数. cxbAxxxf TT 2 1 )(min n RxAc 共轭梯度法 具体求解方法 1. 首先任意给定一个初始点，计算出目标 函数在这点的梯度，若， 则停止计算；否则，令 沿搜索方向得到点，计算出点的 梯度，若，则利用与构造 第2个搜索方向，再沿搜索； 2. 一般的，若已知点和搜索方向，则从 点出发，沿进行搜索， 得到 其中 1 x )(xf 1 g 0 1 g 111 )(gxfd 1 d 2 x 2 x 2 g 0 2 g2 g 1 d
10、 2 d 2 d k x k d k x k d ）（ 1 1 kkkk dxx 0 ()min() k kkkkkk f xdf xd 共轭梯度法 具体求解方法 与最速下降法类似，可得 根据二次函数的梯度的表达形式可得 可得到步长因子 ()()0 T kkkkk f xdd 0 )( )( 1 k T kkk k T kkk k T k dAdg dbdxA dbAx ）（2 k T k k T k k Add dg 共轭梯度法 具体求解方法 计算在处的梯度，若， 则停止计算；否则，用和构造下一个搜 索方向，并使得和关于共轭。 按此设想，令 上式两端左乘，并令 由此得到 再从出发，沿方向搜索
11、. )(xf 1k x 1k g 0 1 k g 1 k g k d 1k d k d 1k d A ）（3 11 kkkk dgd Ad T k 0 11 k T kkk T kk T k AddAgdAdd ）（4 1 k T k k T k k Add Agd 1k x 1k d 共轭梯度法 具体求解方法 3. 综上分析，在第1个搜索方向取负梯度的前提 下，重复公式（1）（2）（3）（4），就能伴 随计算点的增加，构造出一组搜索方向. 注：利用共轭方向的性质，可知利用FR法得到的 一组搜索方向是关于共轭的。同时，该方法 具有二次终止性，由如下例子也可得到验证. A 3.例题（练习） 利用
12、共轭梯度方法求解问题 取初始点. 解：目标函数在点处的梯度为 第1次迭代. 令 从出发，沿方向进行一维线搜索， 2 2 2 1 2)(minxxxf T x)5 , 5( )1( 2 1 4 2 )( x x xf 20 10 )( )1( 1 )1( xfgd )(xfx T x)5 , 5( )1( )1( d 3.例题（练习） 得 第2次迭代. 在点处，目标函数的梯度 构造搜索方向. 先计算因子： 920 940 2 g )2( x )2( d 18 5 20 10 40 02 )20,10( 20 10 )20,10( )1()1( )1( 1 1 Add dg T T 95 920 )1( 1 )1()2( dxx 1 81 4 )1()1( 2 )1( 1 Add Agd T T 3.例题（练习） 令 从出发，沿方向作一维搜索，得 显然点处目标函数的梯度，已达到 极小点. 此例验证了共轭梯度法的二次终止性. T g0 , 0 3 )2( x 1 4 81 100 )1( 12 )2( dgd 20 9 )2()2( )2( 2 2 Add dg T T 0 0 )2( 2 )2()3( dxx )2( d )3( x T x0 , 0 )3(