大二下课件-最优化

第三 无约束最优化方讨论无约束优化问

f(x),xRn（1）

XbTX

fX

2

X）fX）fX1XT2

fXX

2

X

）fX）fX1XT2

2

X一阶展开：f(x)f(xf(x)T(xxo(||xx f(x)f(x)f(x)T(xx 1(xx)T2f(x)T(xx)o(||xx||2 回顾：多元函数Taylor定理：设f：RnR具 二阶连续偏导数。则fXpfX

X

p2

pT2

fXp其中

X

而0＜θ＜1fX

p

fX

X

p2

pT

fXp

p2 f fxkpk.

:

R1.则' kkTk" T2kkkpk 无约束最优化问题的最优性对于一元连续可微函数()

（一阶必要条件若*为()的局部极小点，则(*)（二阶充分条件

0；若(*)点

0，(*)

0，则*为(的严格局部极小(iii)（二阶必要条件若*为()的局部极小点，则(*0，(*0定理 （一阶必要条件若x*

f(x)的局部极小点，且在x*的某邻域内

f(x)具一阶连续偏导数证 反证

g*f(x*)0若

0则存在方向pR（

pTg* 由微分学中值定理，存在1(0,)使f(x*成立

p)f(x*)pTg(x*1由于gx*的某邻域内连续，故存在

0，使0,pTg(x*

0。所以，对

(0,)f(x*

pf(x*)与x*是f的局部极小点满足

X

定理 (二阶充分条件若在x*的某邻域f(x)有二阶连续偏导数g*

G*G(x*)正定则x*为无约束优化问题的严格局部极小点证明

f(x)在x*点用Taylor公式展开，并注意到

0，f(x)

f(x*)

1(xx*)TG*(xx*)2

x

2)因为G*正定pRn有为G*的最小特征值。2于是2

pTG*p

p2其中f(x)

f(x*)

[12

x x充分接近x*（但xx*）时，上式右端大于0，故f(x)

f(

)，即x*

f(x)的严格局部极小点3.1.3(二阶必要条若x*

f(x)的局部极小点，且在x*的某

f(x)有二连续偏导数，g*0，G*半正证明：任取非零pRn，对于R1定义函()

f

p)，()

g(x*

pTG(x*

p)x*为f(x的局部极小点以当充分小时(

(0)，即

0为()的局部极小点故由一元函数的最优性条

(0)即g(x*)T

p0，pTG(x*)p

0pg*0，G*半正定定理 设f(x)在Rn上是凸函数且有一阶连续导数，则x*为f(x的整体极小点的充分必要条件g*0作业：证明如上结论回顾定理：（)凸规划的任意局部极小点就是整体极小点，且极小点集合是凸集。(2)如果凸规划的目标函数是严格凸函数，又存在极小点，则它的极小点还是唯一的。xkk xkk kk，若01则称xk为线性收敛为收敛若0，则称序列xk为超线性收敛的。若1，则称序列xk为次线性收敛的1.2.4设序列xk收敛于xp*有 k k1 k kp则称序列xk为p

最速下降由Taylor公式f(xp)

f(x)g(x)T

p

p

f(x)下降最快算法 最速下降给定控制误差0 取初始点x0，令k0 计算gk gk

g(xk，则

，停；否则，令pkgk由一维搜索求步长k，使f(xkkpk)

f

pkStep4，令xk

k1Step2minf(x)xx2x22xxx2， 初始点设为(0,0)T，采用精确线g(x)

2x

2x

，1， k0： ，

，

1，2 2 xx

()

f

p)

f

2

0 xx

pgpg11g1

2xx

11

1

1

f

p)

f

1

1 22

2

2

215221111

4

1 5

1

k2:5 5g2

1 1 5

g2

例2 始点设为(9,1)T。

f(x) 2 解 9目标函数是正定的二次函数x*

0)可以证明，如

f(x)是二次正定函数，则由精gT一维搜索确定的步长k

k

k作业 p g TkpTGpkk g TkpTGpkkgT

gk，gTg 由于

g(x)9,9)T，所以由上式可 9

9 99

9

7.2x 1 1

099 9 99由于gg(x7.27.2)T

7.27.27.2

7.2

7.2 5.76x

07.27.2 0.647.2 97.2类似计算下去，算法产生如下点 (0.8)k，k1, (1)k

x*，且

xk

xk

0.8，可见**个相邻的搜索方向是正交x xx2x证明：由步长k的定义 ()f(xkpk

(

p)]Tkk取k 使'( kk

(

p)]T kgk即pkgk即pk 故在相继两次迭代中，搜索方向是相互正交的。可见，最速下降法近极小点的路线是锯齿形的，而且越x x 黄金分割法精确一维搜索计算结果

f(x,x

||g(xk) x- x--------kxxf(x,x||g(xk)123456789换为wolf不精确一维搜kf(x1,x2||g(xk)12-34-56-73：Rosenbrockminf(x)100(xx2)2(1x 问题有唯一极小点，精确解为x*1,1)Tfx*)1，1kf||g(xk)1-2-3-4-5-6-7-8-9-4：扩充的Rosenbrocknminf(x)100(xi1xn2ii

22,1)T问题有唯一极小点，精确解为x*,1)T

fx*01，1,…,1，

f

||g(xk)-1，1,…,1

f

||g(xk)-

f(x1,x2

||g(xk)1，1,…,1

f

||g(xk)- 收敛 整体收敛最速下降法对一般的目标函数是整体收敛的定理 设f(x)具有一阶连续偏导数，给定0xRn假定水平集LxRn/f(xf(x)有界00{xk}为由算法3.2.1产生的点列，则或0对某个k0g(xk0或

0；当k时gk0，2．用于二次函数时的收敛速定理f(x)

1xTGx，其中G为正定，表示 的最小与最大特征值，则最速下降算法3.1.1产生的{xk}满f(xk1

22

11

f(xk

k0,1,22

n 1

k0,1,1

（注意

f(x)的唯一极小点为

0对于二次目标函数，最速下降法至少是线性收敛的其收敛比

而由2所以当G的特征值比较分散，即n远远大于1时，收敛比接近于1，收敛速度很慢，接近线性收敛；当G的特征值比较集中，即n1时，0，从而收敛速度接近线性收敛但由于其收敛速度慢，所以它不是好的实用算法。然而一些有效算法是通过对它进行改进或利用它与其他收敛快的算法相结合而得到的。因此，它是基

Newton Newton(x)是二阶连续可微函数，设xk

f(x)的x*f(x)在x附近作Taylorkff(x)q(x) gT(xx)1(xx)TG(xxkkkk2kkkfk

f(xk)，

g(xk

G(xk)，若G正定，则q(x)有唯一极小点，将它取为x*的下 次近似xk1f(x)q(x)ff(x)q(x)fgT(xx)1(xx)TG(xxkkkk2kkk Gk(x

xk)

0 xxG xxkxG1gkkk xk1xkpkpkGkpkgk方程组GkpkgkNewton公式 xG1g称为Newton迭代公式k

算法 Newton给定控制误差0 取初始点x0，令k0 计算gk 若

，则

Gk，并由Gkpkgkpk 令xk

pk

kx例 用Newton法求x

f(x)2

9x22 2设初始点x09,1)Tg(x)

,9x

)T，G(x)

0 xkxkxG1gkkkkxx

9 019 0

x*

解:用Newton法得到得迭代点如表所示k||g(xk)122Newton求minf(x)xx2x22xxx2， 初始点设为(00)Tg(x)

G(x)

2，2x2x1 2 k0：

Gpgg0 ， 22

Gpg 1，

3

2,,

0x1

x0p032

g1 ,0 0

3Newton求解问minf(x)(x2)4(x2)2x2(x 问题极小点为(21)T,取初始点为(1,1)T解:用Newton法得到得迭代点如表所示

||g(xk) - - - - - - - 初始点的影4：用Newton解问

f

(3,4)T,

20)T

f

g(x)

8x1－2x1x2 2x GG(x)12解:(1)用Newton法得到得迭代点如表所kf(xk||gk01234xk

严格局部极小G(x)G(x)12 2解:(2)用Newtonkf(xk||gk012(2.8284,xk

鞍GG(x)－2x112G(2

2,4) 222 2

GG(x)－2x112G(2,0) 4 2Hesse奇异，无法继续5：Rosenbrockminf(x)100(xx2)2(1x 问题有唯一极小点，精确解为x*1,1)Tfx*)1，1，结kf(x1,x2||g(xk)1-2-3收敛设f(x)是某一开域内的三阶连续可微函且它在0开域内有极小点x*，设G*G(x*)正定，则当x与x*充0接近时，对一切k，Newton法有定义，且当xk为无点列时，xk二阶收敛于x，即h0*kk其中hx

O( 2x*2 Newton点⑴如果G*正定且初始点合适，算法是二阶收敛的⑵对正定二次函数，迭代一次就可得到极小缺⑴对多数问题算法不是整体收敛的⑵在每次迭代中需要计算Gk⑶每次迭代需要求解线性方程组，Gk程组有可能是奇异或

gk该⑷收敛于鞍点或极大点的可能性并不小Newton的改以pk作为搜索方向进行一维搜索，求步长k，例如，令k满足精确一维搜索，即f(而

lim

xk

pk这样往往可以克服缺点⑴和⑷，这种方法通常Newton。例7：用阻尼Newton法求解问minf(x)(x2)4(x2)2x2(x 问题极小点为(21)T,取初始点为(1,1)Tkf(x1,x2||g(xk)12-3-4-wolfkf(x1,x2||g(xk)12-3-4-5-6-7-8-8：Rosenbrockminf(x)100(xx2)2(1x 问题有唯一极