《无约束最优化梯度方法.doc》由会员分享，可在线阅读，更多相关《无约束最优化梯度方法.doc（11页珍藏版）》请在三一文库上搜索。
1、第三章无约束最优化的梯度方法1. 最速下降法假定我们已经迭代了 次，获得了第 个迭代点。从 出发，显然应沿下降方向进行，因为负梯度方向是最速下降方向，因此沿负梯度方向应该是有利的。因此，取搜索方向丨。此时有： II如将该方法应用于二次函数X I ，则可求出勺的显式表达式。2. Newton 法适用条件：如果目标函数在 上具有连续的二阶偏导数，其 Hesse矩 阵正定。基本想法：考虑从到的迭代过程。在点处用二次函数来逼近，即：3. 共轭方向法与共轭梯度法1> 共轭方向法定义1：设 是对称正定矩阵。若维空间中非零向量系满I ,二 II ,则称 I是共轭的，或称 I的方向是共轭方向。定理1：若
2、非零向量系I是共轭的，则这 个向量线性无关。推论：在 维空间中，互相共轭的非零向量的向量个数不超过。定义2:设 I 是线性无关的向量系， : 是任意实数。对于任意指定的耐，称形式为的向量集合称为由点目和向量系I 所生成的线性流形，记为 «定理2:假设： 为对称正定矩阵 非零向量 I是共轭向量系； 对二次目标函数 顺次进行如下 次直线搜索:），其中Q是任意选定的初始点。则 ， 亠I 是二次函数在线性流形 «上的极小点。证明：前面已经证明J八由条件可知 上式左乘后再在两边加上，得：I即:J由上式有 丨将所得等式两边左乘，有证明：按条件,则存在一组数 I 使得同样，对于任意.上面
3、两式相减得由结论可知因为 是正定的，因此口是在线性流行 '上的极小点。当 时，线性流行 D就是整个维空间 了，因此此时就是中的极小点。共轭方向法：已知：具有正定矩阵 的二次目标函数 | 和终止限。 选定初始点 和具有下降方向的向量；置亠。 作直线搜索丨。 提供共轭方向丨，使得厂 k=k+1二次函数的直线搜索： 共轭向量系 I的构造方法：先选定个线性无关的向量系 f ，令 一I设已求得共轭向量 '，现在来求3令 U'为使丨与 亠二.共轭，应有：由此解得：H于是共轭方向法的适用范围:可用于非二次函数，首先通过Taylor公式用二次函数来逼近非二次函 数。其次，可用 二J 来
4、构造共轭向量系，这要求 因充分地靠近回2共轭梯度法初始共轭向量也恰好取为初始点处的负梯度I ,以下各共轭方向由第迭代点处的负梯度刮与已得到的共轭向量的线性组合来确定。因为该方法每一个共轭向量都是依赖于迭代点处的负梯度构造出来的，所 以称为共轭梯度法。设已求得共轭向量 匚三I ，现在来求0由二I ，知丨和也是线性无关的，取 D考虑与一共轭，需满足：=于是有： =|现在证明 除与丨共轭外，还与 f共轭。对 I 依次计算0因为 ) 是共轭向量，因此_1, 亠0因为 到又因为 -【,I从共轭向量系构建方法可以看出，迭代点处的梯度是共轭向量系的线性组 合。从而证明了与.F 共轭共轭梯度法在非二次函数中的
5、应用：为了把共轭梯度法应用在非二次函数中，有必要消去表达式因为中的K 1根据表达式的不同，可得到四种共轭梯度算法。最常米用的是第二种表达方式。4.变尺度法1基本想法考虑Newton迭代公式一I , W3变尺度法就是要消除这个迭代公式中的 Hesse逆矩阵丨，为此拟采用某种 近似矩阵 来替换它，即构造一个矩阵序列讨去逼近I。因此，迭代公式为 '其中 可通过从 出发沿 f作直线搜索来确定。为使确实与二近似并具有容易计算的特点，对附加下列条件。 要求对称正定，保证迭代公式具有下降性质。如回对称正定，则一I，保证迭代公式具有下降性质。矩阵，上式称为校正公式”：1必须满足拟Newton条件 对于
6、二次函数 |而言,有：上面两式相减有：j如的逆存在,则有I成立,表明一1能很好近似一I。如记丨，于是拟Newton条件可写为： :拟牛顿法算法：已知：目标函数及其梯度，终止准则。 选定初始点；计算 f，选定初始矩阵-I。 计算搜索方向 作直线搜索I 。 如满足终止准则，停机 计算K。 亠，转2校正公式 (1对称秩1算法(SR1法校正公式取为一 一是待定常数，因为校正公式必须满足拟牛其中 是 维待定非零向量,取 ，于是校正公式为：|对称秩1算法的性质：性质1:设将SR1法施用于具有对称正定矩阵的二次函数，如果 初始矩阵是对称的。 迭代点是互异的。 当二时， 那么有：(I 此算法所生成的搜索方向 I是互相 共轭的。(II 对 一I ,门性质2:若性质1的条件都满足，并且经过次迭代才求到极小点，则IF 。(2DFP算法考虑如下形式的校正公式一 一因为校正公式必须满足拟牛顿条件，于是有:取 II ,II再令W , I于是有：叵,x校正公式为:DFP算法性质:性质1:设将DFP法施用于具有对称正定矩阵的二次函数，如果 初始矩阵 是对称的。 迭代点是互异的。那么有：(I 此算法所生成的搜索方向I是互相 共轭的。(II 对 I ,- I性质2:若性质1的条件都满足，并且经过次迭代才求到极小点，则IF 。性质3:在DFP算法中，若初始矩阵是对称正定的，则中每一个都是正定的。