文档介绍：螄第三章牛顿法螁芁§、最速下降法袅在极小化算法中,若每次都以迭代点处的负梯度方向为搜索方向,产生的算法称为最速下降法,它是无约束最优化算法中最简单、最基本的算法。衿算法描述:蚀给出初始点,允许误差,;肇计算,若,Stop令;蚂由一维搜索确定步长因子,使得节腿令,,goto2).袇蚄二、,则最速下降算法产生的点列的每个聚点均为驻点。蕿证明:设是的一个聚点,则存在子序列,使得薈螅令,由,知是收敛序列,故有界,。,且,则对任何给定的初始点,最速下降算法或有限终止,或,或。蒈证明:不妨设,。,由为单调下降序列,则要么袇,要么。薅最速下降算法若采用不精确一维搜索,仍有下列总体收敛性定理。,则采用不精确一维搜索得到的点列的每个聚点均为驻点。莂证明:。薀注:1);芅2)最速下降算法的主要优点是方法简单、直观,有好的总体收敛性,但收敛很慢。蒃蒀三、,其中为对称正定矩阵,,分别为的最大与最小特征值。设是最优解,则最速下降算法的收敛速度至少是线性的,且下面的界成立:薄,袂其中(为矩阵的条件数)。荿证明:由,有。故螆薅其中使,羁若设,袈其中。则有蒆,而,莃利用这些,可知莃,(要求)芈芇设是的特征值,而是对应得标准特征向量(两两正交的单位向量)。蒄令,则上式可进一步表示为:蒁蚇(将作用到内每一项)羇蒅(由是标准正交向量组)薀对,可适当选取,使。莁事实上,只须令螈芃即可求得羂从而。螀显然单调上升。由,及,即得。,并注意到是正定二次函数(),则有。蒃再由为严格凸二次函数(正定二次型),故当且仅当时,,,则有膃薁从而定理第一式得证。芇下面再证定理第二式,记,。由是对称正定的,故有蚄蒃由,则袈故有,蚆注意到:莄因而有薄最后得(其中)。芁这表明:最速下降算法至少具有线性收敛速度。(Kantorovich不等式)设是阶对称正定矩阵,和分别为其最大和最小特征值,则,有。节证明:参见袁亚湘等《最优化理论与方法》第三章附录,略。荿以上对特殊形式的二次函数的收敛速度进行讨论,对一般的二次函数衿袅利用Kantorovich不等式可得类似的结论,其证明思路如下:设是极小点,则满足莃蚂且可表示为芈记,薅则与仅相差一个常数,它们有相同的最优解,且使用最速下降算法时,每次迭代方向产生的迭代序列均完全相同。现在考察对的极小化,这时最速下降算法的迭代公式为:膀(这里为最优步长因子)袀其中。直接计算可得:蚈(由Kantorovich不等式)莆故有:(1)节由(1)即得:(或)。由正定,当且仅当时,羈肇利用一致凸性,可证必有:。这表明:算法产生的点列是整体收敛到的。肆由(1)有:(2)芃注意到:,芁由(2)有薆(3)袆再令(),则肁,葿注意到羆即有:,薇从而有:,(令)膂最后得:,定理证毕。螁当目标函数为非二次函数时,最速下降算法的收敛速度依然是线性的。,若最速下降算法产生的点列收敛于,则收敛速度至少是线性的。肃膃§、牛顿算法的基本思路聿牛顿算法的基本思路是:利用目标函数在当前迭代点处的二次近似的极小点作为的近似极小点。设是当前迭代点,正定,则螃羁记,其中,肈极小化得