《最优化方法第四章节B课件》由会员分享，可在线阅读，更多相关《最优化方法第四章节B课件（127页珍藏版）》请在金锄头文库上搜索。
1、第4章无约束最优化方法,主要内容,4.1 最速下降法 4.2 牛顿法 4.3 共轭梯度法 4.4 拟牛顿法,4.1 最速下降法,最速下降法是以负梯度方向作为下降方向的极小化算法, 又称梯度法, 是1874 年法国科学家Cauchy(柯西)提出的. 最速下降法是无约束最优化中最简单的方法,设目标函数f(x)在xk附近连续可微, 且 .将f(x)在xk处Taylor展开 (4.1.1) 记 ，则上式可写为 (4.1.2) 显然, 若 满足 , 则是下降方向, 它使得,当 取定后, 的值越小, 即 的值越大, 函数f(x)在xk处下降量越大. 由Cauchy-Schwartz(柯西-施瓦)不等式 (
2、4.1.3) 可知, 当且仅当dk=-gk时, 最小, 最大, 从而-gk 是最速下降方向. 以-gk为下降方向的方法叫最速下降法,如何选择下降最快的方向？,事实上, 最速下降方向也可以这样来考虑. 因为目标函数f 沿方向d 的变化率是g(xk)Td, 故最速下降的单位方向d是问题 (4.1.4) (4.1.5) 的解 这时 (4.1.6) 其中, 是gk与d之间的夹角 当 时取极值,这时 (4.1.7) 最速下降法的迭代格式为 (4.1.8) 其中步长因子 由线性搜索策略确定.,算法4.1.1 (最速下降法),步1. 给出 步2. 计算dk=-gk; 如果 , 停止. 步3. 由线性搜索求步
3、长因子 . 步4. 计算 步5. k:=k+1, 转步2 .,最速下降法的收敛性,对于最速下降法,k=0, 因而, 利用定理3.4.3立即可知最速下降法是总体收敛的. 定理4.1.2 设 在水平集L=xRn|f(x)f(x0)上存在且一致连续, 则最速下降法产生的序列满足或者对某个k 有gk=0, 或者f(xk)-, gk0. 证明：利用定理3.4.3立得.,最速下降法的总体收敛性定理,定理4.1.3 设函数f(x)二次连续可微, 且 , 其中M是某个正常数.对任何给定的初始点x0, 最速下降算法4.1.1或有限终止, 或 , 或 证明:考虑无限迭代下去的情形, 由定理3.4.2, 有 (4.
4、1.9) 于是 (4.1.10) 两边取极限, 于是, 或者 , 或 .从而定理成立,最速下降法优缺点,优点：程序设计简单，计算工作量小，存储量小，对初始点无要求 缺点：最速下降方向仅是局部性质，对整体而言，下降速度慢，锯齿现象,锯齿现象,数值试验表明, 当目标函数的等值线接近于一个圆(球)时, 最速下降法下降较快; 而当目标函数的等值线是一个扁长的椭球时, 最速下降法开始几步下降较快, 后来就出现锯齿现象, 下降十分缓慢 事实上, 由于精确线性搜索满足 则 (4.1.11) 这表明最速下降法中相邻两次的搜索方向是相互直交的, 这就产生了锯齿形状.越接近极小点, 步长越小, 前进越慢.,最速下
5、降法的锯齿现象,最速下降法的收敛速度,精确线性搜索的最速下降法的收敛速度是线性的 对于极小化正定二次函数, 最速下降法产生的序列满足 (4.1.12) (4.1.13) 其中 和 分别是矩阵G的最大和最小特征值, 是矩阵G的条件数.,在非二次情形, 如果f (x)在x*附近二次连续可微, 正定, 则(4.1.12)也成立.,二次型,n个变量的二次齐次多项式 称为一个n元二次型，简称二次型 三元二次型,二次型的矩阵表示,令 因为 二次型可以写成,系数排列成一个矩阵 二次型矩阵 因为 A是一个对称矩阵. 二次型矩阵都是对称矩阵,令 二次型就可以用矩阵的乘积表示出来,即为,二次型 如果对于任意一组不
6、全为零的实数 都有 就称为正定的. A是一个实对称矩阵，如果 实二次型 是正定的，则A称为正定矩阵.,设 是一个实二次型，如果对于任意一组不全为零的实数 ，都有 就称 是负定的. 如果对于任意一组实数 ，都有 ，就称 是半正定的.,如果对于任意一组实数 ，都有 ，就称 是半负定的. 如果 即不是半正定的，也不是半负定的，就称它是不定的.,设A是实对称矩阵，如果二次型 是负定 的，就称A是负定的； 如果 是半正定的或半负定的，就称A是 半正定的或半负定的.,二次函数,二次函数 其中 在代数学中将特殊的二次函数 称为二次型,Hesse矩阵,设 所有的二阶导数都存在，那么f 的Hesse矩阵即,4.
7、2 牛顿法,牛顿法的基本思想是利用目标函数f(x)在迭代点xk处的二次Taylor展开作为模型函数, 并用这个二次模型函数的极小点序列去逼近目标函数的极小点. 设f(x)二次连续可微，Hesse矩阵 正定 我们在xk附近用二次Taylor展开近似f, (4.2.1) 其中 , 为f ( x) 的二次近似,将上式右边极小化, 即令 (4.2.2) 得: (4.2.3) 这就是牛顿法迭代公式.相应的算法称为牛顿法 令 , 则(4.2.3)也可写成 (4.2.4) 对于正定二次函数, 牛顿法一步即可达到最优解,算法步骤,算法框图,给定初始点x0和精度,停止，输出x0,停止，解题失败,停止，输出x1,
8、Newton法收敛速度非常快具有二次收敛的优点，但它存在下面四个严重的缺点： 1.尽管每次迭代不会使目标函数f(x)上升，但仍不能保证f(x)下降当Hesse矩阵非正定时，Newton法的搜索将会失败 2.对初始点要求严格一般要求比较接近或有利于接近极值点，而这在实际计算中是比较难办的,Newton法有关说明,3.在进行某次迭代时可能求不出搜索方向 4.牛顿方向构造困难，计算相当复杂，除了求梯度以外还需计算Hesse矩阵及其逆矩阵，占用机器内存相当大,对于一般非二次函数, 牛顿法并不能保证经过有限次迭代求得最优解, 但如果初始点x0充分靠近极小点, 牛顿法的收敛速度一般是快的. 下面的定理证明
9、了牛顿法的局部收敛性和二阶收敛速度.,牛顿法收敛定理,定理4.2.1设f(x)二阶连续可微, x*是f(x)的局部极小点, 正定. 假定f(x)的Hesse矩阵 满足Lipschitz条件, 即存在 , 使得对于所有 有 (4.2.5) 其中Gij(x)是Hesse矩阵Gk的(i,j)元素. 则当初始点x0充分靠近x*时, 对于一切k, 牛顿迭代(4. 2.4)有意义, 迭代序列xk 收敛到x*, 并且具有二阶收敛速度.,证明 设hk=xk- x*, .由于f(x)二阶连续可微和(4.2.5), 故利用Taylor公式得到 令h=-hk,得 由于f(x)二次连续可微， 正定, 故当xk充分靠近
10、x*时, Gk也正定且 有界, 用 乘以上式两边, 得,由O()的定义, 存在常数C, 使得 (4.2.6) 若xk充分靠近x*使得 则由(4.2.6)有 (4.2.7) 这表明xk+1也在这个领域中. 由归纳法, 迭代对所有k有定义.由于 令k, 得hk0.因此迭代序列xk收敛. (4.2.6)表明收敛速度是二阶的,应该注意的是, 当初始点远离最优解时, Gk不一定正定, 牛顿方向不一定是下降方向, 其收敛性不能保证.为此, 在牛顿法中引进步长因子, 得到 其中k由线性搜索策略确定.,牛顿法的总体收敛性,定理4.2.3 设f(x)二阶连续可微, 又设对任意x0Rn, 存在常数m0,使得f(x
11、)在水平集L(x0)=x|f(x)f(x0)上满足 (4.2.9) 则在精确线性搜索条件下, 带步长因子的牛顿法产生的迭代点列xk满足 (1)当xk是有限点列时, 其最后一个点为f(x)的唯一极小点. (2)当xk是无穷点列时, 它收敛到f(x)的唯一极小点,证明 首先由(4.2.9)知f (x)为Rn上的严格凸函数, 从而其平稳点为总体极小点, 且是唯一的 由假设条件可知, 水平集L(x0)是有界闭凸集.由于 f (xk)单调下降, 可知 , 故xk是有界点列, 于是存在 ，使得 .又f (xk)单调下降且有下界, 故 由于 连续及L(x0)是有界闭凸的, 故存在常数Mm0使得 (4.2.1
12、0),于是 (4.2.11) 再由定理3.4.2可得 (4.2.12) 令k, 并注意到上式左边趋于0, 从而得到 . 这表明xk收敛到唯一极小点,不精确线性搜索牛顿法的总体收敛性,定理4.2.4 设f(x)二阶连续可微, 又设对任意x0Rn, 存在常数m0, 使得f(x)在水平集L(x0)=x|f(x)f(x0)上满足(4.2.9). 则在Wolfe不精确线性搜索条件下, 带步长因子的牛顿法产生的点列满足 (4.2.15) 且xk收敛到f (x)的唯一极小点.,证明：如果线性搜索采用Wolfe不精确线性搜索, 根据引理3.5.4, 我们有 (4.2.13) 将(4.2.12)式换成 (4.2
13、.14) 同样可以推出 .,例 试用Newton法求 的极小点,初始点取为 解: 梯度为 Hesse矩阵为 其逆矩阵为 由迭代公式得第1迭代点为 由于此时 ，停止迭代得 因此，它就是极小点,4.3 共轭梯度法,共轭梯度法是介于最速下降法与牛顿法之间的一个方法. 它仅需利用一阶导数信息, 但克服了最速下降法收敛慢的缺点, 又避免了牛顿法需要存储和计算Hesse矩阵并求逆的缺点. 共轭梯度法不仅是解大型线性方程组最有用的方法之一, 也是解大型非线性最优化问题最有效的算法之一.,4.3.1 共轭方向法,共轭梯度法是共轭方向法的一种. 所谓共轭方向法就是其所有的搜索方向都是互相共轭的方法.,定义4.3
14、.1 设G是nn对称正定矩阵, d1, d2是n维非零向量.如果 (4.3.1) 则称向量d1和d2是G-共轭的(或G-正交的), 简称共轭的. 设d1, d2, , dm是Rn中任一组非零向量, 如果 (4.3.2) 则称d1, d2, , dm是G-共轭的, 简称共轭的. 显然, 如果d1, d2, , dm是G-共轭的, 则它们是线性无关的. 如果G= I, 则共轭性就是通常的正交性.,共轭方向法步骤,步1. 给出初始点x0,0 , k: = 0 .计算g0= g(x0)和初始下降方向d0 , 使 . 步2. 如果 , 停止迭代. 步3. 计算 和xk+1, 使得 (4.3.3) (4.3.4) 步4. 采用某种共轭方向法计算dk+1使得 步5. 令k:=k +1, 转步2,共轭方向,C,D,A,B,定理1,几何意义,对于正定二次函数的极小化 (4.3.5) 梯度 它相当于
