第三章--无约束最优化的梯度方法

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

1、第三章无约束最优化的梯度方法1.最速下降法假定我们已经迭代了次，获得了第个迭代点。从出发，显然应沿下降方向进行，由于负梯度方向是最速下降方向，因此沿负梯度方向应该是有利的。因此，取搜索方向。此时有：如将该方法应用于二次函数，则可求出的显式表达式。2.Newton法适用条件：如果目标函数在上具有连续的二阶偏导数，其Hesse矩阵正定。基本想法：考虑从到的迭代过程。在点处用二次函数来逼近，即：3.共轭方向法与共轭梯度法1)共轭方向法定义1:设是对称正定矩阵。若维空间中非零向量系满足，,则称是共轭的，或称的方向是共轭方向。定理1:若非

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

3、论①可知由于是正定的，因此是在线性流行上的极小点。当时，线性流行就是整个维空间了，因此此时就是中的极小点。共轭方向法：已知：具有正定矩阵的二次目标函数和终止限。①选定初始点和具有下降方向的向量；置。②作直线搜索。③判别是否满足：若满足，停机。④提供共轭方向，使得，⑤k=k+1二次函数的直线搜索：共轭向量系的构造方法：先选定个线性无关的向量系，令设已求得共轭向量，现在来求令为使与共轭，应有：，由此解得：于是共轭方向法的适用范围：可用于非二次函数，首先通过Taylor公式用二次函数来逼近非二次函数。其次，可用来构造共轭向量系，这要求

4、充分地靠近。2)共轭梯度法初始共轭向量恰好取为初始点处的负梯度，以下各共轭方向由第迭代点处的负梯度与已得到的共轭向量的线性组合来确定。因为该方法每一个共轭向量都是依赖于迭代点处的负梯度构造出来的，所以称为共轭梯度法。设已求得共轭向量，现在来求由，知和是线性无关的，取考虑与共轭，需满足：于是有：现在证明除与共轭外，还与共轭。对依次计算由于是共轭向量，因此，因为又因为,从共轭向量系构建方法可以看出，迭代点处的梯度是共轭向量系的线性组合。，，因此有：，,从而证明了与共轭。共轭梯度法在非二次函数中的应用：为了把共轭梯度法应用在非二次函数

5、中，有必要消去表达式中的。由于因为，根据表达式的不同，可得到四种共轭梯度算法。最常采用的是第二种表达方式。4.变尺度法1)基本想法考虑Newton迭代公式，变尺度法就是要消除这个迭代公式中的Hesse逆矩阵，为此拟采用某种近似矩阵来替换它，即构造一个矩阵序列去逼近。因此，迭代公式为其中可通过从出发沿作直线搜索来确定。为使确实与近似并具有容易计算的特点，对附加下列条件。①要求对称正定，保证迭代公式具有下降性质。如对称正定，则，保证迭代公式具有下降性质。②要求之间的迭代具有简单的形式。，其中称为校正矩阵，上式称为校正公式。③必须满足

6、拟Newton条件对于二次函数而言,有:上面两式相减有:如的逆存在,则有成立,表明能很好近似。如记，，于是拟Newton条件可写为：拟牛顿法算法：已知：目标函数及其梯度，终止准则。①选定初始点；计算，选定初始矩阵。②计算搜索方向。③作直线搜索。④如满足终止准则，停机。⑤计算。⑥，转②。2)校正公式(1)对称秩1算法(SR1法)校正公式取为其中是维待定非零向量，是待定常数，由于校正公式必须满足拟牛顿条件，于是有：。取，于是校正公式为：对称秩1算法的性质：性质1:设将SR1法施用于具有对称正定矩阵的二次函数，如果①初始矩阵是对称的。

7、②迭代点是互异的。③当时，那么有：(Ⅰ)此算法所生成的搜索方向是互相共轭的。(Ⅱ)对，性质2:若性质1的条件都满足，并且经过次迭代才求到极小点，则。(2)DFP算法考虑如下形式的校正公式由于校正公式必须满足拟牛顿条件，于是有：取，再令，于是有：，校正公式为：DFP算法性质：性质1:设将DFP法施用于具有对称正定矩阵的二次函数，如果①初始矩阵是对称的。②迭代点是互异的。那么有：(Ⅰ)此算法所生成的搜索方向是互相共轭的。(Ⅱ)对，性质2:若性质1的条件都满足，并且经过次迭代才求到极小点，则。性质3:在DFP算法中，若初始矩阵是对称正

8、定的，则中每一个都是正定的。