非线性无约束规划_第1页
非线性无约束规划_第2页
非线性无约束规划_第3页
非线性无约束规划_第4页
非线性无约束规划_第5页
已阅读5页,还剩40页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

非线性无约束规划第一页,共四十五页,2022年,8月28日1)方向导数设M0位数量场u=u(M)中的一点,从点M0出发引一条射线l,在l上点M0的附近取一动点M,记如果时,下列表达式的极限存在则称之为M0处沿着l方向的方向导数.记为当时,表示函数u沿l是增加方向,当时,表示函数u沿l是减小方向。1.方向导数与梯度第二页,共四十五页,2022年,8月28日2)直角坐标系中方向导数的计算公式定理1.若函数u=u(x,y,z)在点M0(x0,y0,z0)处可微;

为l的方向余弦,则函数u在点M0处沿l方向导数必然存在,且有下面公式计算其中是在M0附近的偏导数.例题1

求函数在点M(1,0,1)处沿着方向的方向导数解:

第三页,共四十五页,2022年,8月28日3)梯度:根据方向导数公式可以知道是其变化率最快的方向,称为梯度,记为Gradu.如果用表示l线上的单位矢量,则方向导数可以写成梯度的性质:1)方向导数等于梯度在该方向的投影.即2)数量场u=u(M)中任一点M处的梯度,垂直于过该点的等值面,且指向u(M)增大的一方.例3

设为点M(x,y,z)的矢径的模,试证第四页,共四十五页,2022年,8月28日2.海瑟矩阵海瑟矩阵是对称形式:第五页,共四十五页,2022年,8月28日3非线性规划问题的展开形式

多元函数泰勒公式的矩阵形式:其中线性函数:f(X)=CTX+B=cixi

+B二次函数:f(X)=(1/2)XTQX+CTX+Bf(x)=f(x*)+fT(x)(x-x*)+(1/2)(x-x*)T

2f(x*)(x-x*)+o‖x-x*‖2第六页,共四十五页,2022年,8月28日4凸集、凸函数和凸规划1)凸函数

定义:

设集合SRn为凸集,函数f:SR

若x(1),x(2)S,(0,1),均有

f(x(1)+(1-)x(2))≤f(x(1))+(1-)f(x(2)),则称f(x)为凸集S上的凸函数。若进一步有上面不等式以严格不等式成立,则称f(x)为凸集S上的严格凸函数。性质:当-f(x)为凸函数(严格凸函数)时,则称f(x)为凹函数(严格凹函数)。严格凸函数凸函数严格凹函数第七页,共四十五页,2022年,8月28日2.2凸集、凸函数和凸规划(续)定理:f(x)为凸集S上的凸函数S上任意有限点的凸组合的函数值不大于各点函数值的凸组合。思考:设f1,f2是凸函数,设1,2>0,1f1+2f2,1f1-2f2是否凸函数?f(x)=max{f1(x),f2(x)},g(x)=min{f1(x),f2(x)}是否凸函数?

凸规划=凸可行集+凸目标函数第八页,共四十五页,2022年,8月28日凸函数与凹函数(续)凸函数的判定:

如果函数f(X)的Hesse矩阵处处半正定,则f(X)为凸函数,若f(X)正定,则f(X)为严格凸函数。注:

该命题的逆命题不成立例题检验函数的凸性。第九页,共四十五页,2022年,8月28日无约束问题的最优性条件1.必要条件:若X*是函数f(X)的局部最大点,则在该点必有f(X*)=0以及Hesse矩阵2f(X*)半正定定义:

对于可微函数f(X),称使其梯度为零向量的点为平稳点(驻点)。2.若X*是驻点,则其为极值点的充分条件:1)若H(X*)半正定,X*为局部极小点;若H(X*)正定,X*为孤立局部极小点;2)若H(X*)半负定,X*为局部极大点;若H(X*)负定,X*为孤立局部极大点;3)若H(X*)不定,X*为鞍点;(阅读课本的例题)第十页,共四十五页,2022年,8月28日6最优化问题的数值解VS解析解1.解析解与数值解注意获得解析解的困难性。2、收敛性概念:考虑(fs)设迭代算法产生点列{x(k)}S.1)算法的理想收敛:设x*∈S是(fs)的最优解,如果x*∈{x(k)},或者虽然

x(k)

≠x*,但是k,满足则称算法收敛到最优解x*。

第十一页,共四十五页,2022年,8月28日

概念:

1)

局部最优:2)全局最优:3)严格全局最优

以及

4)

全局收敛:对任意初始点x(1),算法均收敛。

5)局部收敛:当x(1)

充分接近解x*时,算法才收敛。第十二页,共四十五页,2022年,8月28日2.实用收敛性:

定义解集

S*={x|x具有某种性质}

例:S*={x|x---g.opt}

S*={x|x---l.opt}

S*={x|f(x)=0}

S*={x|f′(x)≤β

}(β为给定实数,称为阈值

当下列情况之一成立时,称算法收敛:

1°x(k)∈S*;2°k,{X(k)}任意极限点∈S*第十三页,共四十五页,2022年,8月28日8.收敛速度

设算法产生点列{x(k)},收敛到解x*,且x(k)≠x*,k,1.线性收敛:当k充分大时成立2.超线性收敛:3.二阶(次)收敛:

﹥0,当k充分大时有第十四页,共四十五页,2022年,8月28日定理:设算法点列{x(k)}超线性收敛于x*,且x(k)≠x*,k,那么证明只需注意|||x(k+1)–x*||-||x(k)–x*|||≤||x(k+1)–x(k)||≤||x(k+1)–x*||+||x(k)–x*||

,除以||x(k)–x*||并令k→∞,利用超线性收敛定义可得结果。8、收敛速度(续)第十五页,共四十五页,2022年,8月28日4.1常用的搜索算法结构考虑(fs)

常用一种线性搜索的方式构造{xk}序列来求解迭代中从一点出发沿下降可行方向找一个新的、更优的点。△下降方向:设∈S,d∈Rn,d≠0,若存在,使,称d为

在点的下降方向。minf(x)

s.t.

x∈S第十六页,共四十五页,2022年,8月28日4常用的搜索算法结构△可行方向:设∈S,d∈Rn,d≠0,若存在使,称d为该点的可行方向。

同时满足上述两个性质的方向称下降可行方向。第十七页,共四十五页,2022年,8月28日迭代算法的停止标准1)2)3)对于无约束问题可以用第十八页,共四十五页,2022年,8月28日10常用的搜索算法结构线性搜索求,新点使x(k+1)∈S初始x(1)∈S,k=1对x(k)点选择下降可行方向d(k)是否满足停机条件?停k=k+1yesno第十九页,共四十五页,2022年,8月28日11一维搜索一元函数求极小及线性搜索均为一维搜索。常用于求:

minf(x(k)+

d(k))=φ()s.t.

∈S

S有3种情况(-∞,+∞)或(0,+∞)或[a,b]一、缩小区间的精确一维搜索:考虑问题(P)minφ()

s.t.∈[α,β]

为此先介绍不确定区间及单峰函数的概念△不确定区间:[α,β]含φ(α)的最小点,但不知其位置第二十页,共四十五页,2022年,8月28日单峰的概念一、缩小区间的精确一维搜索(续)若对任意λ1,λ2,α≤1<2

≤β满足:

1º若

2

*,则φ(

1)>φ(

2);

2º若

1

≥λ*,则φ(

1)<φ(

2).则称φ(

)在[α,β]

上强单峰。

若只有当φ(1)≠φ(*),φ(2)≠φ(*)时,上述1º,2º式才成立,则称φ(

)在[α,β]

上单峰。

α

*

12

β强单峰

α

*

β单峰第二十一页,共四十五页,2022年,8月28日设f(X)是目标函数,如果是在给定Xk和方向矢量Pk下,通过f(x)=f(xk+akPk)

的极小化而产生则称为最优步长。根据单变量的驻点条件:以及复合函数的求导法则可得:1.精确一维搜索(假定求目标函数极小值)第二十二页,共四十五页,2022年,8月28日2一维搜索一、缩小区间的精确一维搜索(续)

定理:设Ф:R→R

在[α,β]上单峰,α≤x1

<x2≤β

。那么

1°若Ф(x1)≥Ф(x2),则去除[,x2

];如左下图

2°若Ф(x1)<Ф(x2),则去除[x2,β];如右下图

α

x1

x2

β

αx1

x2β第二十三页,共四十五页,2022年,8月28日12一维搜索2、黄金分割法(0.618法)选二点x1<x2,比较f(x1)

与f(x2),可去掉[a,x1]或者[x2,b]

考虑下面分割条件:

1°对称:x1

-a=b-x2……①

(使“坏”的情况去掉,区间长度不小于“好”的情况)

2°保持缩减比λ=(保留的区间长度/原区间长度)不变。(使每次保留下来的节点,在下一次的比较中成为一个相应比例位置的节点)。如图所示,推导缩减比λ第二十四页,共四十五页,2022年,8月28日黄金分割法的步骤:1)

确定初始区间为[a,b],初始区间的长度L=b-a,容差>0,k=12)计算初始分割点,x1=a+0.382L,f1=f(x1);x2=a+0.618L,f2=f(x2)3)消去大端值,计算新的分割点:若f1>f2,置a=x1,x1=x2,b=b,f1=f2,x2=a+b-x1,f2=f(x2)

若f1<=f2,置b=x2,x2=x1,a=a,f2=f1,x1=a+b-x2,f1=f(x1)4)收敛检查;如果(b-a)/L<=,则按照下面方式输出结果:若f1<f2,置x*=x1,f*=f1,a=a,b=x2;计算终止。否则,置x*=x2,f*=f2;,a=x1,b=b计算终止。否则,置k=k+1,返回3).通过上面分析可以估计给定容差的迭代次数N>lg

/log0.618例题用黄金分割法求解

minf(x)=x2-6x+10第二十五页,共四十五页,2022年,8月28日牛顿-拉夫逊法(牛顿切线法)

为了找到导数函数对应的驻点,采用根近似假设xk是当前驻点的近似解,则该点的f’(x)函数线性近似可以表示为

f’(x)f’(xk)+f”(xk)(x-xk)令此式为零,得出下一个近似点为

xk+1=xk-f’(xk)/f”(xk)收敛检查:例题:

用牛顿切线法求解

minf(x)=2x2+16/x第二十六页,共四十五页,2022年,8月28日2、二次插值法:

用设f(x)是区间[a,b]上的连续单峰函数,x1,x2,x3

是该区间上三个相邻点,它们的函数值分别为f1,f2,f3,且满足两边大中间小的条件,f1>f2<f3,求系数

ao,a1,a2,使得二次函数

q(x)=a0+a1(x-x1)+a2(x-x1)(x-x2)

在这三点上与f(x)的函数值相等,可得到所有的系数。由dq/dx=0可得例题用二次插值法求解minf(x)=2x2+16/x,在区间[1,1.5]内的最小值。第二十七页,共四十五页,2022年,8月28日3-3多维梯度法(f)

minf(x)

s.t.f:Rn→R(

f连续可微)

取极值的必要条件:若x*-l.opt.←→▽f(x*)=0(驻点)

说明:

f(x)

≥f(x*)+▽Tf(x*)(x-x*),x.

f(x*)

≤f(x),

x.(由于▽Tf(x*)=0

)1.最速下降法

方向:在迭代点x(k)

取方向d(k)=-▽f(x(k))

步长:精确一维搜索第二十八页,共四十五页,2022年,8月28日最速下降法(续)特点:

1)全局收敛,线性收敛;2)缺点:易产生扭摆现象而造成早停

(当x(k)距最优点较远时,速度快,而接近最优点时,速度下降)原因1:

f(x)=f(x(k))+▽Tf(x(k))(x-x(k))+o||x-x(k)||

当x(k)接近l.opt.时▽f(x(k)

)→0,于是高阶项

o||x-x(k)||的影响可能超过▽Tf(x(k))(x-x(k))

。原因2:第二十九页,共四十五页,2022年,8月28日最速下降法的流程x(1),ε>0,k=1||▽f(x(k))

||<ε?Yesstop.x(k)–解Nod(k)=-▽f(x(k))解minf(x(k)+λd(k))s.t.λ>0得x(k+1)=x(k)+λkd(k)k=k+1例题3-9用最速下降法求解:第三十页,共四十五页,2022年,8月28日3Newton法及其修正一、Newton法:

设f(x)二阶可微,取f(x)在x(k)点附近的二阶Taylor近似函数:

qk(x)=f(x(k))+▽Tf(x(k))(x-x(k))+(x-x(k))T▽2f(x(k))(x-x(k))

求驻点:

▽qk(x)=▽f(x(k))+▽2f(x(k))(x-x(k))=0

当▽2f(x(k))正定时,令上述方程解为x(k+1),有极小点:

Newton迭代公式:

x(k+1)=x(k)-[▽2f(x(k))]-1▽f(x(k))停止条件:||f(x(k))||<第三十一页,共四十五页,2022年,8月28日Newton法的计算流程x(1),ε>0,k=1

x(k+1)=x(k)+p(k)||f(x(k))||<?STOP.x(k+1)—l.optYesNok=k+1实用中,判断若▽2f(x(k))

非正定时进行相应处理例题3-11用Newton法计算Pk+1=-[▽2f(x(k))]-1▽f(x(k))第三十二页,共四十五页,2022年,8月28日特点:1)二阶收敛,局部收敛。(当x(k)充分接近x*时,局部函数可用正定二次函数很好地近似,故收敛很快)2)当f(x)为正定二次函数时,从任意初始点可一步迭代达到最优解说明:

设f(x)=xTQx+PTx+r,Qn×n对称正定,P∈Rn,r∈R.x(1),▽f(x(1))=Qx(1)+P▽2f(x(1))=Q迭代:

x(2)=x(1)-Q–1(Qx(1)+P)=-Q–1P(驻点即opt.)主要缺点:

(1)局部收敛

(2)用到二阶Hesse阵,且要求正定

(3)需计算Hesse阵逆或解n阶线性方程组,计算量大Newton法:(续)第三十三页,共四十五页,2022年,8月28日6、Newton法的改进(续)--------自己阅读和体会(1)为减小工作量,取m(正整数),使每m次迭代使用同一个Hesse阵,迭代公式变为:

x(km+j+1)=x(km+j)-[▽2f(x(km))]-1▽f(x(km+j))j=0,1,2,…,m-1,k=0,1,2,…

特点:收敛速度随m的增大而下降

m=1时即Newton法,m→∞即线性收敛。(2)带线性搜索的Newton法:在Newton迭代中,取d(k)=-[▽2f(x(k))]-1▽f(x(k)),

加入线性搜索:minf(x(k)+λkd(k))

求得λk,x(k+1)=x(k)+λkd(k)

特点:可改善局部收敛性,当d(k)为函数上升方向时,可向负方向搜索,但可能出现±d(k)均非下降方向的情况。第三十四页,共四十五页,2022年,8月28日二、算法流程图x(1),ε>0d(1)=-▽f(x(1)),k=1k=k+1k=1||▽f(x(k))||<ε?Stop.x(k)—解解minf(x(k)+λd(k))s.t.λ>0得λkx(k+1)=x(k)+λkd(k)

k=n?x(1)=x(n+1)d(1)=-▽f(x(1)),k=1求βkd(k+1)=-▽f(x(k+1))+βkd(k)yNyN重新开始第三十五页,共四十五页,2022年,8月28日6共轭梯度法共轭的概念:

对于方向pi,pj相对于nn对称正定矩阵Q共轭,则基本公式:停止条件:第三十六页,共四十五页,2022年,8月28日共轭梯度法算法特点1、全局收敛(下降算法);线性收敛;2、每步迭代只需存储若干向量(适用于大规模问题);3、有二次终结性(对于正定二次函数,至多n次迭代可达opt.)例题3-10

用共轭梯度法求解第三十七页,共四十五页,2022年,8月28日目标函数(f)minf(x),f:Rn→R1、基本思想:

用对称正定矩阵H(k)近似▽2f(x(k))的逆,而H(k)的产生从给定H(1)开始逐步修整得到。2、算法框图:x(1),H(1)对称ε>0,k=1d(k)=-H(k)▽f(x(k))一维搜索得λkx(k+1)=x(k)+λkd(k)||x(k+1)-x(k)||<ε?修正H(k)产生H(k+1)Stop.x(k+1)----解k=k+1yN5变尺度法第三十八页,共四十五页,2022年,8月28日5、变尺度法的主要特点:

⑴只需用到函数一阶梯度

(Newton法用到二阶Hesse阵)⑵下降算法,故全局收敛;⑶不需求矩阵逆;(计算量小)⑷一般可达到超线性收敛;(速度快)⑸有二次终结性。二DFP(Davidon(1959),FletcherandPowell(1963))法:

1、DFP法:以下省去各量上标,x,s,y,H

表示第k

步的量,等表示第k+1步的量。第三十九页,共四十五页,2022年,8月28日二、1、DFP法:(续)Ex.用DFP法求解minf(X)=10x12+x22解:取初始点x(1)=(1∕10,1)T,H(1)=I(单位矩阵)得到如下结果:(计算过程见下页)第四十页,共四十五页,2022年,8月28日第四十一页,共四十五页,2022年,8月28日2、BFGS法

BFGS(Broyden(1970),Fletcher(1970),Goldfarb(1970),Schanno(19

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论