最优化：最速下降法和Newton法

唯楚有材

於斯为盛

最优化主讲：刘陶文

学好最优化，走遍天下都不怕

课件制作：刘陶文

第三章 无约束问题算法(I)—— 最速下降法、 Newton法第一节 最速下降法

第二节 Newton法及其修正形式

给定无约束问题 min f ( x) nx R

(3.1)

在上一章里, 我们介绍了下降算法的结构及步长计算的 方法，在后面的几章里, 我们来介绍下降方向的计算. 下降方向的计算是整个最优化方法的核心, 不同计算方 式对应不同的最优化算法, 相应算法的收敛性理论和数 值效果有很大区别

第一节

最速下降法

最古老的优化方法，十九世纪中叶由Cauchy提出1、 思想 ：每次沿负梯度方向进行搜索

●

x*xk 1

等值线(面)

●

xk

●

f ( xk )

负梯度方向也称为最速下降方向：事实上，对任意p R n 且 || p || , 由Cauchy - Schwarz 不等式得 f ( xk ) T P - || f ( xk ) || || P || - || f ( xk ) || - f ( xk ) - f ( xk ) 当取p 时等号成立，即 p 是下列问题 || f ( xk ) || || f ( xk ) || 的解 min f ( xk ) T P|| p||

以负梯度为搜索方向的算法称为最速下降法

2、 算法步骤算法3.1 (最速下降法 ) 步1 给定初始点x0 R n , 精度 0.令k 0; 步2 若 || f ( x k ) || ,则得解x k , 算法终止.否则 计算d k - f ( xk ), 然后转步3 ; 步3 由线性搜索计算步长 k ; 步4 令xk 1 xk k d k , k : k 1, 转步2.

最优化算法看来是如此的简单？

例3.1.1 取初始点x ( ) ( , )T . 采用精确搜索的最速下降 法求解下面的最优化问题： min f ( x ) x x x 1 解 函数 f 的梯度为： f ( x ) 2 x , Q f ( x ) - x 搜索方向 d - f ( x ) - x 采用精确搜索极小化二次函数的步长公式为 f ( x ) T d x x - T d Qd x x

迭代公式为

x ( k ) x ( k ) k d ( k ) x ( k )

(k ) ( x ( k ) ) ( x ) - (k ) (k ) ( x ) ( x )

x ( k ) x (k )

由上面的迭代公式不难计算出最速下降法产生的点列为 x(k )

1 3

k

2 (-1) k , k 0, 1,

容易看出上面的序列是收敛的, 并且x ( k ) (0, 0)T x *

从上面的例子看到, 对于简单的二元二次函数极小化问题， 最速下降法在有限次迭代并没有求出其精确最优解, 但能 以较慢的速度无限接近最优解.

事实上，上面的例子刻画了最速下降法的所有收 敛特征

3、 最速下降法的收敛性 全局收敛性由于最速下降法

的搜索方向与负梯度方向一致, 即 k 0, 且 || f ( xk ) || || d k || 所以, 由定理2.4.1 - 2.4.3, 我们很容易得到最速下降算法的全 局收敛性.

定理 3.1.1 设假设 2.4.1的条件成立 , 那么采用精确搜索 , 或 Armijo搜索或 Wolfe- P owell搜索的最速下降法产生 的迭 代序列{xk }满足 lim || f ( xk ) || 0k

由前面的例子看到, 最速下降法的收敛速度至多是线性的, 具体 见下面的两个定理.

收敛速度估计下面的定理给出了其求解严格凸二次函数极小化问题的 收敛速度估计.定理证明可参考文献[19, 定理3.3] 定理 3.1.2 设矩阵 Q对称正定 , q R n .记 max 和 min分别是 Q max 的最大和最小特征值 , .考察如下二次函数极小 化 min问题： T min f ( x ) x Qx q T x 则由采用精确搜索的最 速下降法产生的点列 {x k }满足 - * || xk - x ||Q || x k - x ||Q *

(3.2 )

其中 x 是问题的惟一解 , || x ||Q x Qx * T

-1 * || xk 1 - x * ||Q || xk - x ||Q 1

(3.2 )

对于二次函数, 由于 f ( x ) Qx q且在x *处 f ( x * ) Qx * q 0 1 1 * * T * 2 则 f ( x ) - f ( x ) ( x - x ) Q ( x - x ) || x - x * ||Q 2 2 所以(3.2)可以改写成 -1 * * f ( xk 1 ) - f ( x ) [ f ( x ) f ( x )] k 1 由收敛速度估计式(3.2) 看到, 最速下降的收敛速度与矩阵 Q的条件数 有关, 当 接近于1, 最速下降收敛很快, 特别, 当 1即Q的所有特征值相等时, 算法只需一次迭代即可 求出最优解. 而当 较大时(Q接近病态) , 算法收敛很慢.2

从上图可以看出，最速下降法 具有锯齿现象

对一般的非二次函数有下面的收敛速度估计：定理 3.1.3 设函数 f二次连续可微 , 若采用精确搜索的最速 下降 法产生的点列 {xk } 收敛到问题 ( . )的解 x * , 且 f ( x * )正定 , 则 有估计 - * * f ( xk ) - f ( x * ) [ f ( xk ) - f ( x )] o[ f ( xk ) - f ( x )] 2

max 其中 , 且 max 和 min分别是 f ( x * )的最大和最小特征值 . min

定理的证明参见文献[19,定理3.4]

由上面的分析可知，最速下降法的收敛速度 比较慢，通常将其用在某些算法的初始阶段求较 好的初始点或作为某些算法的间插步.有点难啊 思考题：设序列{x k }是由采用精确搜索的最速下降法求解二 元二次函数 f ( x ) xQx bT x c 所产生，这里x R , Q R 对称正定，b R , c R.试证 明偶次迭代点x , x , 和奇次迭代点 x , x , 分别共线， 而且这两条直线的交点就是函数 f ( x )的最小点.

证明：我们

首先证明 : ( x 2 - x1 ) T Q ( x 2 - x0 ) 0 记 x k 1 x k k d k x k 1 x k k f ( x k ) f ( xk 1 ) f ( x k ) k Qd k 又由精确搜索得 f ( xk 1 ) T f ( x k ) 0 由(1) 和( 2), 进一步得到 - f ( x k ) T f ( x k ) f ( x k ) T f ( xk ) k T f ( x k ) Qd k f ( x k ) T Q f ( x k ) x …… 此处隐藏：1591字，全部文档内容请下载后查看。喜欢就下载吧 ……