第一章-最优化问题概述-最优化方法课件

最优化方法2 2目录目录第一章第一章 最优化问题概述最优化问题概述第二章第二章 线性规划线性规划第三章第三章 无约束最优化方法无约束最优化方法第四章第四章 约束最优化方法约束最优化方法第一章最优化问题概述4 41.1 最优化问题的数学模型最优化问题的数学模型与基本概念与基本概念5 5例例 1.1.1 运输问题运输问题设有设有m个水泥厂个水泥厂A1,A2,Am,年产量各为年产量各为a1,a2,am吨吨.有有k个城市个城市B1,B2,Bk用这些水泥用这些水泥厂生产的水泥厂生产的水泥,年需求量年需求量b1,b2,bk吨吨.再设由再设由Ai到到Bj每吨水泥的运价为每吨水泥的运价为cij元元.假设产销是平衡假设产销是平衡的的,即即:试设计一个调运方案试设计一个调运方案,在满足需要的同时使总在满足需要的同时使总运费最省运费最省.6 6A1 由题意可画出如下的运输费用图由题意可画出如下的运输费用图:B2AmB1A2Bk产量产量需求量需求量设设AiBj的水泥量为的水泥量为xij,已知已知AiBj单价为单价为cij,单单位为元位为元,则总运费为则总运费为:7 7数学模型数学模型:注注:平衡条件平衡条件 作为已知条件并不作为已知条件并不出现在约束条件中出现在约束条件中.8 8例例1.1.2 生产计划问题设某工厂有设某工厂有m种资源种资源B1,B2,Bm,数量各为数量各为:b1,b2,bm,用这些资源产用这些资源产n种产品种产品A1,A2,An.每生产一个单位的每生产一个单位的Aj产品需要消耗资源产品需要消耗资源Bi的的量为量为aij,根据合同规定根据合同规定,产品产品Aj的量不少于的量不少于dj.再再设设Aj的单价为的单价为cj.问如何安排生产计划问如何安排生产计划,才能既完成合同才能既完成合同,又使该又使该厂总收入最多厂总收入最多?9 9假设产品假设产品Aj的计划产量为的计划产量为xj.由题意可画出如下的生产与消耗的关系图由题意可画出如下的生产与消耗的关系图:B1B2BmAnA2A1消耗消耗1010数学模型数学模型1111例例 1.1.3 指派问题指派问题设有四项任务设有四项任务B1,B2,B3,B4派四个人派四个人A1,A2,A3,A4去完成去完成.每个人都可以承担四项任务中的每个人都可以承担四项任务中的任何一项任何一项,但所消耗的资金不同但所消耗的资金不同.设设Ai完成完成Bj所所需资金为需资金为cij.如何分配任务如何分配任务,使总支出最少使总支出最少?设变量设变量指派指派Ai完成完成bj不指派不指派Ai完成完成bj1212则总支出可表示为则总支出可表示为:数学模型数学模型:1313例例 1.1.4 数据拟合问题数据拟合问题 在实验数据处理或统计资料分析中常遇到如在实验数据处理或统计资料分析中常遇到如下问题下问题.设两个变量设两个变量x和和y,已知存在函数关系已知存在函数关系,但但其解析表达式或者是未知的或者虽然为已知其解析表达式或者是未知的或者虽然为已知的但过于复杂的但过于复杂.设已取得一组数据设已取得一组数据:(xi,yi)i=1,2,m.根据这一组数据导出函数根据这一组数据导出函数y=f(x)的一个简单而的一个简单而近似的解析表式近似的解析表式.1414最小二乘法最小二乘法解这种问题常用的方法是最小二乘法解这种问题常用的方法是最小二乘法,以一个以一个简单的函数序列简单的函数序列j j1(x),j j2(x),j jn(x)为基本函数为基本函数.一般选取一般选取1,x,x2,xn为基本函数为基本函数,即以即以作为近似表达式作为近似表达式.1515最小二乘法最小二乘法系数的选取要使得下面得平方和最小系数的选取要使得下面得平方和最小:因此因此,数据拟合问题得数学模型为数据拟合问题得数学模型为其中其中xi,yi(i=1,2,m)及及j jj(x)(j=0,1,n)为已知为已知.1616最优化问题最优化问题最优化问题的一般形式为最优化问题的一般形式为:(1.1)(目标函数目标函数)(1.3)(不等式约束不等式约束)(1.2)(等式约束等式约束)其中其中x是是n维向量维向量.在实际应用中在实际应用中,可以将求最大值的目标函数取可以将求最大值的目标函数取相反数后统一成公式中求最小值的形式相反数后统一成公式中求最小值的形式.1717相关定义相关定义定义定义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为闭集为闭集.1818相关定义相关定义定义定义1.1.3 (整体最优解整体最优解)若若x*D,对于一切对于一切xD恒有恒有f(x*)f(x),则称则称x*为最优化问题为最优化问题(P)的的整体最优解整体最优解.若若x*D,xx*,恒有恒有f(x*)f(x),则称则称x*为最优为最优化问题化问题(P)的严格整体最优解的严格整体最优解.1919相关定义相关定义定义定义1.1.4 (局部最优解局部最优解)若若x*D,存在存在x*的某的某邻域邻域Ne e(x*),使得对于一切使得对于一切xDNe e(x*),恒有恒有f(x*)f(x),则称为最优化问题则称为最优化问题(P)的局部最优解的局部最优解,其中其中Ne e(x*)=x|x-x*|0.当当xx*时时,若上面的不等式为严格不等式则称若上面的不等式为严格不等式则称x*为问题为问题(P)的严格局部最优解的严格局部最优解.显然显然,整体最优解一定是局部最优解整体最优解一定是局部最优解,而局部最而局部最优解不一定是整体最优解优解不一定是整体最优解.2020相关定义相关定义求解最优化问题求解最优化问题(P),就是求目标函数就是求目标函数f(x)在约在约束条件束条件(1.2),(1.3)下的极小点下的极小点,实际上是求可行实际上是求可行域域D上的整体最优解上的整体最优解.但是但是,在一般情况下在一般情况下,整体整体最优解是很难求出的最优解是很难求出的,往往只能求出局部最优往往只能求出局部最优解解.2121向量范数向量范数定义定义1.1.5 如果向量如果向量xRn 的某个实值函数的某个实值函数|x|,满足条件满足条件(1)|x|0(|x|=0当且仅当当且仅当x=0)(正定性正定性);(2)|a ax|=|a a|x|(对于任意对于任意a aR);(3)|x+y|x|+|y|(三角不等式三角不等式);则称则称|x|为为Rn 上的一个向量范数上的一个向量范数.2222常用的向量范数常用的向量范数1-范数范数2-范数范数(欧式范数欧式范数)-范数范数p-范数范数-范数是范数是p-范数的极限范数的极限2323常用的向量范数常用的向量范数对向量对向量x=(1,-2,3)T,有有|x|p是是p的单调递减函数的单调递减函数.2424最优化问题的分类最优化问题的分类根据数学模型中有无约束函数分为有约束的根据数学模型中有无约束函数分为有约束的最优化问题和无约束的最优化问题最优化问题和无约束的最优化问题.根据目标函数和约束函数的函数类型分类根据目标函数和约束函数的函数类型分类:线线性最优化问题性最优化问题,非线性最优化问题非线性最优化问题,二次规划二次规划,多多目标规划目标规划,动态规划动态规划,整数规划整数规划,0-1规划规划.25251.2 最优化问题的一般算法最优化问题的一般算法2626迭代算法迭代算法迭代算法迭代算法 选取一个初始可行点选取一个初始可行点x0D,由这个由这个初始可行点出发初始可行点出发,依次产生一个可行点列依次产生一个可行点列:x1,x2,xk,记为记为xk,使得某个使得某个xk恰好是问题的一个最优解恰好是问题的一个最优解,或者该点列收敛到问题的一个最优解或者该点列收敛到问题的一个最优解x*.下降算法下降算法 在迭代算法中一般要求在迭代算法中一般要求 f(xk+1)f(xk).2727可行点列的产生可行点列的产生在在xk处求得一个方向处求得一个方向pk(下降方向下降方向),在射线在射线xk+a apk(a a 0)上求一点上求一点:xk+1=xk+a akpk使得使得f(xk+1)f(xk).其中其中a ak称为步长称为步长.定义定义1.2.1(下降方向下降方向)在点在点xk处处,对于方向对于方向pk0,若存在实数若存在实数b b 0,使得任意的使得任意的a a(0,b b),有有:f(xk+a apk)f(xk),则称则称pk为函数为函数f(x)在点在点xk处的一个下降方向处的一个下降方向.2828下降方向下降方向若若f(x)具有连续的一阶偏导数具有连续的一阶偏导数,令令由由Taylor公式公式:当当gkTpk0时时,f(xk+a apk)f(xk),所以所以pk是是f(x)在在xk处的一个下降方向处的一个下降方向.反之反之,当当pk是是f(x)在在xk处的一个下降方向时处的一个下降方向时,有有gkTpk0(书中有错书中有错).通常称满足通常称满足gkTpk0,使得对任意的使得对任意的a a(0,b b),有有:xk+a apkD,则称则称pk为点为点xk处关于区域处关于区域D的可行方向的可行方向.对于对于D的内点的内点(存在邻域包含于存在邻域包含于D),任意方向可任意方向可行行,对于边界点对于边界点(任意邻域既有任意邻域既有D的点也有不在的点也有不在D中的点中的点),则有些方向可行则有些方向可行,有些方向不可行有些方向不可行.若下降方向关于域若下降方向关于域D可行可行,则称为可行下降方向则称为可行下降方向.3030最优化问题的算法的一般迭代格式最优化问题的算法的一般迭代格式给定初始点给定初始点x0,令令k=0.(1)确定确定xk处的可行下降方向处的可行下降方向pk;(2)确定步长确定步长a ak,使得使得f(xk+a akpk)f(xk),(3)令令x xk k+1+1=x xk k+a a a ak kp pk k;(4)若若x xk k+1+1满足某种终止准则满足某种终止准则,则停止迭代则停止迭代,以以x xk k+1+1为近似最优解为近似最优解;或者已经达到最大迭代步或者已经达到最大迭代步数数,也可终止迭代也可终止迭代.否则令否则令k:=k+1,转转(1)3131收敛性收敛性如果一个算法只有当初始点如果一个算法只有当初始点x0充分接近充分接近x*时时,产生的点列才收敛于产生的点列才收敛于x*,则称该算法为具有局则称该算法为具有局部收敛的算法部收敛的算法.如果对任意的如果对任意的x0D,由算法产生的点列都收敛由算法产生的点列都收敛x*,则称该算法为具有全局收敛的算法则称该算法为具有全局收敛的算法.由于一般情况下最优解由于一般情况下最优解x*是未知的是未知的,所以只有所以只有具有全局收敛性的算法才有实用意义具有全局收敛性的算法才有实用意义.但算法但算法的局部收敛性分析的局部收敛性分析,在理论上是重要的在理论上是重要的,因为它因为它是全局收敛性分析的基础。是全局收敛性分析的基础。3232收敛速度收敛速度定义定义1.2.3 设序列设序列xk收敛于收敛于x*,而且而且若若0b b0是预先给定的是预先给定的.34341.3 二维最优化问题的几何解释二维最优化问题的几何解释3535理论分析理论分析二维最优化问题的目标函数二维最优化问题的目标函数z=f(x1,x2)表示三表示三维空间维空间R3中的曲面中的曲面.在空间直角坐标系在空间直角坐标系O-x1x2z中中,平面平面z=c与曲面与曲面z=f(x1,x2)的交线在的交线在0-x1x2平平面上的投影曲线为面上的投影曲线为:取不同的取不同的c值得到不同的投影曲线值得到不同的投影曲线,每一条投影每一条投影曲线对应一个曲线对应一个c值值,称投影曲线为目标函数的等称投影曲线为目标函数的等值线或等高线值线或等高线.36363737理论分析理论分析求目标函数求目标函数z=f(x1,x2)在可行域在可行域D上的极小点上的极小点,是在与可行域是在与可行域D有交集的等值线中找出具有有交集的等值线中找出具有最小值的等值线最小值的等值线.也就是在可行域也就是在可行域D上沿着上沿着f(x1,x2)的负梯度方向或某种下降方向上找取的负梯度方向或某种下降方向上找取得最小值得最小值c的点的点.3838例例1.3.1解解 首先画出可行域首先画出可行域D,目标函数的等值线是以目标函数的等值线是以点点(1,2)为圆心的一族圆为圆心的一族圆.f(x1,x2)的梯度为的梯度为3939例例1.3.1负梯度方向指向负梯度方向指向等值线圆心等值线圆心,所以所以等值线与可行域等值线与可行域D的边界相切的点的边界相切的点x*=(1/2,3/2)T 是此是此问题的最优解问题的最优解,目目标函数的最优值标函数的最优值为为1/2.4040例例1.3.2解解 首先画出可行域首先画出可行域D的图形的图形.D为凸多边形为凸多边形 ODEFGO.再以再以c为参数画出目标函数的等值为参数画出目标函数的等值线线2x1+3x2=c.4141例例1.3.2目标函数目标函数c的值由的值由小到大逐渐增加小到大逐渐增加,等等值线沿着目标函数值线沿着目标函数的梯度方向平行移的梯度方向平行移动动.当移动到点当移动到点E时时,再移动就与可行域再移动就与可行域D不相交了不相交了,所以顶所以顶点点E就是最优点就是最优点,最最优值为优值为14.4242例例1.3.3解解 如图所示如图所示,可行域只能是可行域只能是圆弧圆弧ABE,其中点其中点A和点和点E是是等值线等值线x1x2+1=0和圆和圆x12+x22-9=0的交点的交点.注意到等注意到等值线是平行的抛物线值线是平行的抛物线,图中画图中画出了几条目标函数的等值线出了几条目标函数的等值线.容易看出容易看出B点是最优点点是最优点,所以所以最优解是最优解是(0,-3)T,最优值为最优值为-3.43431.4 一维搜索一维搜索4444问题描述问题描述已知已知xk,并且求出了并且求出了xk处的可行下降方向处的可行下降方向pk,从从 xk出发出发,沿方向沿方向pk求目标函数的最优解求目标函数的最优解,即求解即求解问题问题:设其最优解为设其最优解为a ak,于是得到一个新点于是得到一个新点xk+1=xk+a ak pk所以一维搜索是求解一元函数所以一维搜索是求解一元函数f f(a a)的最优化问的最优化问题题(也叫一维最优化问题也叫一维最优化问题).我们来求解我们来求解4545在在a,b内任取内任取x1x2,1.4.1 Fibonacci法与黄金分割法法与黄金分割法 设设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 4646Fibonacci方法方法如果只有一个试点如果只有一个试点x,我们无法将区间缩小我们无法将区间缩小.如果知道两个试点如果知道两个试点x1b-a,因此因此max(x2-a,b-x1)(b-a)/2.我们尽量靠近我们尽量靠近a,b中点来取点中点来取点.一般取一般取x1=(b-a)/2,x2=x1+0.1(b-a),或者或者x2=(b-a)/2,x1=x2-0.1(b-a).4747Fibonacci法法下面我们考虑任给一个下面我们考虑任给一个f(x)的单峰区间的单峰区间a,b,如如果给定试点的个数果给定试点的个数n,如何使最后确定的包含最如何使最后确定的包含最优值的区间尽量的小优值的区间尽量的小.另一种思维方式为另一种思维方式为,按什么方式取点按什么方式取点,求求n次函数次函数值之后值之后,可最多将多长的原始区间长度缩小为可最多将多长的原始区间长度缩小为1.设设Ln为试点个数为为试点个数为n,最终区间长度为最终区间长度为1时时,原始区原始区间间a,b的最大可能长度。的最大可能长度。4848Fibonacci法法设最初两个试点为设最初两个试点为x1和和x2,若极小点在若极小点在a,x1内内,至至多还有多还有n2个试点个试点,则则x1-aLn2.若极小点在若极小点在x1,b内内,包括包括x2在内可以有在内可以有n1个试个试点点,则则bx1Ln1.因此因此,LnLn1+Ln2.如果我们采取合适的技巧如果我们采取合适的技巧,可以使得可以使得Ln=Ln1+Ln2.另外另外,显然有显然有L0=L1=1.4949Fibonacci数列数列从而从而Ln满足差分方程满足差分方程:此为此为Fibonacci数列数列,一般写为一般写为:Fibonacci数列的前几个数据为：数列的前几个数据为：5050Fibonacci法法若原始区间为若原始区间为a,b,要求最终的区间长度要求最终的区间长度e e,则则Fn(b-a)/e e,由此可确定由此可确定n,区间缩短之后与之前区间缩短之后与之前的比依次为的比依次为:n确定之后确定之后,最初两个试点最初两个试点(关于关于a,b对称对称)分分别为别为:5151Fibonacci法法上述过程完成了一次迭代上述过程完成了一次迭代,新区间仍记为新区间仍记为a,b.若已经进行了若已经进行了i 1次迭代次迭代,第第i次迭代时次迭代时,还有还有ni+1个试点个试点(包括已计算过的一个函数值包括已计算过的一个函数值).注注:(1)最后的两个试点取的方式最后的两个试点取的方式:x1=(b-a)/2,x2=x1+0.1(b-a).(2)若若f(x1)与与 f(x2)近似相等近似相等,则认为则认为x*在在x1,x2内内.5252例例1.4.1(Fibonacci方法方法)用用Fibonacci法求函数法求函数f(x)=x2-x+2在区间在区间-1,3上上的极小点的极小点.要求最终区间长度不大于原始区间长要求最终区间长度不大于原始区间长度的度的0.08倍。倍。由由Fn1/0.08=12.5,可知可知n应取应取6(F6=13).解解 函数函数f(x)在区间在区间-1,3上为下单峰函数上为下单峰函数,5353第一次迭代第一次迭代(a=1,b=3)f1 f2,缩短后区间为缩短后区间为-1,1.462x1=0.538x2=1.4625535454x1=-0.077第二次迭代第二次迭代(a=1,b=1.462)332新区间为新区间为-0.077,1.4625555第三次迭代第三次迭代(a=-0.077,b=1.462)新区间为新区间为 新区间为新区间为第四次迭代第四次迭代(a=-0.077,b=0.846)5656第五次迭代第五次迭代(a=0.231,b=0.846)取最优解取最优解5757Fibonacci方法评价方法评价Fibonacci方法的优点方法的优点(1)如果缩小的区间包含原来的试点如果缩小的区间包含原来的试点,则该试点则该试点在下一步被利用在下一步被利用(2)效率最高效率最高,有限个试点的情况下有限个试点的情况下,将最优点所将最优点所在的区间缩小到最小在的区间缩小到最小.Fibonacci方法的缺点方法的缺点(1)搜索前先要计算搜索的步数搜索前先要计算搜索的步数(2)每次搜索试点计算的公式不一致每次搜索试点计算的公式不一致5858黄金分割法黄金分割法我们希望保留我们希望保留Fibonacci方法的优点方法的优点(效率最高效率最高是不可能保留的是不可能保留的),改进其缺点改进其缺点.若第一次选取的试点为若第一次选取的试点为x1x2,则下一步保留的则下一步保留的区间为区间为a,x2或或x1,b,两者的机会是均等的两者的机会是均等的.因此我们选取试点时希望因此我们选取试点时希望x2-a=b-x1.abx1x2设设x1=a+p(b-a),则则x2=a+(1-p)(b-a).5959黄金分割法黄金分割法另外另外,我们希望如果缩小的区间包含原来的试点我们希望如果缩小的区间包含原来的试点,则该试点在下一步被利用则该试点在下一步被利用.若保留的区间为若保留的区间为a,x2,前一次的试点前一次的试点x1在这个区在这个区间内间内.abx1x2abx26060黄金分割法黄金分割法abx1x2abx2我们希望原来我们希望原来的的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化简得化简得6161黄金分割法黄金分割法若保留区间为若保留区间为x1,b,我们得到的结果是一致的我们得到的结果是一致的.该方法称为黄金分割法该方法称为黄金分割法,实际计算取近似值实际计算取近似值:x1=a+0.382(b a),x2=a+0.618(b a),所以黄金分割法又称为所以黄金分割法又称为0.618法法.黄金分割法每次缩小区间的比例是一致的黄金分割法每次缩小区间的比例是一致的,每每次将区间长度缩小到原来的次将区间长度缩小到原来的0.618倍倍.6262算法算法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|e e,则则 x*=(a+b)/2,Stop.step 4 若若f1f2,则则a=x2,x1=x2,f1=f2,转转step 5;step 5 令令x2=a+0.618(b a)，f2=f(x2),转转step3.6363用用0.618法求解例法求解例1.4.1的数据表的数据表迭代迭代迭代迭代次数次数次数次数a,bx1x2f1f2|b b-a a|e e e e0 0-1,3-1,30.5280.5281.4721.472 1.7511.751 2.6952.695否否否否1 1-1,1.472-1,1.472-0.056-0.056 0.5280.528 2.0592.059 1.7511.751否否否否2 2-0.056,1.4720.056,1.4720.5280.5280.8880.888 1.7511.751 1.9011.901否否否否3 3-0.056,0.8880.056,0.8880.3050.3050.5280.528 1.7881.788 1.7511.751否否否否4 40.305,0.8880.305,0.8880.5280.5280.6650.665 1.7511.751 1.7771.777否否否否5 50.305,0.6650.305,0.6650.4430.4430.5280.528 1.7531.753 1.7511.751否否否否6 60.443,0.6650.443,0.6650.5280.5280.5800.580 1.7511.751 1.7571.757是是是是 最优解最优解x*=(0.443+0.665)/2=0.55464640.618法和法和Fibonacci之间的关系之间的关系0.618法为法为Fibonacci法的极限形式法的极限形式.65650.618法和法和Fibonacci之间的关系之间的关系迭迭代代步步数数的的比比较较 0.618法法:Fibonacci方法方法:忽略忽略 得到得到 黄金分割黄金分割法至多比法至多比Fibonacci法多一步法多一步6666进退法进退法(寻找下单峰区间寻找下单峰区间)在一维搜索之前在一维搜索之前,必须先知道一个必须先知道一个f(x)的下单峰的下单峰区间区间.书中的算法书中的算法1.4.3给出了求函数的一般的下给出了求函数的一般的下单峰区间的算法单峰区间的算法.此处我们对算法此处我们对算法1.4.3加以改进加以改进,求出求出f(x)的一个形如的一个形如0,b形式的下单峰区间形式的下单峰区间因为我们关心的问题是因为我们关心的问题是:我们的目的是找出两个点我们的目的是找出两个点x10,x1=x0+D Dx.x0下面分两种情况讨论下面分两种情况讨论.(1)f(x1)f(x0)x1对应着图上用红线标出的一部分对应着图上用红线标出的一部分6868进退法进退法(寻找下单峰区间寻找下单峰区间)x0(1)f(x1)f(x0)此时此时x1取值小取值小,我们加大步长向右搜索我们加大步长向右搜索,取取D Dx=2D Dx,x2=x1+D Dx若若f(x1)f(x2),则我们要找的区间即为则我们要找的区间即为x0,x2x1x2D Dx2D2Dx6969进退法进退法(寻找下单峰区间寻找下单峰区间)x0(1)f(x1)f(x0)若若f(x1)f(x2),则我们所取的步长偏小则我们所取的步长偏小.令令x1=x2,D Dx=2D Dx,x2=x1+D Dx继续往下判断继续往下判断,直到满足直到满足f(x1)f(x2).x1x2D Dx2D2Dxx1x27070进退法进退法(寻找下单峰区间寻找下单峰区间)x0(2)f(x1)f(x0)此时此时x1取值大取值大,我们缩小步长向我们缩小步长向x1左边搜索左边搜索,取取D Dx=D Dx/2,x2=x1,x1=x2 -D Dx若若f(x1)f(x0),则我们要找的区间即为则我们要找的区间即为x0,x2否则继续缩小区间否则继续缩小区间,直到满足直到满足f(x1)f(x0).x1x2x171711.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,则以则以b,c代替代替a,b作为新区间作为新区间.72721.4.3 抛物线法抛物线法在求一元函数的极小点问题上在求一元函数的极小点问题上,我们可以利用若我们可以利用若干点处的函数值来构造一个多项式干点处的函数值来构造一个多项式,用这个多项用这个多项式的极小点作为原来函数极小点的近似值式的极小点作为原来函数极小点的近似值.抛物线法就是一个用二次函数来逼近抛物线法就是一个用二次函数来逼近f(x)的方法的方法,这也是我们常说的二次插值法这也是我们常说的二次插值法.设在已知的三点设在已知的三点x1x0f0,f0f2过三点过三点(x1,f1),(x0,f0),(x2,f2)作二次函数作二次函数y=j j(x),即作即作一条抛物线一条抛物线,则可推导出：则可推导出：7373为求为求j j(x)的极小点的极小点,令令j j(x)=0,得得:7474若若 充分接近充分接近 ,即对于预先给定的精度即对于预先给定的精度 ,有有 ,则把则把 作为近似极小点作为近似极小点.否则计算否则计算 ,找出找出 和和 之间的大者之间的大者,去去掉掉 或或 ,使新的三点仍具有两端点的函数值使新的三点仍具有两端点的函数值大于中间点的函数值的性质大于中间点的函数值的性质.利用新的点再构造利用新的点再构造二次函数二次函数,继续进行迭代继续进行迭代.75751.4.4 不精确的一维搜索不精确的一维搜索前面介绍的得几种一维搜索方法前面介绍的得几种一维搜索方法,都是为了获都是为了获得一元函数得一元函数f(x)的最优解的最优解,所以习惯上称为精确所以习惯上称为精确一维搜索一维搜索.在解非线性规划问题中在解非线性规划问题中,一维搜索一般很难得一维搜索一般很难得到真正的精确值到真正的精确值.因此因此,不精确的一维搜索开始为人们所重视不精确的一维搜索开始为人们所重视.即在即在xk点确定了下降方向点确定了下降方向pk后后,只计算少量的只计算少量的几个函数就可得到一个满足几个函数就可得到一个满足f(xk+1)f(xk)的近的近似点似点xk+1.7676不精确的一维搜索不精确的一维搜索对于不精确的一维搜索对于不精确的一维搜索,要求产生的点列具有要求产生的点列具有某种收敛性某种收敛性.所以除了对下降方向所以除了对下降方向pk有要求之有要求之外外,对步长对步长a ak也有要求也有要求,即要求目标函数要即要求目标函数要“充充分的下降分的下降”.下面令下面令f f(a a)=f(xk+a a pk),我们讨论我们讨论a ak满足的条件满足的条件.7777不精确一维搜索不精确一维搜索对于一元函数对于一元函数f f(a a),精确一维搜索的条件为精确一维搜索的条件为f f(a ak)=0.不精确一维搜索的条件不精确一维搜索的条件f f(a ak)0,或或|f f(a ak)|s s.实际计算中上式不好控制实际计算中上式不好控制,一般的方法是一般的方法是|f f(a ak)/f f(0 0)|s s.s s的选取：不宜太大的选取：不宜太大否则下降不够充分；否则下降不够充分；不宜太小不宜太小否则否则“太精确太精确”.适合的范围：比适合的范围：比1稍小一些稍小一些.7878不精确一维搜索不精确一维搜索例：函数例：函数f f(a a)=(a a-1)2.f f(a a)=2(a a-1),f f(0)=-2.取取s s=0.5,则控制条件为则控制条件为|f f(a ak)|s s|f f(0 0)|=1,即即|2(a ak-1)|1,1/2 a ak3/2.7979不精确一维搜索不精确一维搜索上述条件是不够的上述条件是不够的上述条件是不够的上述条件是不够的,甚至不能保证甚至不能保证甚至不能保证甚至不能保证f f f f(a a a ak k)3/2 3/2时时时时,f f f f(a a a a)=)=a a a a-5/4-5/4-5/4-5/4.易见易见易见易见f f f f(a a a a)是一个连续可导是一个连续可导是一个连续可导是一个连续可导函数函数函数函数,且且且且a a a a 3/2 3/2时导数为时导数为时导数为时导数为1.1.|f f f f(a a a ak k)|)|s s s s|f f f f(0 0 0 0)|=1)|=1确定的范围是确定的范围是确定的范围是确定的范围是1/2 1/2 a a a ak k,不能保证函数值下降不能保证函数值下降不能保证函数值下降不能保证函数值下降.8080不精确一维搜索不精确一维搜索为此为此,我们在直线我们在直线y=0以及函数以及函数f f(a a)在在a a=0处的处的切线之间画一条直线切线之间画一条直线,将搜索范围首先限制在将搜索范围首先限制在这条直线下方这条直线下方.8181不精确一维搜索不精确一维搜索上述直线的方程为上述直线的方程为y-f f(0 0)=m f m f(0 0)a a.因此搜索的条件为因此搜索的条件为f f(a ak)-f f(0 0)m f m f(0 0)a ak .作业：对作业：对f f(a a)=f(xk+a a pk),证明证明8282不精确一维搜索不精确一维搜索|f f(a ak)/f f(0 0)|s sf f(a ak)-f f(0 0)m f m f(0 0)a a8383不精确一维搜索的不精确一维搜索的Wolfe原则原则设设f(x)可微可微,取取m m(0,1/2),s s(m m,1),选取选取a a k 0,使使或用下面更强的条件代替或用下面更强的条件代替(1.7)式式:8484Wolfe原则原则关于满足关于满足Wolfe原则的步长原则的步长a ak的存在性的存在性:定理定理1.4.2 设设f(x)有下界且有下界且 gkTpk0.令令m m(0,1/2),s s(0,m m),则存在区间则存在区间c1,c2,使得任意的使得任意的a ac1,c2均满足式均满足式(1.6)和和(1.7)(也满足也满足(1.8).8585不精确一维搜索不精确一维搜索Wolfe算法算法问题问题:设已知设已知xk和下降方向和下降方向pk,求问题求问题的近似值的近似值a ak,使使a ak 满足满足(1.6)和和(1.7).算法算法1.4.6 不精确一维搜索不精确一维搜索Wolfe算法算法step 1 给定给定m m(0,1),s s(m m,1),令令a=0,b=,a a=1,j=0;step2 xk+1=xk+a a pk,计算计算fk+1,gk+1;8686 若若a a 满足满足(1.6)和和(1.7)式式,则令则令a ak=a a;若若a a 不满足不满足(1.6)式式,则令则令k:=k+1,转转step 3;若若a a 不满足不满足(1.7)式式,则令则令k:=k+1,转转step 4;step 3 令令 转转step 2 step 4 令令 转转step 2.8787step 1 给定给定m m=0.1,s s=0.5,令令a=0,b=,a 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的近似步长的近似步长a ak.解解8888因为因为fkfk+1=1100=99ma ma gkTpk=0.2所以所以(1.6)式成立。转式成立。转step 3step 2 xk+1=xk+a a pk=(1,0)T,fk+1=f(1,0)=100step 3 令令b=1,a a =(a+a a)/2=(1+0)/2=0.5,转转step 2.重新计算重新计算xk+1.迭代四次得到满足迭代四次得到满足Wolfe条件的步长条件的步长a ak=0.125xk+1=xk+a ak pk=(0.125,1)T.8989总结总结一一维维搜搜索索的的方方法法利用导数利用导数的方法的方法仅用仅用函数函数值的值的方法方法二分法二分法 (算法算法1.4.4)精确精确方法方法不精确不精确方法方法Fibonacci方法方法(算法算法1.4.1)黄金分割法黄金分割法 (算法算法1.4.2)求初始区间的方法求初始区间的方法进退法进退法 (算法算法1.4.3)二次插值法二次插值法 (算法算法1.4.5)Wolfe算法算法(算法算法1.4.6)