非线性-无约束规划.ppt

《非线性-无约束规划.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四章无约束非线性最优化方法基本模型:用符号(fs)表示非线性规划1）方向导数设M0位数量场u=u(M)中的一点,从点M0出发引一条射线l,在l上点M0的附近取一动点M,记如果时，下列表达式的极限存在则称之为M0处沿着l方向的方向导数.记为,则当时,表示函数u沿l是增加方向,当时,表示函数u沿l是减小方向。1.方向导数与梯度2)梯度：根据方向导数公式可以知道是其变化率最快的方向,称为梯度,记为Gradu.如果用表示l线上的单位矢量,则方向导数可以写成3)梯度的性质：1)方向导数等于梯度在该方向的投影,即2)数量场u=u(M)中任一点M处的梯度,垂直于过该点的等值面,且指向u(M)增大

2、的一方.2.海瑟矩阵海瑟矩阵是对称形式：3.非线性规划问题的展开形式3)多元函数泰勒公式的矩阵形式：其中1)线性函数：f(X)=CTX+B=cixi+B2)二次函数：f(X)=(1/2)XTQX+CTX+Bf(x)=f(x*)+fT(x)△xi+(1/2)△xiT2f(x*)△xi+o‖△xi‖24.凸集、凸函数和凸规划-请自己复习1)定理:f(x)为凸集S上的凸函数S上任意有限点的凸组合的函数值不大于各点函数值的凸组合。2)凸函数的判定:如果函数f(X)的Hesse矩阵处处半正定，则f(X)为凸函数，若f(X)正定，则f(X)为严格凸函数。思考：设f1,f2是凸函数，设1

3、,2>0,1f1+2f2,1f1-2f2是否凸函数？f(x)=max{f1(x),f2(x)},g(x)=min{f1(x),f2(x)}是否凸函数？凸规划=凸可行集+凸目标函数5.无约束问题的最优性条件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*为孤立

4、局部极大点；3)若H(X*)不定，X*为鞍点；请阅读课本的例题。6最优化问题的数值解VS解析解1.解析解与数值解(结构:x(k+1)=x(k)+kd(k).)注意获得解析解的困难性。2、收敛性概念：考虑(fs)设迭代算法产生点列{x(k)}x(k)}S.1)算法的理想收敛：设x*∈S是(fs)的最优解，如果x*∈{x(k)}，或者虽然x(k)≠x*，但是k，满足则称算法收敛到最优解x*。最终解的分类1)局部最优解；2)全局最优解；3)严格全局最优解。解序列对于初始点的依赖4)全局收敛：对任意初始点x(1),算法均收敛。5)局部收敛：当x(1)充分接近解x*时，算法才收敛。7.非

5、线性最优解的概念6）实用收敛性：定义最优解集如下S*={x

6、x具有某种性质}例：S*={x

7、x---g.opt}S*={x

8、x---l.opt}S*={x

9、f(x)=0}S*={x

10、f’(x)≤β}(β为给定实数,称为阈值）当下列情况之一成立时，称算法收敛具有该性质点1°x(k)∈S*;2°k，{X(k)}任意极限点∈S*8.收敛速度设算法产生点列{x(k)},收敛到解x*,且x(k)≠x*，k，满足下列条件时称为相应的收敛1.线性收敛：当k充分大时成立2.超线性收敛：3.二阶(次)收敛：﹥0，当k充分大时有定理：设算法点列{x(k)}超线性收敛于x*,且x(k)≠x*，

11、k，那么证明只需注意

12、

13、

14、x(k+1)–x*

15、

16、-

17、

18、x(k)–x*

19、

20、

21、≤

22、

23、x(k+1)–x(k)

24、

25、≤

26、

27、x(k+1)–x*

28、

29、+

30、

31、x(k)–x*

32、

33、，除以

34、

35、x(k)–x*

36、

37、并令k→∞，利用超线性收敛定义可得结果。8、收敛速度（续）9.迭代算法的停止标准1）2）3）对于无约束问题可以用10.常用的搜索算法结构考虑（fs）基本思路：构造{xk}序列来逼近驻点(最优点)1)方向搜索△下降方向：设∈S，d∈Rn,d≠0,若存在，使，称d为在点的下降方向。minf(x)s.t.x∈S10常用的搜索算法结构(续)△可行方向：设∈S，d∈Rn,d≠0,若存在使，称d为该点的可行方向

38、。同时满足上述两个性质的方向称下降可行方向。10常用的搜索算法结构(续)线性搜索求，新点使x(k+1)∈S初始x(1)∈S,k=1对x(k)点选择下降可行方向d(k)是否满足停机条件？停k=k+1yesno设f(X)是目标函数，如果是在给定Xk和方向矢量Pk下，通过f(x)=f(xk+akPk)的极小化而产生则称为最优步长。根据单变量的驻点条件:df(xk+akPk)/dak=0（当ak=ak*时）以及复合函数的求导法则可得：1)精确一维搜索（假定求目标函