运筹学10使用导数的最优化方法

《运筹学10使用导数的最优化方法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、最优化理论与算法帅天平北京邮电大学数学系Email:tpshuai@gmail.com,Tel:62281308,Rm:主楼814§10，使用导数的最优化方法TPSHUAI1第十章使用导数的最优化方法最速下降法牛顿法共轭梯度法拟牛顿法信赖域法TPSHUAI210.1最速下降法10.1最速下降法考虑无约束问题minf(x),xRn(10.1.1)其中f(x)具有一阶连续偏导数。在处理这类问题时，一般策略是，希望从某一点出发，选择一个目标函数值下降最快的方向，沿此方向搜索以期尽快达到极小点，基于这一思想，Cauchy于1847年提出了最速下降法。这

2、是无约束最优化中最简单的方法。TPSHUAI310.1最速下降法－1函数f(x)在点x处沿方向d的变化率可用方向导数表示，当函数可微时有，方向导数TDfxd(,)fxd()(1.2)求函数f(x)在点x处下降最快的方向,归结为求Tminfxd()st.d1(1.3)由Schwartz不等式,Tfxd()fx()dfx()Tfxd()fx()(1.4)TPSHUAI410.1最速下降法－2由上式知.当fx()d(1.5)fx()时等号成立.故在点x处沿(1.5)所定义的方向变化率最小,即负梯度方向为最速下降方向.

3、注意:在不同的尺度下最速下降方向是不同的.TPSHUAI510.1最速下降法－3最速下降算法最速下降算法的迭代公式为(k1)()k()kxxd(1.6)k()k()k()k其中d是从x出发的搜索方向,此处取在点x的最速下降()kk()方向,即dfx().()kk()是从xd出发沿方向进行一维搜索的步长,即满足k()k()k()k()k(fxd)fx(d)(1.7)kmin0TPSHUAI610.1最速下降法－4算法描述()knStep1,给定初始点xE,允许误差0,置k1()kk()Step2,计算搜索方向d

4、fx()()k()k()kStep3,若d,停止,否则,从x出发,沿d进行一维搜索,()k()k()k()k求,使得fx(d)fx(d)kkmin0(k1)()k()kStep4,令xxd,置k:k1,转Step2kTPSHUAI7例1.1用最速下降法求解下列问题22min()fx2xx12(1)T1初点x(1,1),10第一次迭代目标函数f(x)在点x处的梯度4x1fx()2x2TPSHUAI8令搜索方向4(1)(1)dfx()2d164251/10

5、(1)(1)从xd出发,沿方向进行一维搜索,求步长,即1(1)(1)min()fx(d)01414(1)(1)xd121222()2(14)(12)TPSHUAI9令()16(14)4(12)05/181在直线上的极小点1/9(2)(1)(1)xxd14/9第二次迭代(2)fx()在点x处的最速下降方向为4/9(2)(2)dfx()8/9(2)4d51/109TPSHUAI10(2)

6、(2)从xd出发,:沿方向进行一维搜索(2)(2)min()fx(d)01/94/9(14)/9(2)(2)xd4/98/9(48)/922216()(14)(12)8181令1664()(14)(12)081815/122TPSHUAI11得到21(3)(2)(2)xxd2271第三次迭代(3)fx()在点x处的最速下降方向为42(3)(3)dfx()271(3)4d51/102

7、7TPSHUAI12(3)(3)从xd出发,:沿方向进行一维搜索(3)(3)min()fx(d)02142214(3)(3)xd27127127128422()(14)(12)222727令()05/182TPSHUAI13221/91(4)(3)(3)xxd2274/92434此时(4)81fx()524310已经满足精度要求,得近似解21x2434问题的最优解为x*=(0.0)TPS

8、HUAI14算法的收敛性Theorem1.1设fx()是连续可微的实函数,解集合()k=xfx()0,最速下降法产生的序列{x