最优化方法第四章B.ppt

第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(柯西-施瓦)不等式 (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. 由线性有哪些信誉好的足球投注网站求步长因子 . 步4. 计算 步5. k:=k+1, 转步2 . 最速下降法的收敛性 对于最速下降法,θk=0, 因而, 利用定理3.4.3立即可知最速下降法是总体收敛的. 定理4.1.2 设 在水平集L={x∈Rn|f(x)≤f(x0)}上存在且一致连续, 则最速下降法产生的序列满足或者对某个k 有gk=0, 或者f(xk)→-∞, gk→0. 证明：利用定理3.4.3立得. 最速下降法的总体收敛性定理 定理4.1.3 设函数f(x)二次连续可微, 且 , 其中M是某个正常数.对任何给定的初始点x0, 最速下降算法4.1.1或有限终止, 或 , 或 证明:考虑无限迭代下去的情形, 由定理3.4.2, 有 (4.1.9) 于是 (4.1.10) 两边取极限, 于是, 或者 , 或 .从而定理成立 最速下降法优缺点 优点：程序设计简单，计算工作量小，存储量小，对初始点无要求 缺点：最速下降方向仅是局部性质，对整体而言，下降速度慢，锯齿现象 锯齿现象 数值试验表明, 当目标函数的等值线接近于一个圆