无约束最优化梯度方法

1、第三章无约束最优化的梯度方法1. 最速下降法假定我们已经迭代了 一次，获得了第色个迭代点皿。从勺出发，显然应沿下 降方向进行，因为负梯度方向是最速下降方向，因此沿负梯度方向应该是有利 的。因此，取搜索方向I I 。此时有：I如将该方法应用于二次函数I = I，则可求出21的显式表达式。2. Newton 法适用条件：如果目标函数回 在叫上具有连续的二阶偏导数，其 Hesse矩 阵 正定。3. 共轭方向法与共轭梯度法1 共轭方向法定义1:设亍是E对称正定矩阵。若耳维空间中非零向量系1 1 满足I x I ， I =-= M,则称 | I 是电共轭的，或称_二|的方向是共轭方向。定理1：若非零向量

2、系I是共轭的，则这 个向量线性无关。推论：在冋维空间中，互相共轭的非零向量的向量个数不超过 匡。定义2:设I . 是线性无关的向量系，匚三！是任意实数。对于任意指定的 凹,称形式为I N I的向量集合称为由点1和向量系I I 所生成的线性流形，记为I 一 。定理2:假设： 慎为b对称正定矩阵 非零向量I是共轭向量系； 对二次目标函数I = | 顺次进行如下E次直线搜索：I I ，匕 ，其中凹是任意选定的初始点。则勺是二次函数在线性流形I上的极小点。证明：前面已经证明n=n由条件可知|上式左乘因后再在两边加上丄，得：I = 证明:按条件,，则存在一组数使得同样，对于任意上面两式相减得由结论可知因

3、为因是正定的，因此因是在线性流行上的极小点。当q时，线性流行1/就是整个耳维空间二了，因此此时凶就是中的极小点。共轭方向法:已知：具有正定矩阵 的二次目标函数和终止限 选定初始点凶和具有下降方向的向量 凶；置一国 作直线搜索k=k+1二次函数的直线搜索:共轭向量系I的构造方法：先选定-个线性无关的向量系 I = I ，令I ” I设已求得共轭向量 I = | ，现在来求 凹为使凶与共轭，应有:由此解得：于是共轭方向法的适用范围：可用于非二次函数，首先通过Taylor公式用二次函数来逼近非二次函数。其次，可用 旦1来构造共轭向量系，这要求 勺充分地靠近弓。2共轭梯度法初始共轭向量凶恰好取为初始点

4、处的负梯度 ，以下各共轭方向第迭代点叵处的负梯度巨与已得到的共轭向量的线性组合来确定。因为该方法每一个共轭向量都是依赖于迭代点处的负梯度构造出来的，所以称为共轭梯度法。设已求得共轭向量,现在来求日,知和弓是线性无关的，取考虑回与列目共轭，需满足:现在证明同除与可共轭外，还与于是有:I 共轭。依次计算因为 y 是共轭向量，因此因为从共轭向量系构建方法可以看出，迭代点处的梯度是共轭向量系的线性组LJ因此有:从而证明了 与 I共轭。共轭梯度法在非二次函数中的应用：为了把共轭梯度法应用在非二次函数中，有必要消去表达式1 =中的目。因为I 一 I因为=I ， 根据习表达式的不同，可得到四种共轭梯度算法。

5、最常米用的是第二种表达方式。4.变尺度法1基本想法考虑Newt on迭代公式I 一 1, W!变尺度法就是要消除这个迭代公式中的 Hesse逆矩阵，为此拟采用某种 近似矩阵匸斗 来替换它，即构造一个矩阵序列去逼近凹。因此，迭代公式为L 1 |其中可通过从日出发沿1作直线搜索来确定。为使回确实与近似并具有容易计算的特点，对叵|附加下列条件。 要求工对称正定，保证迭代公式具有下降性质。如凹T对称正定，则，保证迭代公式具有下降性质。 要求丨之间的迭代具有简单的形式。I ，其中 称为校正矩阵，上式称为校正公式|必须满足拟Newton条件一对于二次函数 而言,有:上面两式相减有：|如憾的逆存在,则有IL

6、 = I成立,表明卜能很好近似二I。如记 AlJ ， I，于是拟Newton条件可写为：I =拟牛顿法算法：已知：目标函数包 及其梯度回，终止准则。 选定初始点；计算I，选定初始矩阵L。 计算搜索方向I 。 作直线搜索I 。 如满足终止准则，停机。 计算 I I 。 亠L转。2校正公式(1对称秩1算法(SR1法校正公式取为I其中 是 维待定非零向量，是待定常数，因为校正公式必须满足拟牛顿条件，于是有：I。,于是校正公式为: 对称秩1算法的性质:性质1:设将SR1法施用于具有对称正定矩阵的二次函数，如果 初始矩阵百是对称的。 迭代点是互异的。当习时， 1那么有：(I 此算法所生成的搜索方向一三I是互相卫共轭的。(II 对 Q , I 1性质2:若性质1的条件都满足，并且经过次迭代才求到极小点，则考虑如下形式的校正公式因为校正公式必须满足拟牛顿条件，于是有:(2DFP算法再令凹，1于是有：| x |校正公式为:DFP算法性质:性质1:设将DFP法施用于具有对称正定矩阵的二次函数，如果 初始矩阵百是对称的。 迭代点是互异的。那么有：(I 此算