非线性无约束规划优秀PPT.ppt
《非线性无约束规划优秀PPT.ppt》由会员分享,可在线阅读,更多相关《非线性无约束规划优秀PPT.ppt(45页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、非线性无约束规划第一页,本课件共有45页1)方向导数方向导数设设M0位数量场位数量场u=u(M)中的一点中的一点,从点从点M0出发引一出发引一条射线条射线l,在在l上点上点M0的附近取一动点的附近取一动点M,记记如果如果 时,下列表达式的极限存在时,下列表达式的极限存在则称之为则称之为M0处沿着处沿着l方向的方向导数方向的方向导数.记为记为当当 时时,表示函数表示函数u沿沿l是增加方向是增加方向,当当 时时,表示函数表示函数u沿沿l是减小方向。是减小方向。1.方向导数与梯度第二页,本课件共有45页2)直角坐标系中方向导数的计算公式直角坐标系中方向导数的计算公式定理定理1.若函数若函数u=u(x
2、,y,z)在点在点M0(x0,y0,z0)处可微处可微;为为l的方向余弦的方向余弦,则函数则函数u在点在点M0处处沿沿l方向导数必然存在,且有下面公式计算方向导数必然存在,且有下面公式计算其中其中 是在是在M0附近的偏导数附近的偏导数.例题例题1 求函数求函数 在点在点M(1,0,1)处沿着处沿着 方向的方向导数方向的方向导数解解:第三页,本课件共有45页3)梯度梯度:根据方向导数公式:根据方向导数公式可以知道可以知道 是其变化率最快的方向是其变化率最快的方向,称为称为梯度梯度,记为记为Grad u.如果用如果用 表示表示l线线上的单位矢量上的单位矢量,则方向导数可以写成则方向导数可以写成梯度
3、的性质梯度的性质:1)方向导数等于梯度在该方向的投影方向导数等于梯度在该方向的投影.即即2)数量场数量场u=u(M)中任一点中任一点M处的梯度处的梯度,垂直于过该点垂直于过该点的等值面的等值面,且指向且指向u(M)增大的一方增大的一方.例例3 设设 为点为点M(x,y,z)的矢径的矢径 的模的模,试证试证第四页,本课件共有45页2.海瑟矩阵 海瑟矩阵是对称形式:第五页,本课件共有45页3 非线性规划问题的展开形式 多元函数泰勒公式的矩阵形式多元函数泰勒公式的矩阵形式:其中线性函数线性函数:f(X)=CTX+B=ci xi +B二次函数二次函数:f(X)=(1/2)XTQX+CTX+Bf(x)=
4、f(x*)+f T(x)(x-x*)+(1/2)(x-x*)T 2f(x*)(x-x*)+ox-x*2第六页,本课件共有45页4 4 凸集、凸函数和凸规划凸集、凸函数和凸规划1)凸函数)凸函数 定义定义:设集合设集合 S Rn 为凸集,函数为凸集,函数 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 上的严格凸函数。上的严格凸函数。l性质性质:当当
5、-f(x)为凸函数(严格凸函数)时,则称为凸函数(严格凸函数)时,则称 f(x)为凹函数(严格凹函数)。为凹函数(严格凹函数)。严格凸函数严格凸函数凸函数凸函数严格凹函数严格凹函数第七页,本课件共有45页2.2 2.2 凸集、凸函数和凸规划凸集、凸函数和凸规划(续续)定理定理:f(x)为凸集为凸集 S 上的凸函数上的凸函数 S 上任上任意有限点的凸组合的函数值不大于各点函意有限点的凸组合的函数值不大于各点函数值的凸组合。数值的凸组合。l思考思考:设:设f1,f2是凸函数,是凸函数,1)设设 1,2 0,1f1+2f2,1f1-2f2是否凸函是否凸函数?数?2)f(x)=max f1(x),f2
6、(x),g(x)=min f1(x),f2(x)是否凸函数?是否凸函数?凸规划凸规划=凸可行集凸可行集+凸目标函数凸目标函数第八页,本课件共有45页凸函数与凹函数凸函数与凹函数(续续)凸函数的凸函数的判定判定:如果函数f(X)的Hesse矩阵处处半正定,则f(X)为凸函数,若f(X)正定,则f(X)为严格凸函数。注注:该命题的逆命题不成立该命题的逆命题不成立例题 检验函数的凸性。第九页,本课件共有45页无约束问题的最优性条件1.必要条件必要条件:若:若X*是函数是函数f(X)的局部最大点,则在该点必有的局部最大点,则在该点必有 f(X*)=0以及以及Hesse矩阵矩阵 2f(X*)半正定半正定
7、 定义定义:对于可微函数对于可微函数f(X),称使其梯度为零向量的点为称使其梯度为零向量的点为平平稳点(驻点)稳点(驻点)。2.若若X*是驻点,则其为极值点的是驻点,则其为极值点的充分条件充分条件:1)若若H(X*)半正定,半正定,X*为局部极小点;为局部极小点;若若H(X*)正定,正定,X*为孤立局部极小点;为孤立局部极小点;2)若若H(X*)半负定,半负定,X*为局部极大点;为局部极大点;若若H(X*)负定,负定,X*为孤立局部极大点;为孤立局部极大点;3)若若H(X*)不定,不定,X*为鞍点;为鞍点;(阅读课本的例题阅读课本的例题)第十页,本课件共有45页6 6 最优化问题的最优化问题的
8、数值解数值解 VS VS 解析解解析解1.解析解与数值解解析解与数值解 注意获得解析解的困难性。注意获得解析解的困难性。2、收敛性概念:收敛性概念:考虑考虑(fs)设迭代算法产生点列设迭代算法产生点列x(k)S.1)算法的算法的理想收敛理想收敛:设:设x*S是是(fs)的最优解,如果的最优解,如果x*x(k),或者虽然,或者虽然 x(k)x*,但是但是 k,满足满足 则则称算法收敛到最优解称算法收敛到最优解 x*。第十一页,本课件共有45页 概念概念:1)局部最优局部最优:2)全局最优全局最优:3)严格全局最优严格全局最优 以及以及 4)全局收敛:全局收敛:对任意初始点对任意初始点x(1),算
9、法均收敛。算法均收敛。5)局部收敛:局部收敛:当当x(1)充分接近解充分接近解x*时,算法才收敛。时,算法才收敛。第十二页,本课件共有45页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*第十三页,本课件共有45页8.收敛速度收敛速度 设算法产生点列设算法产生点列x(k),收敛到解收敛到解x
10、*,且且x(k)x*,k,1.线性收敛:线性收敛:当当k充分大时成立充分大时成立2.超线性收敛:超线性收敛:3.二阶二阶(次次)收敛:收敛:0,当,当k充分大时有充分大时有第十四页,本课件共有45页定理定理:设算法点列:设算法点列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、收敛速度(续)、收敛速度(续)第十五页,本课件共有45页4.1 4.1 常用的搜
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 非线性 无约束 规划 优秀 PPT
限制150内