《非线性无约束规划 (2)精选PPT.ppt》由会员分享，可在线阅读，更多相关《非线性无约束规划 (2)精选PPT.ppt（36页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、非线性无约束规划第1页，此课件共36页哦1）方向导数方向导数设设M0位数量场位数量场u=u(M)中的一点中的一点,从点从点M0出发引一出发引一条射线条射线l,在在l上点上点M0的附近取一动点的附近取一动点M,记记如果如果 时，下列表达式的极限存在时，下列表达式的极限存在则称之为则称之为M0处沿着处沿着l方向的方向导数方向的方向导数.记为记为 ,则则当当 时时,表示函数表示函数u沿沿l是增加方向是增加方向,当当 时时,表示函数表示函数u沿沿l是减小方向。是减小方向。1.方向导数与梯度第2页，此课件共36页哦2)梯度梯度：根据方向导数公式：根据方向导数公式可以知道可以知道 是其变化率最快的方向是其
2、变化率最快的方向,称为称为梯度梯度,记为记为Grad u.如果用如果用 表示表示l线线上的单位矢量上的单位矢量,则方向导数可以写成则方向导数可以写成3)梯度的性质梯度的性质：1)方向导数等于梯度在该方向的投影方向导数等于梯度在该方向的投影,即即2)数量场数量场u=u(M)中任一点中任一点M处的梯度处的梯度,垂直于过该点垂直于过该点的等值面的等值面,且指向且指向u(M)增大的一方增大的一方.第3页，此课件共36页哦2.海瑟矩阵 海瑟矩阵是对称形式：第4页，此课件共36页哦3.非线性规划问题的展开形式3)多元函数泰勒公式的矩阵形式多元函数泰勒公式的矩阵形式：其中 1)线性函数线性函数：f(X)=C
3、TX+B=ci xi +B 2)二次函数二次函数：f(X)=(1/2)XTQX+CTX+Bf(x)=f(x*)+f T(x)xi+(1/2)xiT 2f(x*)xi +o xi 2第5页，此课件共36页哦4.4.凸集、凸函数和凸规凸集、凸函数和凸规划划-请自己复习请自己复习 1)定理定理:f(x)为凸集为凸集 S 上的凸函数上的凸函数 S 上任意有限点的凸上任意有限点的凸组合的函数值不大于各点函数值的凸组合。组合的函数值不大于各点函数值的凸组合。2)2)凸函数的凸函数的判定判定:如果函数如果函数f(X)的的HesseHesse矩阵处处半正定，则矩阵处处半正定，则f(X)为凸函数，为凸函数，若若
4、f(X)正定，则正定，则f(X)为严格凸函数。为严格凸函数。l思考思考：设：设f1,f2是凸函数，是凸函数，1)设设 1,2 0,1f1+2f2,1f1-2f2是否凸函数？是否凸函数？2)f(x)=max f1(x),f2(x),g(x)=min f1(x),f2(x)是否是否凸函数？凸函数？凸规划凸规划=凸可行集凸可行集+凸目标函数凸目标函数第6页，此课件共36页哦5.无约束问题的最优性条件1.必要条件必要条件：若：若X*是函数是函数f(X)的局部最小点，则在该点必有的局部最小点，则在该点必有 f(X*)=0以及以及Hesse矩阵矩阵 2f(X*)半正定半正定 定义定义:对于可微函数对于可微
5、函数f(X),称使其梯度为零向量的点为称使其梯度为零向量的点为平稳平稳点（驻点）点（驻点）。2.若若X*是驻点，则其为极值点的是驻点，则其为极值点的充分条件充分条件:1)若若H(X*)半正定，半正定，X*为局部极小点；为局部极小点；若若H(X*)正定，正定，X*为孤立局部极小点；为孤立局部极小点；2)若若H(X*)半负定，半负定，X*为局部极大点；为局部极大点；若若H(X*)负定，负定，X*为孤立局部极大点；为孤立局部极大点；3)若若H(X*)不定，不定，X*为鞍点；为鞍点；请请阅读课本的例题。阅读课本的例题。第7页，此课件共36页哦6 6 最优化问题的最优化问题的数值解数值解 VS 解析解解
6、析解1.解析解与数值解解析解与数值解(结构结构:x(k+1)=x(k)+k d(k).)注意获得解析解的困难性。注意获得解析解的困难性。2、收敛性概念：收敛性概念：考虑考虑(fs)设迭代算法产生点列设迭代算法产生点列x(k)x(k)S.1)算法的算法的理想收敛理想收敛：设：设x*S是是(fs)的最优解，如果的最优解，如果 x*x(k)，或者虽然，或者虽然 x(k)x*，但是但是 k，满足满足 则则称算法收敛到最优解称算法收敛到最优解 x*。第8页，此课件共36页哦 最终解的分类最终解的分类 1)局部最优解；局部最优解；2)全局最优解；全局最优解；3)严格全局最优解。严格全局最优解。解序列对于初
7、始点的依赖解序列对于初始点的依赖 4)全局收敛：全局收敛：对任意初始点对任意初始点x(1),算法均收敛。算法均收敛。5)局部收敛：局部收敛：当当x(1)充分接近解充分接近解x*时，算法才收敛。时，算法才收敛。7.非线性最优解的概念非线性最优解的概念第9页，此课件共36页哦 6）实用收敛性实用收敛性：定义最优解集如下定义最优解集如下 S*=x|x 具有某种性质具有某种性质 例：例：S*=x|x-g.opt S*=x|x-l.opt S*=x|f(x)=0 S*=x|f(x)(为给定实数为给定实数,称为阈值称为阈值）当下列情况当下列情况之一之一成立时，称算法收敛具有该性质点成立时，称算法收敛具有该
8、性质点 1 x(k)S*;2 k，X(k)任意极限点任意极限点S*第10页，此课件共36页哦8.收敛速度收敛速度 设算法产生点列设算法产生点列x(k),收敛到解收敛到解x*,且且x(k)x*，k，满足下列条件时称为相应的收敛满足下列条件时称为相应的收敛1.线性收敛：线性收敛：当当k充分大时成立充分大时成立2.超线性收敛：超线性收敛：3.二阶二阶(次次)收敛：收敛：0，当，当k充分大时有充分大时有第11页，此课件共36页哦定理定理：设算法点列：设算法点列x(k)超线性收敛于超线性收敛于x*,且且x(k)x*，k，那么那么证明只需注意证明只需注意|x(k+1)x*|-|x(k)x*|x(k+1)x
9、(k)|x(k+1)x*|+|x(k)x*|，除以，除以|x(k)x*|并令并令k，利用超线，利用超线性收敛定义可得结果。性收敛定义可得结果。8、收敛速度（续）、收敛速度（续）第12页，此课件共36页哦9.9.迭代算法的停止标准迭代算法的停止标准1）2）3）对于无约束问题可以用第13页，此课件共36页哦10.常用的搜索算法结构常用的搜索算法结构 考虑（考虑（fs）基本思路：基本思路：构造构造xk序列来逼近驻点序列来逼近驻点(最优点最优点)1)方向搜索方向搜索下降方向下降方向 ：设设 S，d Rn,d0,若存在若存在 ，使，使 ，称，称d 为为 在在 点的下降方向点的下降方向。min f(x)s
10、.t.xS第14页，此课件共36页哦10 10 常用的搜索算法结构常用的搜索算法结构(续续续续)可行方向可行方向：设设 S，dRn,d0,若存在若存在 使使 ，称称d 为该点的可行方向为该点的可行方向。同时满足上述两个性质的方向称同时满足上述两个性质的方向称 下降可行方向。下降可行方向。第15页，此课件共36页哦10 10 常用的搜索算法结构常用的搜索算法结构常用的搜索算法结构常用的搜索算法结构(续续续续)线性搜索求线性搜索求 ，新点新点使使x(k+1)S初始x(1)S,k=1对对x(k)点选择下降点选择下降可行方向可行方向d(k)是否满足停机条件？停k=k+1yesno第16页，此课件共36
11、页哦 设设f(X)是目标函数，如果是目标函数，如果 是在给定是在给定Xk和方向和方向矢量矢量Pk下，通过下，通过f(x)=f(xk+akPk)的极小化而产生的极小化而产生则称则称 为为最优步长最优步长。根据单变量的驻点条件根据单变量的驻点条件:d f(xk+akPk)/dak=0 （当（当ak=ak*时）时）以及复合函数的求导法则可得：以及复合函数的求导法则可得：1)精确一维搜索精确一维搜索（假定求目标函数极小值）（假定求目标函数极小值）11.最优步长的一维搜索最优步长的一维搜索第17页，此课件共36页哦2）缩小区间的非精确一维搜索缩小区间的非精确一维搜索缩小区间的非精确一维搜索缩小区间的非精
12、确一维搜索（1）单峰的概念单峰的概念 若对任意若对任意1,2,1 (2);2 若若 1*，则，则(1)(2).则称则称()在在,上强单峰。上强单峰。若只有当若只有当(1)(*)，(2)(*)时，上述时，上述1,2 式才成立式才成立，则称则称()在在,上单峰。上单峰。*1 2 强单峰强单峰 *单峰单峰第18页，此课件共36页哦2)缩小区间的非精确一维搜索（续）缩小区间的非精确一维搜索（续）定理：定理：设设：RR 在在，上单峰，上单峰，x1 x2 。那么那么 1若若(x1)(x2)，则去除，则去除 ，x2；如左下图；如左下图 2若若(x1)(x2)，则则 去除去除x2，；如右下图；如右下图 x1
13、x2 x1 x2 第19页，此课件共36页哦3)黄金分割法（黄金分割法（0.618 法法）选二点选二点x10,k=12)计算初始分割点，计算初始分割点，x1=a+0.382L,f1=f(x1);x2=a+0.618L,f2=f(x2)3)消去大端值，计算新的分割点：消去大端值，计算新的分割点：若若 f1f2,置置 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=,则按照下面方式输出结果：则按照下面方式输出结果：若若f
14、1lg/log 0.618例题例题 用黄金分割法求解用黄金分割法求解 min f(x)=x2-6x+10第21页，此课件共36页哦4）二次插值法：）二次插值法：用设用设f(x)是区间是区间a,b上的连续单峰函数，上的连续单峰函数，x1,x2,x3 是该区间上三个是该区间上三个相邻点，它们的函数值分别为相邻点，它们的函数值分别为f1,f2,f3,且满足两边大中间小的条件，且满足两边大中间小的条件，f1 f20,k=1|f(x(k)|0得得 x(k+1)=x(k)+kd(k)k=k+1例题例题3-9 用最速下降法求解用最速下降法求解:第25页，此课件共36页哦2）牛顿-拉夫逊法(牛顿切线法)为了找
15、到导数函数对应的驻点，采用根近似方法为了找到导数函数对应的驻点，采用根近似方法假设假设xk是当前驻点的近似解，则该点的是当前驻点的近似解，则该点的f(x)函数线性函数线性近似可以表示为近似可以表示为 f(x)f(xk)+f”(xk)(x-xk)令此式为零，得出下一个近似点为令此式为零，得出下一个近似点为 xk+1=xk-f(xk)/f”(xk)收敛检查：收敛检查：例题例题:用牛顿切线法求解用牛顿切线法求解 min f(x)=2x2+16/x第26页，此课件共36页哦3)Newton法及其修正法及其修正(1)Newton法法：设设f(x)二阶可微，取二阶可微，取f(x)在在x(k)点附近的二阶点
16、附近的二阶Taylor近似函数：近似函数：qk(x)=f(x(k)+Tf(x(k)(x-x(k)+(x-x(k)T2f(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)-1f(x(k)停止条件停止条件:|f(x(k)|0,k=1 x(k+1)=x(k)+p(k)|f(x(k)|0d(1)=-f(x(1),k=1k=k+1k=1|f(x(k)|0得 k x(k+1)=x(k)+k d(k
17、)k=n?x(1)=x(n+1)d(1)=-f(x(1),k=1求 kd(k+1)=-f(x(k+1)+kd(k)yNyN重新开始第31页，此课件共36页哦4)4)共轭梯度法共轭梯度法共轭的概念共轭的概念:对于方向pi,pj相对于nn对称正定矩阵Q共轭，则基本公式:停止条件:第32页，此课件共36页哦共轭梯度法算法特点共轭梯度法算法特点共轭梯度法算法特点共轭梯度法算法特点1、全局收敛（下降算法）；线性收敛；、全局收敛（下降算法）；线性收敛；2、每步迭代只需存储若干向量、每步迭代只需存储若干向量(适用于大规模问题适用于大规模问题)；3、有二次终结性（对于正定二次函数，至多、有二次终结性（对于正定
18、二次函数，至多n次迭代次迭代 可达可达opt.）例题例题 3-10 用共轭梯度法求解用共轭梯度法求解第33页，此课件共36页哦5）多维直接算法多维直接算法-单纯形法单纯形法单纯形法单纯形法 (目标函数最小为最优目标函数最小为最优)设设 x(0),x(1),x(n)是是R n中中n+1个点构成的一个当前的单纯形。比较各点个点构成的一个当前的单纯形。比较各点的函数值得到：的函数值得到：x max,x min使使 f(x max)=maxf(x(0),f(x(1),f(x(n)f(x min)=minf(x(0),f(x(1),f(x(n)取单纯形中除去取单纯形中除去x max点外，其他所有点的形心
19、：点外，其他所有点的形心：去掉去掉x max，加入，加入x(n+1)得到新的单纯形。得到新的单纯形。重复上述过程。重复上述过程。优点：不需求导数，不需要一维搜索。优点：不需求导数，不需要一维搜索。缺点：无法加速，收敛慢，有时效果差。缺点：无法加速，收敛慢，有时效果差。第34页，此课件共36页哦 单纯形法的基本步骤单纯形法的基本步骤-可变多面体算法可变多面体算法 设第设第k步迭代得到步迭代得到n+1个点：个点：x(0),x(1),x(n)，得到，得到x max,x min 及通过及通过4步求新顶点步求新顶点,初始点选择初始点选择:1 反射反射：取反射系数取反射系数 0,(单纯形法中单纯形法中=1
20、)2 扩展扩展：给定扩展系数：给定扩展系数 1,计算。（加速）计算。（加速）第35页，此课件共36页哦 若若f(y(1)f(y(2),那么那么y(2)取代取代x max;否则，否则，y(1)取代取代x max。若若maxf(x(i)|x(i)x max f(y(1)f(x min),y(1)取代取代x max。3 收缩收缩：若：若f(x max)f(y(1)f(x(i),x(i)x max,计算计算 ,以以y(3)取代取代x max。4 减半减半：若：若f(y(1)f(x max),重新取各点，使重新取各点，使 x(i)=x min+12(x(i)-x min)得到新单纯形。得到新单纯形。算法停机准则取：算法停机准则取：例题例题3-13 用单纯形法求解用单纯形法求解 第36页，此课件共36页哦