资源描述：
《运筹学使用导数的最优化方法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、运筹学10使用导数的最优化方法最优化理论与算法§10，使用导数的最优化方法TPSHUAI1第十章使用导数的最优化方法最速下降法牛顿法共轭梯度法拟牛顿法信赖域法TPSHUAI210.1最速下降法10.1最速下降法考虑无约束问题minf(x),x??Rn(10.1.1)其中f(x)具有一阶连续偏导数。在处理这类问题时，一般策略是，希望从某一点出发，选择一个目标函数值下降最快的方向，沿此方向搜索以期尽快达到极小点，基于这一思想，Cauchy于1847年提出了最速下降法。这是无约束最优化中最简单的方法。TPSHUAI310.1最速下降法－1函数f(x)在点x处沿方向d的变化率可用
2、方向导数表示，当函数可微时有，方向导数Df(x,d)f(x)Td(1.2)求函数f(x)在点x处下降最快的方向,归结为求minTf(x)ds.tdδ1(1.3)由Schwartz不等式,Tf(x)dδf(x)df(δx)Tf(x)dτf(x)(1.4)TPSHUAI410.1最速下降法－2由上式知.当f(x)d(1.5)f(x)时等号成立.故在点x处沿(1.5)所定义的方向变化率最小,即负梯度方向为最速下降方向.注意:在不同的尺度下最速下降方向是不同的.TPSHUAI510.1最速下降法－3最速下降算法最速下降算法的迭代公式为(k1)(k)(k)xxΟd(1.6)k其中(
3、k)是从(k)出发的搜索方向,此处取在点(k)dxx的最速下降方向即()(),df(x).Ο是从()出发沿方向()进行一维搜索的步长,即满足k(k)(k)m(k)(k)f(xd)inf(xΟd)(1.7)ΟkΟ0τTPSHUAI6(k)nStep1,给定初始点xE,允许误差Η0!,置k1()(k)Step2,计算搜索方向df(x)(k)(k)(k)Step3,若dδ,Η停止,否则,从x出发,沿d进行一维搜索,10.1最速下降法－4算法描述(k)(k)(k)(k)求Ο,使得f(xdΟ)mf(xdΟ)inΟ0τ(k1)(k)(k)Step4,令xxΟd,置k:k1,转Step
4、2kTPSHUAI7例1.1用最速下降法m求解下列问题22inf(x)2xx1初点(1)T1x(1,1),Η10第一次迭代目标函数f(x)在点x处的梯度4x1??≡f(x)2??≈x2←…TPSHUAI84??≡(1)(1)(1)(1)令搜索方向mdf(xinΜ()Οf(x??d≈Ο)2Ο0τ←…d164251/10!1??≡4??1≡4Ο??≡(1)(1)从x(1)出d发,沿方Ο向d(1)进行一维搜Ο索,求步长1Ο,即??≈??≈??≈1←…2←1…2Ο←…22Μ()Ο2(14)Ο(12)ΟTPSHUAI9令Μ(χ)Ο16(14)Ο4(12)0Ο1Ο5/18在直线上的极
5、小点4/19/9??≡(2)(1)(1)xx(21Οd)第二次迭代df(x4??≈/9←…在点8/9f(x)x(2)处的最速下降方向为4(2)d51/10!9TPSHUAI10(2)(2)minΜ()Οf(xdΟ)Ο0τ??1/9≡4/9??(≡14??Ο)/9≡(2)(2)dΟ??≈??≈??≈4/98/9(48Ο)/9从x(2)出发,沿方向d←(2)进行一维…搜索←…←…:2162Μ()Ο(14)Ο(12)Ο81616481令Μ(χ)Ο(14)Ο(12)0Ο8181Ο5/122TPSHUAI11得到21??≡(3)(2)Ο(2)xx2d??≈271←…第三次迭代42?
6、?≡(3)(3)df(x??≈f(x)在点x(3)处2的7最1速←下降…方向为4(3)d51/10!27TPSHUAI12(3)(3)minΜ()Οf(xdΟ)Ο0τ21??≡42??2≡14Ο??≡(3)(3)dΟ??≈??≈??≈Ο从2712712712x(3)出发←…←…←…,沿方向d(3)进行一维搜索:822Μ()Ο(14)Ο(12)Ο222727令(Μχ)0Ο2Ο5/18TPSHUAI132??1/9≡21??≡(4)(3)(3)xx2Οd??≈??≈27←4/9…2434←…此时(4)81f(x)524310已经满足精度要求,得近似解21??≡x??≈2434
7、←…问题的最优解为x*=(0.0)TPSHUAI14T算法的收h敛性eorem1.1设f(x)是连续可微的实函数,解集合(k):=x⊥f(x)0,??最速下降法产生的序列{x}含于某个紧集,则序列(k){}的每个聚点x??.:证明:最速下降算法A可表示为合成映射A=MD其中D(x)=(x,-f(x)),是EnοEnυEn的映射.每给定一点x,经算法D作用,得到点x和在x处的负梯度(从x出发的方向d).算法M是EnυEnοEnTPSHUAI15映射.每给定一点x及方向d=-f(x),经M作用,即一维搜索,得到一个新点,在这一点,
