非线性-无约束规划课件

章章无约束非线性最优化方无约束非线性最优化方法法基本模型基本模型:用符号用符号(fs)表示非线性规划表示非线性规划1）方向导数方向导数设设M0位数量场位数量场u=u(M)中的一点中的一点,从点从点M0出发引一出发引一条射线条射线l,在在l上点上点M0的附近取一动点的附近取一动点M,记记如果如果 时，下列表达式的极限存在时，下列表达式的极限存在则称之为则称之为M0处沿着处沿着l方向的方向导数方向的方向导数.记为记为当当 时时,表示函数表示函数u沿沿l是增加方向是增加方向,当当 时时,表示函数表示函数u沿沿l是减小方向。是减小方向。1.方向导数与梯度2）直角坐标系中方向导数的计算公式直角坐标系中方向导数的计算公式定理定理1.若函数若函数u=u(x,y,z)在点在点M0(x0,y0,z0)处可微处可微;为为l的方向余弦的方向余弦,则函数则函数u在点在点M0处处沿沿l方向导数必然存在，且有下面公式计算方向导数必然存在，且有下面公式计算其中其中 是在是在M0附近的偏导数附近的偏导数.例题例题1 求函数求函数 在点在点M(1,0,1)处沿着处沿着 方向的方向导数方向的方向导数解解:3)梯度梯度：根据方向导数公式：根据方向导数公式可以知道可以知道 是其变化率最快的方向是其变化率最快的方向,称为称为梯度梯度,记为记为Grad u.如果用如果用 表示表示l线线上的单位矢量上的单位矢量,则方向导数可以写成则方向导数可以写成梯度的性质梯度的性质：1)方向导数等于梯度在该方向的投影方向导数等于梯度在该方向的投影.即即2)数量场数量场u=u(M)中任一点中任一点M处的梯度处的梯度,垂直于过该点垂直于过该点的等值面的等值面,且指向且指向u(M)增大的一方增大的一方.例例3 设设 为点为点M(x,y,z)的矢径的矢径 的模的模,试证试证2.海瑟矩阵 海瑟矩阵是对称形式：3 非线性规划问题的展开形式 多元函数泰勒公式的矩阵形式多元函数泰勒公式的矩阵形式：其中线性函数线性函数：f(X)=CTX+B=ci xi +B二次函数二次函数：f(X)=(1/2)XTQX+CTX+Bf(x)=f(x*)+f T(x)(x-x*)+(1/2)(x-x*)T 2f(x*)(x-x*)+ox-x*24 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性质性质:当当-f(x)为凸函数（严格凸函数）时，则称为凸函数（严格凸函数）时，则称 f(x)为凹函数（严格凹函数）。为凹函数（严格凹函数）。严格凸函数严格凸函数凸函数凸函数严格凹函数严格凹函数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(x),g(x)=min f1(x),f2(x)是否凸函数？是否凸函数？凸规划凸规划=凸可行集凸可行集+凸目标函数凸目标函数凸函数与凹函数凸函数与凹函数(续续)凸函数的凸函数的判定判定:如果函数f(X)的Hesse矩阵处处半正定，则f(X)为凸函数，若f(X)正定，则f(X)为严格凸函数。注注:该命题的逆命题不成立该命题的逆命题不成立例题 检验函数的凸性。无约束问题的最优性条件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*为鞍点；为鞍点；(阅读课本的例题阅读课本的例题)6 6 最优化问题的最优化问题的数值解数值解 VS VS 解析解解析解1.解析解与数值解解析解与数值解 注意获得解析解的困难性。注意获得解析解的困难性。2、收敛性概念：收敛性概念：考虑考虑(fs)设迭代算法产生点列设迭代算法产生点列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*时，算法才收敛。时，算法才收敛。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*8.收敛速度收敛速度 设算法产生点列设算法产生点列x(k),收敛到解收敛到解x*,且且x(k)x*，k，1.线性收敛：线性收敛：当当k充分大时成充分大时成立立2.超线性收敛：超线性收敛：3.二阶二阶(次次)收敛：收敛：0，当，当k充分大时有充分大时有定理定理：设算法点列：设算法点列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、收敛速度（续）、收敛速度（续）4.1 4.1 常用的搜索算法结构常用的搜索算法结构 考虑（考虑（fs）常用一种线性搜索的方式构造常用一种线性搜索的方式构造xk序列来求解序列来求解 迭代中从一点出发沿下降可行方向找一个迭代中从一点出发沿下降可行方向找一个新的、更优的点。新的、更优的点。下降方向下降方向 ：设设 S，d Rn,d0,若存在若存在 ，使使 ，称，称d 为为 在在 点的下降方向点的下降方向。min f(x)s.t.xS4 4 常用的搜索算法结构常用的搜索算法结构可行方向可行方向：设设 S，dRn,d0,若存在若存在 使使 ，称称d 为该点的可行方向为该点的可行方向。同时满足上述两个性质的方向称同时满足上述两个性质的方向称 下降可行方向。下降可行方向。迭代算法的停止标准1）2）3）对于无约束问题可以用10 10 常用的搜索算法结构常用的搜索算法结构线性搜索求线性搜索求 ，新点新点使使x(k+1)S初始初始x(1)S,k=1对对x(k)点选择下降点选择下降可行方向可行方向d(k)是否满足停机条件？是否满足停机条件？停停k=k+1yesno11 11 一维搜索一维搜索一元函数求极小及线性搜索均为一维搜索。常用于求：一元函数求极小及线性搜索均为一维搜索。常用于求：min f(x(k)+d(k)=()s.t.S S有有3种情况种情况（-，+）或（）或（0，+）或）或a,b一、缩小区间的精确一维搜索：考虑问题一、缩小区间的精确一维搜索：考虑问题(P)min()s.t.,为此先介绍为此先介绍不确定区间及单峰函数不确定区间及单峰函数的概念的概念 不确定区间：不确定区间：,含含()的最小点，的最小点，但不知其位置但不知其位置单峰的概念单峰的概念一、缩小区间的精确一维搜索（续）一、缩小区间的精确一维搜索（续）若对任意若对任意1,2,1 (2);2 若若 1*，则，则(1)(2).则称则称()在在,上强单峰。上强单峰。若只有当若只有当(1)(*)，(2)(*)时，上述时，上述1,2 式才成立式才成立，则称则称()在在,上单峰。上单峰。*1 2 强单峰强单峰 *单峰单峰 设设f(X)是目标函数，如果是目标函数，如果 是在给定是在给定Xk和方向和方向矢量矢量Pk下，通过下，通过f(x)=f(xk+akPk)的极小化而产生的极小化而产生则称则称 为为最优步长最优步长。根据单变量的驻点条件根据单变量的驻点条件:以及复合函数的求导法则可得：以及复合函数的求导法则可得：1.精确一维搜索（假定求目标函数极小值）精确一维搜索（假定求目标函数极小值）2 2 一维搜索一维搜索一、缩小区间的精确一维搜索（续）一、缩小区间的精确一维搜索（续）定理：定理：设设：RR 在在，上单峰，上单峰，x1 x2 。那么那么 1若若(x1)(x2)，则去除，则去除 ，x2；如左下图；如左下图 2若若(x1)(x2)，则则 去除去除x2，；如右下图；如右下图 x1 x2 x1 x2 12 12 一维搜索一维搜索2、黄金分割法（、黄金分割法（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=,则按照下面方式输出结果：则按照下面方式输出结果：若若f1lg/log 0.618例题例题 用黄金分割法求解用黄金分割法求解 min f(x)=x2-6x+10牛顿牛顿-拉夫逊法拉夫逊法(牛顿切线法牛顿切线法)为了找到导数函数对应的驻点，采用根近似假设xk是当前驻点的近似解，则该点的f(x)函数线性近似可以表示为 f(x)f(xk)+f”(xk)(x-xk)令此式为零，得出下一个近似点为 xk+1=xk-f(xk)/f”(xk)收敛检查：例题:用牛顿切线法求解 min f(x)=2x2+16/x2、二次插值法：、二次插值法：用设用设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 用最速下降法求解用最速下降法求解:3 Newton法及其修正法及其修正一、一、Newton法法：设设f(x)二阶可微，取二阶可微，取f(x)在在x(k)点附近的二阶点附近的二阶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)k=n?x(1)=x(n+1)d(1)=-f(x(1),k=1求 kd(k+1)=-f(x(k+1)+kd(k)yNyN重新开始6 共轭梯度法共轭的概念共轭的概念:对于方向pi,pj相对于nn对称正定矩阵Q共轭，则基本公式:停止条件:共轭梯度法算法特点共轭梯度法算法特点1、全局收敛（下降算法）；线性收敛；、全局收敛（下降算法）；线性收敛；2、每步迭代只需存储若干向量、每步迭代只需存储若干向量(适用于大规模问题适用于大规模问题)；3、有二次终结性（对于正定二次函数，至多、有二次终结性（对于正定二次函数，至多n次迭代次迭代 可达可达opt.）例题例题 3-10 用共轭梯度法求解用共轭梯度法求解 目标函数目标函数 (f)min f(x),f:R n 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)+k d(k)|x(k+1)-x(k)|0,(单纯形法中单纯形法中=1)2 扩展扩展：给定扩展系数：给定扩展系数 1,计算。（加速）计算。（加速）若若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 用单纯形法求解用单纯形法求解