最优化方法ppt课件解可新.ppt

1,前言一、什么是最优化 最优化是一门应用性相当广泛的学科，它讨论决策问题的最佳选择之特性，寻找最佳的计算方法，研究这些计算方法的理论性质及其实际计算表现。应用范围：信息工程及设计、经济规划、生产管理、交通运输、国防工业以及科学研究等诸多领域。,2,二、包含的内容按照优化思想分为经典方法与现代方法。经典方法主要包括：线性规划、非线性规划、整数规划、动态规划等现代方法主要包括：随机规划、模糊规划、模拟退火算法、遗传算法、禁忌搜索和人工神经网络等。我们学习的内容主要是经典的最优化方法。内容包括线性规划及其对偶规划，无约束最优化方法、约束最优化方法等主要内容。,3,目录,第一章 最优化问题概述第二章 线性规划第三章 无约束最优化方法第四章 约束最优化方法,第一章最优化问题概述,5,1.1 最优化问题的数学模型与基本概念,6,例 1.1.1 运输问题,设有m个水泥厂A1,A2,Am,年产量各为a1,a2,am吨.有k个城市B1,B2,Bk用这些水泥厂生产的水泥,年需求量b1,b2,bk吨.再设由Ai到Bj每吨水泥的运价为cij元.假设产销是平衡的,即:,试设计一个调运方案,在满足需要的同时使总运费最省.,7,A1,由题意可画出如下的运输费用图:,B2,Am,B1,A2,Bk,产量,需求量,设AiBj的水泥量为xij,已知AiBj单价为cij,单位为元,则总运费为:,8,数学模型:,注:平衡条件 作为已知条件并不出现在约束条件中.,9,例1.1.2 生产计划问题,设某工厂有m种资源B1,B2,Bm,数量分别为:b1,b2,bm,用这些资源产n种产品A1,A2,An.每生产一个单位的Aj产品需要消耗资源Bi的量为aij,根据合同规定,产品Aj的量不少于dj.再设Aj的单价为cj.问如何安排生产计划,才能既完成合同,又使该厂总收入最多?,10,假设产品Aj的计划产量为xj.由题意可画出如下的生产与消耗的关系图:,B1,B2,Bm,An,A2,A1,消耗,11,数学模型,12,例 1.1.3 指派问题,设有四项任务B1,B2,B3,B4派四个人A1,A2,A3,A4去完成.每个人都可以承担四项任务中的任何一项,但所消耗的资金不同.设Ai完成Bj所需资金为cij.如何分配任务,使总支出最少?设变量,指派Ai完成bj,不指派Ai完成bj,13,则总支出可表示为:,数学模型:,14,例 1.1.4 数据拟合问题,在实验数据处理或统计资料分析中常遇到如下问题.设两个变量x和y,已知存在函数关系,但其解析表达式或者是未知的或者虽然为已知的但过于复杂.设已取得一组数据:(xi,yi)i=1,2,m.根据这一组数据导出函数y=f(x)的一个简单而近似的解析表式.,15,最小二乘法,解这种问题常用的方法是最小二乘法,以一个简单的函数序列j1(x),j2(x),jn(x)为基本函数.一般选取1,x,x2,xn为基本函数,即以,作为近似表达式.,16,最小二乘法,系数的选取要使得下面得平方和最小:,因此,数据拟合问题得数学模型为,其中xi,yi(i=1,2,m)及jj(x)(j=0,1,n)为已知.,17,最优化问题,最优化问题的一般形式为:,(1.1)(目标函数),(1.3)(不等式约束),(1.2)(等式约束),其中x是n维向量.在实际应用中,可以将求最大值的目标函数取相反数后统一成公式中求最小值的形式.我们总是讨论,P:,18,相关定义,定义1.1.1(可行解)满足约束条件(1.2)和(1.3)的x称为可行解,也称为可行点或容许点.,定义1.1.2(可行域)全体可行解构成的集合称为可行域,也称为容许集,记为D,即:D=x|hi(x)=0,i=1,m,gj(x)0,j=1,p,xRn.若hi(x),gj(x)为连续函数,则D为闭集.,19,定义1.1.3(整体最优解)若x*D,对于一切xD恒有f(x*)f(x),则称x*为最优化问题(P)的整体最优解.若x*D,xx*,恒有f(x*)f(x),则称x*为最优化问题(P)的严格整体最优解.,相关定义,20,定义1.1.4(局部最优解)若x*D,存在x*的某邻域Ne(x*),使得对于一切xDNe(x*),恒有f(x*)f(x),则称为最优化问题(P)的局部最优解,其中Ne(x*)=x|x-x*|0.当xx*时,若上面的不等式为严格不等式则称x*为问题(P)的严格局部最优解.显然,整体最优解一定是局部最优解,而局部最优解不一定是整体最优解.x*对应的目标函数值f(x*)称为最优值，记为f*.,相关定义,21,求解最优化问题(P),就是求目标函数f(x)在约束条件(1.2),(1.3)下的极小点,实际上是求可行域D上的整体最优解.但是,在一般情况下,整体最优解是很难求出的,往往只能求出局部最优解.在求解时需要范数的概念，以下给出定义。,相关定义,22,向量范数,定义1.1.5 如果向量xRn 的某个实值函数|x|,满足条件(1)|x|0(|x|=0当且仅当x=0)(正定性);(2)|ax|=|a|x|(对于任意aR);(3)|x+y|x|+|y|(三角不等式);则称|x|为Rn 上的一个向量范数.,23,常用的向量范数,1-范数,2-范数(欧氏范数),-范数,p-范数,-范数是p-范数的极限,24,常用的向量范数,对向量x=(1,-2,3)T,有,|x|p是p的单调递减函数.,25,最优化问题的分类,根据数学模型中有无约束函数分为有约束的最优化问题和无约束的最优化问题.根据目标函数和约束函数的函数类型分类:线性最优化问题,非线性最优化问题,二次规划,多目标规划,动态规划,整数规划,0-1规划.,26,1.2 最优化问题的一般算法,27,迭代算法,迭代算法 选取一个初始可行点x0D,由这个初始可行点出发,依次产生一个可行点列:x1,x2,xk,记为xk,使得某个xk恰好是问题的一个最优解,或者该点列收敛到问题的一个最优解x*.下降算法 在迭代算法中一般要求 f(xk+1)f(xk).,28,可行点列的产生,在xk处求得一个方向pk(下降方向),在射线xk+apk(a 0)上求一点:xk+1=xk+akpk使得f(xk+1)f(xk).其中ak称为步长.定义1.2.1(下降方向)在点xk处,对于方向pk0,若存在实数b 0,使得任意的a(0,b),有:f(xk+apk)f(xk),则称pk为函数f(x)在点xk处的一个下降方向.,29,下降方向,若f(x)具有连续的一阶偏导数,令由Taylor公式:,当gkTpk0时,f(xk+apk)f(xk),所以pk是f(x)在xk处的一个下降方向.反之,当pk是f(x)在xk处的一个下降方向时,有gkTpk0.通常称满足gkTpk0的方向pk是为f(x)在xk处的一个下降方向.称为f(x)在x处的梯度。,30,可行方向,定义1.2.2(可行方向)已知区域,xkD,对于向量pk0,若存在实数b 0,使得对任意的a(0,b),有:xk+apkD,则称pk为点xk处关于区域D的可行方向.对于D的内点(存在邻域包含于D),任意方向可行,对于边界点(任意邻域既有D的点也有不在D中的点),则有些方向可行,有些方向不可行.若下降方向关于域D可行,则称为可行下降方向.,31,最优化问题的算法的一般迭代格式,给定初始点x0,令k=0.(1)确定xk处的可行下降方向pk;(2)确定步长ak,使得f(xk+akpk)f(xk),(3)令xk+1=xk+akpk;(4)若xk+1满足某种终止准则,则停止迭代,以xk+1为近似最优解;或者已经达到最大迭代步数,也可终止迭代.否则令k:=k+1,转(1),32,收敛性,如果一个算法只有当初始点x0充分接近x*时,产生的点列才收敛于x*,则称该算法为具有局部收敛的算法.如果对任意的x0D,由算法产生的点列都收敛x*,则称该算法为具有全局收敛的算法.由于一般情况下最优解x*是未知的,所以只有具有全局收敛性的算法才有实用意义.但算法的局部收敛性分析,在理论上是重要的,因为它是全局收敛性分析的基础。,33,收敛速度,定义1.2.3 设序列xk收敛于x*,而且,若0b1,则称xk为线性收敛的,称b为收敛比;,定义1.2.4 设序列xk收敛于x*,而且,若b=0,则称xk为超线性收敛的.,则称xk为p阶收敛.,34,终止准则,对于一种算法,应该有某种终止准则,当某次迭代满足终止准则时,就停止迭代.常用的终止准则有:,(1),或,(2),或,(3),(4)上面三种准则的组合.注:其中e 0是预先给定的.,35,1.3 二维最优化问题的几何解释,36,理论分析,二维最优化问题的目标函数z=f(x1,x2)表示三维空间R3中的曲面.在空间直角坐标系O-x1x2z中,平面z=c与曲面z=f(x1,x2)的交线在0-x1x2平面上的投影曲线为:,取不同的c值得到不同的投影曲线,每一条投影曲线对应一个c值,称投影曲线为目标函数的等值线或等高线.,37,38,理论分析,求目标函数z=f(x1,x2)在可行域D上的极小点,是在与可行域D有交集的等值线中找出具有最小值的等值线.也就是在可行域D上沿着f(x1,x2)的负梯度方向或某种下降方向上找取得最小值c的点.,39,例1.3.1,解 首先画出可行域D,目标函数的等值线是以点(1,2)为圆心的一族圆.f(x1,x2)的梯度为,40,例1.3.1,负梯度方向（下降方向）指向等值线圆心,所以等值线与可行域D的边界相切的点x*=(1/2,3/2)T 是此问题的最优解,目标函数的最优值为1/2.,41,例1.3.2,解 首先画出可行域D的图形.D为凸多边形 ODEFGO.再以c为参数画出目标函数的等值线2x1+3x2=c.,42,例1.3.2,目标函数c的值由小到大逐渐增加,等值线沿着目标函数的梯度方向平行移动.当移动到点E时,再移动就与可行域D不相交了,所以顶点E就是最优点,最优值为14.,43,例1.3.3,解 如图所示,可行域只能是圆弧ABE,其中点A和点E是等值线x1x2+1=0和圆x12+x22-9=0的交点.注意到等值线是平行的抛物线,图中画出了几条目标函数的等值线.容易看出B点是最优点,所以最优解是(0,-3)T,最优值为-3.,44,1.4 一维搜索,45,问题描述,已知xk,并且求出了xk处的可行下降方向pk,从 xk出发,沿方向pk求目标函数的最优解,即求解问题:,设其最优解为ak,于是得到一个新点xk+1=xk+ak pk所以一维搜索是求解一元函数f(a)的最优化问题(也叫一维最优化问题).我们来求解令()=0,求出的值。,46,在a,b内任取x1x2,1.4.1 黄金分割法,设f(x)在a,b上为下单峰函数,即有唯一的极小点x*,在x*左边f(x)严格下降,在x*右边 f(x)严格上升.,若f(x1)f(x2),则x*x1,b.,若f(x1)f(x2),则x*a,x2,47,黄金分割法,若第一次选取的试点为x1x2,则下一步保留的区间为a,x2或x1,b,两者的机会是均等的.因此我们选取试点时希望x2-a=b-x1.,a,b,x1,x2,设x1=a+p(b-a),则x2=a+(1-p)(b-a).,48,黄金分割法,另外,我们希望如果缩小的区间包含原来的试点,则该试点在下一步被利用.若保留的区间为a,x2,前一次的试点x1在这个区间内.,a,b,x1,x2,a,b,x2,49,黄金分割法,a,b,x1,x2,a,b,x2,我们希望原来的x1,在缩小的区间内成为新的“x2”.我们根据这一条件来计算p.,计算x2的公式为,x2=a+(1 p)(b a).,因此我们希望,a+p(b a)=a+(1p)(a+(1 p)(b a)a),x2=a+(1 p)(b a).,即,p2-3p+1=0,化简得,50,黄金分割法,若保留区间为x1,b,我们得到的结果是一致的.该方法称为黄金分割法,实际计算取近似值:x1=a+0.382(b a),x2=a+0.618(b a),所以黄金分割法又称为0.618法.黄金分割法每次缩小区间的比例是一致的,每次将区间长度缩小到原来的0.618倍.,51,算法1.4.2 黄金分割法,给定a,b(a0,step 1 令x2=a+0.618(b-a),f2=f(x2);step 2 令x1=a+0.382(b-a),f1=f(x1);step 3 若|b a|f2,则a=x2,x1=x2,f1=f2,转step 5;step 5 令x2=a+0.618(b a)，f2=f(x2),转step3.,52,例1.4.1 用黄金分割法求函数f(x)=x2-x+2在区间-1,3上的极小值，要求区间长度不大于原始区间长的0.08。,53,用0.618法求解例1.4.1的数据表,54,进退法(寻找下单峰区间),在一维搜索之前,必须先知道一个f(x)的下单峰区间.书中的算法1.4.3给出了求函数的一般的下单峰区间的算法.此处我们对算法1.4.3加以改进,求出f(x)的一个形如0,b形式的下单峰区间,因为我们关心的问题是:,我们的目的是找出两个点x1x2,使得f(x1)f(x2),f(x1)f(0).,55,进退法(寻找下单峰区间),给定初始点x0=0,初始步长Dx0,x1=x0+Dx.,x0,下面分两种情况讨论.,(1)f(x1)f(x0)x1对应着图上用红线标出的一部分,56,进退法(寻找下单峰区间),x0,(1)f(x1)f(x0),此时x1取值小,我们加大步长向右搜索,取Dx=2Dx,x2=x1+Dx,若f(x1)f(x2),则我们要找的区间即为x0,x2,x1,x2,Dx,2Dx,57,进退法(寻找下单峰区间),x0,(1)f(x1)f(x0),若f(x1)f(x2),则我们所取的步长偏小.令x1=x2,Dx=2Dx,x2=x1+Dx继续往下判断,直到满足f(x1)f(x2).,x1,x2,Dx,2Dx,x1,x2,58,进退法(寻找下单峰区间),x0,(2)f(x1)f(x0),此时x1取值大,我们缩小步长向x1左边搜索,取Dx=Dx/2,x2=x1,x1=x2-Dx,若f(x1)f(x0),则我们要找的区间即为x0,x2否则继续缩小区间,直到满足f(x1)f(x0).,x1,x2,x1,59,1.4.2 二分法,若f(x)的导数存在且容易计算,则线性搜索的速度可以得到提高,下面的二分法每次将区间缩小至原来的二分之一.设f(x)为下单峰函数,若f(x)在a,b具有连续的一阶导数,且f(a)0取 c=(a+b)/2,若f(c)=0,则c为极小点;若f(c)0,则以a,c代替a,b作为新区间;若f(c)0,则以c,b代替a,b作为新区间.,60,1.4.3 抛物线法,在求一元函数的极小点问题上,我们可以利用若干点处的函数值来构造一个多项式,用这个多项式的极小点作为原来函数极小点的近似值.抛物线法就是一个用二次函数来逼近f(x)的方法,这也是我们常说的二次插值法.设在已知的三点x1f0,f0f2过三点(x1,f1),(x0,f0),(x2,f2)作二次函数y=j(x),即作一条抛物线,则可推导出：,61,为求j(x)的极小点,令j(x)=0,得:,62,若 充分接近,即对于预先给定的精度,有,则把 作为近似极小点.,否则计算,找出 和 之间的大者,去掉 或,使新的三点仍具有两端点的函数值大于中间点的函数值的性质.利用新的点再构造二次函数,继续进行迭代.,63,1.4.4 不精确的一维搜索,前面介绍的得几种一维搜索方法,都是为了获得一元函数f(x)的最优解,所以习惯上称为精确一维搜索.在解非线性规划问题中,一维搜索一般很难得到真正的精确值.因此,不精确的一维搜索开始为人们所重视.即在xk点确定了下降方向pk后,只计算少量的几个函数就可得到一个满足f(xk+1)f(xk)的近似点xk+1.,64,不精确的一维搜索,对于不精确的一维搜索,要求产生的点列具有某种收敛性.所以除了对下降方向pk有要求之外,对步长ak也有要求,即要求目标函数要“充分的下降”.下面令f(a)=f(xk+a pk),我们讨论ak满足的条件.,65,不精确一维搜索,对于一元函数f(a),精确一维搜索的条件为f(ak)=0.不精确一维搜索的条件f(ak)0,或|f(ak)|s.实际计算中上式不好控制,一般的方法是|f(ak)/f(0)|s.s的选取：不宜太大否则下降不够充分；不宜太小否则“太精确”.适合的范围：比1稍小一些.,66,不精确一维搜索,例：函数f(a)=(a-1)2.f(a)=2(a-1),f(0)=-2.取s=0.5,则控制条件为|f(ak)|s|f(0)|=1,即|2(ak-1)|1,1/2 ak3/2.,67,不精确一维搜索的Wolfe原则,设f(x)可微,取m(0,1/2),s(m,1),选取a k 0,使,或用下面更强的条件代替(1.7)式:,68,Wolfe原则,关于满足Wolfe原则的步长ak的存在性:定理1.4.2 设f(x)有下界且 gkTpk0.令m(0,1/2),s(m,1),则存在区间c1,c2,使得任意的ac1,c2均满足式(1.6)和(1.7)(也满足(1.8).,69,不精确一维搜索Wolfe算法,问题:设已知xk和下降方向pk,求问题,的近似值ak,使ak 满足(1.6)和(1.7).,算法1.4.6 不精确一维搜索Wolfe算法step 1 给定m(0,1),s(m,1),令a=0,b=,a=1,k=0;step2 xk+1=xk+a pk,计算fk+1,gk+1;,70,若a 满足(1.6)和(1.7)式,则令ak=a;若a 不满足(1.6)式,则令k:=k+1,转step 3;若a 不满足(1.7)式,则令k:=k+1,转step 4;step 3 令 转step 2 step 4 令 转step 2.,71,step 1 给定m=0.1,s=0.5,令a=0,b=,a=1,j=0;,Wolfe准则(例1.4.2),用不精确一维搜索求Rosenbrock函数f(x)=100(x2-x12)2+(1-x1)2在点xk=(0,0)T处沿方向pk=(1,0)T的近似步长ak.解,72,因为fkfk+1=1100=99ma gkTpk=0.2所以(1.6)式成立。转step 3,step 2 xk+1=xk+a pk=(1,0)T,fk+1=f(1,0)=100,step 3 令b=1,a=(a+a)/2=(1+0)/2=0.5,转step 2.重新计算xk+1.,迭代四次得到满足Wolfe条件的步长ak=0.125xk+1=xk+ak pk=(0.125,1)T.,