最优化理论 第四章 最速下降法与牛顿法

2.1的关键步骤——确定目标函数的下降方向.§4.1最速下降法在§2.4f(xxk处下降，搜索方向dk必须满足不等式

f(xk)Tdk0.向量f(xkdk的内积f(xk)Tdk||f(xk)||||dk||cos， (4.1.1)其中是向量f(xk和dkdk是下降方向的充分必要条件为它与f(xk的夹角必须大于2，或者说，它与f(xk的夹角必须小于2.k仅是负的，而且绝对值越大，目标函数的下降越多. 因此，我们希望搜索方向dk是优化问k题mind0

f(xk)Td||d||

(4.1.2)(4.1.1)易见，dkf(xk||f(xk||是优化问题(4.1.2)的最优解.因此，我们把dkf(xk称为最速下降方向.§4.1.1最速下降算法降法，它是无约束最优化算法中最简单、最基本的算法.4.1（最速下降法）1x0n，容许误差0k0；2：计算f(xk，若||f(xk||xk；3：令dkf(xk；步4：由线搜索确定步长因子k，譬如，取k使得f(xkdk)minf(xkdk)；k 0k5xk1xkdkkk12.k交的.kdkf(xk，对一元函数(f(xkdk，精确线搜索的最优步长因子k应满足(k0，即kkf(xkdk)Tdk0，xk1xkdk，又dk1f(xk1，故有kk(dk)Tdk10. (4.1.3)（迭代点列呈锯齿状趋于最优解）.好的总体收敛性，但缺点是在实际应用中收敛速率慢.§4.1.2 最速下降法的收敛性定理4.1.1 设fC1，则最速下降法产生的点列{xk}的每个聚点均为驻点.K1x是{xk{xk}K1

limxkxdkf(xk，kK1KfC1知{f(xk)}K1

收敛，故{dk}K1K

有界，且limdkf(x3.2.2，有kK1f(x)T[f(x)]f(x)20，故有f(x0.定理4.1.2 若f(x)二阶连续可微且2f(x)M则对任意给定的初始点x0n，最速下降法或有限终止，或limf(xk)，或limf(xk)0.k k证不妨设对任意k都有f(xk03.2.1，有12Mf(xk)f(xk1) f(xk)212M于是kkf(x0)f(xk)f(xi)f(xi1)1

f(xi)2. i0

2Mi0由于f(xk)}为单调下降序列，故或有limf(xk，或有limf(xk)0.k k定理4.1.3 设fC1则最速下降法采用不精确线搜索得到的点列{xk}的每个聚点均为驻点.3.4.2可得.§4.1.3 最速下降法的收敛速率我们先来考察一般的正定二次函数f(x)1xTGxrTx，2其中G为n阶对称正定矩阵. 设x*是极小点，则f(x)可表示为f(x)1(xx*)TG(xx*)1(x*)TGx*，2 2f(x)1xTGx.2定理4.1.4 对极小化问题minf(x)1xTGx，其中G为n阶对称正定矩阵，，xRn 2 1 nxk1x*xkxxk1x*xkx*1nf(xk1)f(x*)

()2

1n1 n ，1n

1 n.f(xk)f(x*)

)2

n证由于f(xGx，故k k k k xk1xkdkxkf(xk)xkGxk(IG)xk，其中f[(IG)xkf[(IG)xk对任意k k k k P(t)1kt，Q(t)utuRQ(0)Q(G)IuG，由此可知，当0u0时，我们有f(xk1)f[(IG)xk]f(Q(G)xk)k Q(0)1(Q(G)xk)TG(Q(G)xk)

1 (Q(G)xk)TG(Q(G)xk).2Q(0) Q(0) 2Q2(0)设

是G的特征值，而ui(i12,n是对应得标准特征向量（两两1 2 n正交的单位向量）.xk

nniii1

akui，代入上式，得f(xk1) 1

akQGuiTG

akQ(G)uj)2Q2(0)

ni1n

i jj1 1 (n

akQ(uiTG

akQ()uj)2Q2(0)

ni1n

i i j jj1 1 (n

akQ(uiT

akQ()uj)2Q2(0)

ni1n

i i j j jj1i i i i 2Q2(0)i1

(ak)2Q2().对Q(tut，通过令Q(11,Q(n1，我们来确定待定参数u，由此得1n,u 2 ，从而有Qt)t1n.

显然Q(t单调增加，由Q(11,Q(n1及12,n，即得

于是，由

i i f(xk1)i i (0)i1

(ak)2Q2()

1 n2Q2(0)i1

(ak)2，i i 1n1k kiT

n kj 1 n

n n1kiT k j k21f(x

)2(iu

G(aj

)2(iu)(ajj

)2i(ai)，i1

i1

i1f(xk)

2我们有f(xk1) .又由于Q2(0)1 n

，因此，对任意k，都有Q2(0)

n2f(xk1)1 n1n

f(xk). (4.1.4)由于01n1f(xk)0f()(k)f(x)1nxk0x*(k)，即点列{xkx*0.(4.1.4)得到第一个估计式f(xk1)f(x*)

f(xk1) 2 1 n.f(xk)f(x*)

f(xk)

n记ekxkx*，由G的对称正定性，对任意k，我们有(ek)Tek(ek)TGek(ek)Tek，n 1x*0(ek)TGekxk)TGxk2f(xk)k，有(ek)Tek2f(xk)(ek)Tek.n 1(4.1.4)，可得

(ek1)Tek1

2f(x

2xk1x*2xk1x* n 11 n，xkx*2

(ek)Tek

2f(xk)1

.如果令1n

GG1

，即为矩阵G的条件数，则上式可写成xk1xk1x*xkx*(1)(1).4.1.5f(x3.2.7的假设条件，若最速下降算法产生的点列{xk收敛x*R线性的.3.2.7的自然推论.§4.2牛顿法§4.2.1牛顿迭代公式f(xxkTaylor展开式的极小xk1f(x的一个更佳近似解，由此产生算法的基本迭代格式.xk2f(xkf(xxkTaylor展开式为q(k)(s)f(xk)f(xk)Ts1sT2f(xk)s，2sxxk，极小化q(ks)得sk2f(xk)1f(xk，由此得到牛顿法的基本迭代格式xk1xk2f(xk)1f(xk). (4.2.1)g(xG(x)f(x)的梯度f(x)Hessiank矩阵2f(xgk

f(xk)，G

2f(xk).k注（1）牛顿法可视为椭球范数|2f(xkk

下的最速下降法. 事实上，欧氏空间Rn中一般范数||||下的方向导数定义为：tsdftsds

t0

f(xkts)f(xk)

f(xk)Tss，ss它显然与范数||||有关.不难理解，minssRn

f(xk)Ts

的最优解就是函数f(x在xk处对应于范数||||的最速下降方向，且这个解与所取的范数有关.G若取椭球范数||||Gk

，则对任意sRn，有T 1

(G1g

G1g sgTsksGksGkgkkks k k kgTsksGksGksGk

k kGk

GkG1g ，sGkksGkk k 这意味着G1k

为方向导数的下界. 另一方面，若取sG1gk Gk s2s

，则有gTs gTG1g (G1g)TG(G1g) G k k k k k k k k k kG1g ，s sGk Gk

s sGk

k kGk这表明方向导数能够达到下界G1g

是关于椭球范数||||

的最速下降方向.

k kGk

k k k Gk（2）无约束最优化问题的牛顿法也可以理解为非线性方程组的牛顿法，这是因为求解minfx的经典方法实际上是在寻找f(x的一个驻点，即求解非线性方程组f(x)0.xRn设xk是当前迭代点，若f(xk0xk是方程组的解，否则将f(xxk处线性化，得

f(x)f(xk)2f(xk)(xxk)0，将上述线性方程组的解xxk2f(xk)1f(xk作为f(x)0牛顿迭代公式（4.2.1）.§4.2.2牛顿法的收敛性定理4.2.1fC2xkx*，而f(x*02f(x*)正定.若Hessian矩阵2f(xLipschitz条件，则由牛顿法产生的序列{xkx*，且具有二阶收敛速率.fC2，2f(xLipschitzxkx*时，由定理1.2.1可知，存在0，使得||f(x*)f(xk

)2

f(x

k)(x*xk

||x*xk2

||2，fC2，2f(x*可逆（正定矩阵必定可逆）1.1.1x*的充分小邻域内，2f(xM0，满足||2f(x)1||M.xk充分靠近极小x*时，对任意k，我们有||xk1x*||||xk2f(xk)1f(xk)x*||||2f(xk)1||||f(xk)(x*xk)2f(xk)||M||f(x*)||||x*xk||2 2 M2

||x*xk

||2，M||x*xk||r1，则有2.

0(k，即迭代点列{xk收敛，k索；而牛顿法的缺点是不能保证全局收敛，当G不正定时，甚至不能保证dk是下降方向，算法需要计算Hessian矩阵，单步计算量大.k§4.2.3 阻尼牛顿法搜索过程.4.2（阻尼牛顿法）1x0Rn，容许误差0，置k0；2gk，若gkx；k3：确定牛顿方向，从牛顿方程Gkdgk

解出dk；4：沿dk进行线搜索，使得f(xkdkminf(xkdk)；k k 0k5xk1xkdk，置kk12.k4.2.2fRnRx0Rn，存在常数m0，使得f(x)L(x0{xf(x)f(x0上满足不等式uT2f(x)umu2，uRn，k则采用精确线搜索的阻尼牛顿法产生的迭代点列{xk或者对某个kg0，或者{xk收fx*.kk证不妨设对任意kg0.由定理的条件知，f(xL(x0f(x)kL(x0f(xL(x0f(x的极小点.下面证明{xk}f(x的驻点.由f(x)L(x0)L(x0)是有界闭凸集，再由f(xk)单调下降，可知K{xkL(x0，故{xkxL(x0及子列{xk}，使得K1lim

xkx. 再由f(xk)单调有界知limf(xk k

f(x，特别地，有lim

f(xk)f(x).L(x0是有界闭集，故f(x)L(x0上一致连续，且由fC2知，存在常数M0L(x0上有G(x)M，因此，对任意k，有gTdk

k)TGdk

(dk)TGdk mmdk2kkk2cos k k k ，mdk2kkk2kg dkk

g

Gdk

Mdk M由此知

k2

M

. 3.2.3，有f(xk)g2

0，从而f(x)0xf(x的驻点，它也是极小点.x0.xkx，则存在正数和一个子x0K序列{xk}K2

，使对一切kK2，有

xk

0

.注意到{xk}K2K

是有界点列，故存在收敛K子列{xk}K3

(K3K2

limlim

f(xk)f(ˆ)，32.，可得f(ˆ)0，从而ˆ也是f(x)ˆxf(x的极小点唯一矛盾，故必有{xkx.§4.3牛顿法的修正策略kG1不存在；kk k Gk k

G1g

可能不是下降方向..§4.3.1 Goldstein—Price修正方案当Gk非正定时，采用最速下降方向gk替代牛顿方向.若进一步将搜索方向与负梯度方向的角度准则结合起来，则有dk

dk,g

,dkN N kgk,

否则,这里dkG1g，这样搜索方向dk总满足cosdkg

.N k k k.牛顿法的局部快速收敛性质.§4.3.2 Goldfeld修正方案若Gk不正定，则用GkGkvkI来修正Gk.通过适当选取vk0，可以使Gk正定.事实上，只要将vk取得稍大于Gk的最小特征值的模即可.利用特征值的圆盘定理可以求得最小特征值的模的估计 mini min(Gk)ii(Gk)ij. i 1in

ji 用此方法可求出vkvkGk与Gk相差甚远，这是一个缺陷.而实际求出Gk的全部特征值计算量又太大，因此，这个方法更多的是理论的价值.§4.3.3 基于GkCholesky分解的方案先作GkCholesky分解GLDL，然后令kTkGLDLT，kDdiag(d11,dnndiimaxdii,diiD为给定的小正数.k这种处理方法简单，但有下列缺陷：当Gk不可逆或GkGkCholesky分解不存在.即使Gk的分解存在，其计算过程也可能数值不稳定.计算过程中小的误差会导致结果的巨大差别，同时还可能出现Gk与Gk的差别很大.§4.3.4 GillMurray修正方案Gill—Murray修正法也称为强迫矩阵正定的Cholesky分解法，它在Gk的分解过程中进行适当修正，使dLDLT不是ii k真正的Gk，而是Gk的近似Gk.其要点在于：在分解过程中，增加了保证分解得到的因子矩阵元素一致有界的措施.在过程完成时，得到

E，k kE是非负对角矩阵.dii及因子矩阵元素一致有界，必须对Gk的元素进行调整，否则算法进行不下去，但必须指出的是，所有调整都只涉及Gk的对角元素，通常是将其增大，这就保证了即Gk与Gk仅差一个对角矩阵.可以证明，当Gk充分正定时，有GkGk.Gill—Murray修正牛顿法有如下收敛性质.设f(x)在Rnx0使L(x0xf(x)f(x0为有界闭凸集，x1L(x0，则由Gill—Murray修正牛顿法产生的点列{xk满足：若{xk是有限点列时，它的最后一个点必为f(x的驻点；若{xk是无穷点列时，它必有聚点，且任一聚点均为f(x的驻点.§4.4 负曲率方向法§4.4.1负曲率方向负曲率方向法是修正牛顿法的又一种形式.当2f(xk到下降方向，尤其在鞍点处，即f(xk)0，而2f(xk不是半正定时，若采用负曲率方向作为搜索方向，可以使目标函数下降.f(xD上二阶连续可微，若2f(xxD称为不xddT2f(x)d0df(x)x处的负d是负曲率方向，显然dsTf(x0dTf(x0，dT2f(x)d0，则称向量对sdxx不是一个不定点，则满足：sTf(x)0，dTf(x0，dT2f(x)d0的向量对(sd)x处的下降对.

sf

若2fx)0,否则,其中u是对应于2f(x的负特征值的特征向量，则向量对(sd)x处的一个下降对.由定义易见，当且仅当f(x)0且2f(x0x处不存在下降对.因此，一旦在该点不存在下降对，那么该点必满足极小点的二阶必要条件（但仍不一定是极小点）.若x*是鞍点，则负曲率方向必为下降方向. 事实上，设d为负曲率方向，由f(x*d)f(x*)f(x*)Td12dT2f(x*)d(d2)2容易看出，当很小时，有f(x*d)f(x*).x为一般点，且负曲率方向d满足dTf(x)0，则d与d均为下降方向.若dTf(x0，则ddTf(x0，则d是下降方向..而唯一难找到下降方向的情形f(x0且2f(x0时.Gill-MurrayCholesky分解与负曲率方向相结合.当Gk不正定时，采用修改Choleskygk0时，采用负曲率方向使函数值下降.Fiacco-