最优化方法课件解可新1

安康学院数学与统计系 应用数学教研室前言前言一、什么是最优化一、什么是最优化 最优化是一门应用性相当广泛的学科，它讨论决策最优化是一门应用性相当广泛的学科，它讨论决策问题的最佳选择之特性，寻找最佳的计算方法，研究这问题的最佳选择之特性，寻找最佳的计算方法，研究这些计算方法的理论性质及其实际计算表现。些计算方法的理论性质及其实际计算表现。应用范围：信息工程及设计、经济规划、生产管理、交应用范围：信息工程及设计、经济规划、生产管理、交通运输、国防工业以及科学研究等诸多领域。通运输、国防工业以及科学研究等诸多领域。1 1前言1安康学院数学与统计系 应用数学教研室二、包含的内容二、包含的内容按照优化思想分为经典方法与现代方法。按照优化思想分为经典方法与现代方法。经典方法主要包括：线性规划、非线性规划、整数规经典方法主要包括：线性规划、非线性规划、整数规划、动态规划等划、动态规划等现代方法主要包括：随机规划、模糊规划、模拟退火现代方法主要包括：随机规划、模糊规划、模拟退火算法、遗传算法、禁忌搜索和人工神经网络等。算法、遗传算法、禁忌搜索和人工神经网络等。我们学习的内容主要是经典的最优化方法。我们学习的内容主要是经典的最优化方法。内容包括线性规划及其对偶规划，无约束最优化方法、内容包括线性规划及其对偶规划，无约束最优化方法、约束最优化方法等主要内容。约束最优化方法等主要内容。2 2二、包含的内容2安康学院数学与统计系 应用数学教研室目录目录第一章第一章 最优化问题概述最优化问题概述第二章第二章 线性规划线性规划第三章第三章 无约束最优化方法无约束最优化方法第四章第四章 约束最优化方法约束最优化方法3 3目录第一章 最优化问题概述3安康学院数学与统计系 应用数学教研室第一章最优化问题概述第一章最优化问题概述安康学院数学与统计系 应用数学教研室1.1 最优化问题的数学模型最优化问题的数学模型与基本概念与基本概念5 51.1 最优化问题的数学模型与基本概念5安康学院数学与统计系 应用数学教研室例例 1.1.1 运输问题运输问题设有设有m个水泥厂个水泥厂A1,A2,Am,年产量各为年产量各为a1,a2,am吨吨.有有k个城市个城市B1,B2,Bk用这些水泥用这些水泥厂生产的水泥厂生产的水泥,年需求量年需求量b1,b2,bk吨吨.再设由再设由Ai到到Bj每吨水泥的运价为每吨水泥的运价为cij元元.假设产销是平衡假设产销是平衡的的,即即:试设计一个调运方案试设计一个调运方案,在满足需要的同时使总在满足需要的同时使总运费最省运费最省.6 6例 1.1.1 运输问题设有m个水泥厂A1,A2,A安康学院数学与统计系 应用数学教研室A1 由题意可画出如下的运输费用图由题意可画出如下的运输费用图:B2AmB1A2Bk产量产量需求量需求量设设AiBj的水泥量为的水泥量为xij,已知已知AiBj单价为单价为cij,单单位为元位为元,则总运费为则总运费为:7 7A1 由题意可画出如下的运输费用图:B2AmB1A2Bk产量安康学院数学与统计系 应用数学教研室数学模型数学模型:注注:平衡条件平衡条件 作为已知条件并不作为已知条件并不出现在约束条件中出现在约束条件中.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例1.1.2 生产计划问题设某工厂有m种资源B1,B2,安康学院数学与统计系 应用数学教研室假设产品假设产品Aj的计划产量为的计划产量为xj.由题意可画出如下的生产与消耗的关系图由题意可画出如下的生产与消耗的关系图:B1B2BmAnA2A1消耗消耗1010假设产品Aj的计划产量为xj.B1B2BmAnA2A1消耗1安康学院数学与统计系 应用数学教研室数学模型数学模型1111数学模型11安康学院数学与统计系 应用数学教研室例例 1.1.3 指派问题指派问题设有四项任务设有四项任务B1,B2,B3,B4派四个人派四个人A1,A2,A3,A4去完成去完成.每个人都可以承担四项任务中的每个人都可以承担四项任务中的任何一项任何一项,但所消耗的资金不同但所消耗的资金不同.设设Ai完成完成Bj所所需资金为需资金为cij.如何分配任务如何分配任务,使总支出最少使总支出最少?设变量设变量指派指派Ai完成完成bj不指派不指派Ai完成完成bj1212例 1.1.3 指派问题设有四项任务B1,B2,B3,B4派安康学院数学与统计系 应用数学教研室则总支出可表示为则总支出可表示为:数学模型数学模型:1313则总支出可表示为:数学模型:13安康学院数学与统计系 应用数学教研室例例 1.1.4 数据拟合问题数据拟合问题 在实验数据处理或统计资料分析中常遇在实验数据处理或统计资料分析中常遇到如下问题到如下问题.设两个变量设两个变量x和和y,已知存在函数关已知存在函数关系系,但其解析表达式或者是未知的或者虽然为但其解析表达式或者是未知的或者虽然为已知的但过于复杂已知的但过于复杂.设已取得一组数据设已取得一组数据:(xi,yi)i=1,2,m.根据这一组数据导出函数根据这一组数据导出函数y=f(x)的一个简单而的一个简单而近似的解析表式近似的解析表式.1414例 1.1.4 数据拟合问题 在实验数据处安康学院数学与统计系 应用数学教研室最小二乘法最小二乘法解这种问题常用的方法是最小二乘法解这种问题常用的方法是最小二乘法,以一个以一个简单的函数序列简单的函数序列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维向量维向量.在实际应用中在实际应用中,可以将求最大值的目标函数取可以将求最大值的目标函数取相反数后统一成公式中求最小值的形式相反数后统一成公式中求最小值的形式.我们总是讨论我们总是讨论P:P:1717最优化问题最优化问题的一般形式为:(1.1)(目标函数)(1安康学院数学与统计系 应用数学教研室相关定义相关定义定义定义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.1(可行解)满足约束条件(1.2)安康学院数学与统计系 应用数学教研室定义定义1.1.3 (整体最优解整体最优解)若若x*D,对于一切对于一切xD恒有恒有f(x*)f(x),则称则称x*为最优化问题为最优化问题(P)的的整体最优解整体最优解.若若x*D,xx*,恒有恒有f(x*)f(x),则称则称x*为最优为最优化问题化问题(P)的严格整体最优解的严格整体最优解.相关定义相关定义1919定义1.1.3 (整体最优解)若x*D,对于一切x安康学院数学与统计系 应用数学教研室定义定义定义定义1.1.4 (1.1.4 (局部最优解局部最优解局部最优解局部最优解)若若若若x x*D D,存在存在存在存在x x*的某邻域的某邻域的某邻域的某邻域N Ne e e e(x x*),*),使得对于一切使得对于一切使得对于一切使得对于一切x xD D N Ne e e e(x x*),*),恒有恒有恒有恒有f f(x x*)*)f f(x x),),则则则则称为最优化问题称为最优化问题称为最优化问题称为最优化问题(P)(P)的局部最优解的局部最优解的局部最优解的局部最优解,其中其中其中其中N Ne e e e(x x*)=*)=x x|x x-x x*|*|0.0.当当当当x x x x*时时时时,若上面的不等式为严格不等式则称若上面的不等式为严格不等式则称若上面的不等式为严格不等式则称若上面的不等式为严格不等式则称x x*为问为问为问为问题题题题(P)(P)的严格局部最优解的严格局部最优解的严格局部最优解的严格局部最优解.显然显然显然显然,整体最优解一定是局部最优解整体最优解一定是局部最优解整体最优解一定是局部最优解整体最优解一定是局部最优解,而局部最优解不而局部最优解不而局部最优解不而局部最优解不一定是整体最优解一定是整体最优解一定是整体最优解一定是整体最优解.x x*对应的目标函数值对应的目标函数值对应的目标函数值对应的目标函数值f f(x x*)*)称为最优值，记为称为最优值，记为称为最优值，记为称为最优值，记为f f *.相关定义相关定义2020定义1.1.4 (局部最优解)若x*D,存在x*的某安康学院数学与统计系 应用数学教研室求解最优化问题求解最优化问题求解最优化问题求解最优化问题(P P),),就是求目标函数就是求目标函数就是求目标函数就是求目标函数f f(x x)在约束条件在约束条件在约束条件在约束条件(1.2),(1.3)(1.2),(1.3)下的极小点下的极小点下的极小点下的极小点,实际上是求可行域实际上是求可行域实际上是求可行域实际上是求可行域D D上的整体上的整体上的整体上的整体最优解最优解最优解最优解.但是但是但是但是,在一般情况下在一般情况下在一般情况下在一般情况下,整体最优解是很难求出整体最优解是很难求出整体最优解是很难求出整体最优解是很难求出的的的的,往往只能求出局部最优解往往只能求出局部最优解往往只能求出局部最优解往往只能求出局部最优解.在求解时需要范数的概念，以下给出定义。在求解时需要范数的概念，以下给出定义。在求解时需要范数的概念，以下给出定义。在求解时需要范数的概念，以下给出定义。相关定义相关定义2121求解最优化问题(P),就是求目标函数f(x)在约束条件(1.安康学院数学与统计系 应用数学教研室向量范数向量范数定义定义1.1.5 如果向量如果向量xRn 的某个实值函数的某个实值函数|x|,满足条件满足条件(1)|x|0(|x|=0当且仅当当且仅当x=0)(正定性正定性);(2)|x|=|x|(对于任意对于任意 R);(3)|x+y|x|+|y|(三角不等式三角不等式);则称则称|x|为为Rn 上的一个向量范数上的一个向量范数.2222向量范数定义1.1.5 如果向量xRn 的某个实值函数|安康学院数学与统计系 应用数学教研室常用的向量范数常用的向量范数1-范数范数2-范数范数(欧氏范数欧氏范数)-范数范数p-范数范数-范数是范数是p-范数的极限范数的极限2323常用的向量范数1-范数2-范数(欧氏范数)-范数p-范数安康学院数学与统计系 应用数学教研室常用的向量范数常用的向量范数对向量对向量x=(1,-2,3)T,有有|x|p是是p的单调递减函数的单调递减函数.2424常用的向量范数对向量x=(1,-2,3)T,有|x|p是安康学院数学与统计系 应用数学教研室最优化问题的分类最优化问题的分类根据数学模型中有无约束函数分为有约束的根据数学模型中有无约束函数分为有约束的最优化问题和无约束的最优化问题最优化问题和无约束的最优化问题.根据目标函数和约束函数的函数类型分类根据目标函数和约束函数的函数类型分类:线线性最优化问题性最优化问题,非线性最优化问题非线性最优化问题,二次规划二次规划,多多目标规划目标规划,动态规划动态规划,整数规划整数规划,0-1规划规划.2525最优化问题的分类根据数学模型中有无约束函数分为有约束的最优化安康学院数学与统计系 应用数学教研室1.2 最优化问题的一般算法最优化问题的一般算法26261.2 最优化问题的一般算法26安康学院数学与统计系 应用数学教研室迭代算法迭代算法迭代算法迭代算法 选取一个初始可行点选取一个初始可行点x0D,由这个由这个初始可行点出发初始可行点出发,依次产生一个可行点列依次产生一个可行点列:x1,x2,xk,记为记为xk,使得某个使得某个xk恰好是问题的一个最优解恰好是问题的一个最优解,或者该点列收敛到问题的一个最优解或者该点列收敛到问题的一个最优解x*.下降算法下降算法 在迭代算法中一般要求在迭代算法中一般要求 f(xk+1)f(xk).2727迭代算法迭代算法 选取一个初始可行点x0D,由这个初始可安康学院数学与统计系 应用数学教研室可行点列的产生可行点列的产生在在xk处求得一个方向处求得一个方向pk(下降方向下降方向),在射线在射线xk+pk(0)上求一点上求一点:xk+1=xk+kpk使得使得f(xk+1)f(xk).其中其中 k称为步长称为步长.定义定义1.2.1(下降方向下降方向)在点在点xk处处,对于方向对于方向pk0,若存在实数若存在实数b b 0,使得任意的使得任意的(0,b b),有有:f(xk+pk)f(xk),则称则称pk为函数为函数f(x)在点在点xk处的一个下降方向处的一个下降方向.2828可行点列的产生在xk处求得一个方向pk(下降方向),在射线x安康学院数学与统计系 应用数学教研室下降方向下降方向若若若若f f(x x)具有连续的一阶偏导数具有连续的一阶偏导数具有连续的一阶偏导数具有连续的一阶偏导数,令令令令由由由由TaylorTaylor公式公式公式公式:当当gkTpk0时时,f(xk+pk)f(xk),所以所以pk是是f(x)在在xk处的一个下降方向处的一个下降方向.反之反之,当当pk是是f(x)在在xk处的一个下降方向时处的一个下降方向时,有有gkTpk0.通常称满足通常称满足gkTpk0的方向的方向pk是为是为f(x)在在xk处的处的一个下降方向一个下降方向.称为称为f(x)在在x处的梯度。处的梯度。2929下降方向若f(x)具有连续的一阶偏导数,令当gkTpk0,使得对任意的使得对任意的(0,b b),有有:xk+pkD,则称则称pk为点为点xk处关于区域处关于区域D的可行方向的可行方向.对于对于D的内点的内点(存在邻域包含于存在邻域包含于D),任意方向可任意方向可行行,对于边界点对于边界点(任意邻域既有任意邻域既有D的点也有不在的点也有不在D中的点中的点),则有些方向可行则有些方向可行,有些方向不可行有些方向不可行.若下降方向关于域若下降方向关于域D可行可行,则称为可行下降方向则称为可行下降方向.3030可行方向定义1.2.2(可行方向)已知区域 安康学院数学与统计系 应用数学教研室最优化问题的算法的一般迭代格式最优化问题的算法的一般迭代格式给定初始点给定初始点x0,令令k=0.(1)确定确定xk处的可行下降方向处的可行下降方向pk;(2)确定步长确定步长 k,使得使得f(xk+kpk)f(xk),(3)令令x xk k+1+1=x xk k+k kp pk k;(4)若若x xk k+1+1满足某种终止准则满足某种终止准则,则停止迭代则停止迭代,以以x xk k+1+1为近似最优解为近似最优解;或者已经达到最大迭代步或者已经达到最大迭代步数数,也可终止迭代也可终止迭代.否则令否则令k:=k+1,转转(1)3131最优化问题的算法的一般迭代格式给定初始点x0,令k=0.31安康学院数学与统计系 应用数学教研室收敛性收敛性如果一个算法只有当初始点如果一个算法只有当初始点x0充分接近充分接近x*时时,产生的点列才收敛于产生的点列才收敛于x*,则称该算法为具有局则称该算法为具有局部收敛的算法部收敛的算法.如果对任意的如果对任意的x0D,由算法产生的点列都收敛由算法产生的点列都收敛x*,则称该算法为具有全局收敛的算法则称该算法为具有全局收敛的算法.由于一般情况下最优解由于一般情况下最优解x*是未知的是未知的,所以只有所以只有具有全局收敛性的算法才有实用意义具有全局收敛性的算法才有实用意义.但算法但算法的局部收敛性分析的局部收敛性分析,在理论上是重要的在理论上是重要的,因为它因为它是全局收敛性分析的基础。是全局收敛性分析的基础。3232收敛性如果一个算法只有当初始点x0充分接近x*时,产生的点列安康学院数学与统计系 应用数学教研室收敛速度收敛速度定义定义1.2.3 设序列设序列xk收敛于收敛于x*,而且而且若若0b b0是预先给定的是预先给定的.3434终止准则对于一种算法,应该有某种终止准则,当某次迭代满足终止安康学院数学与统计系 应用数学教研室1.3 二维最优化问题的几何解释二维最优化问题的几何解释35351.3 二维最优化问题的几何解释35安康学院数学与统计系 应用数学教研室理论分析理论分析二维最优化问题的目标函数二维最优化问题的目标函数z=f(x1,x2)表示三表示三维空间维空间R3中的曲面中的曲面.在空间直角坐标系在空间直角坐标系O-x1x2z中中,平面平面z=c与曲面与曲面z=f(x1,x2)的交线在的交线在0-x1x2平平面上的投影曲线为面上的投影曲线为:取不同的取不同的c值得到不同的投影曲线值得到不同的投影曲线,每一条投影每一条投影曲线对应一个曲线对应一个c值值,称投影曲线为目标函数的等称投影曲线为目标函数的等值线或等高线值线或等高线.3636理论分析二维最优化问题的目标函数z=f(x1,x2)表示三维安康学院数学与统计系 应用数学教研室373737安康学院数学与统计系 应用数学教研室理论分析理论分析求目标函数求目标函数z=f(x1,x2)在可行域在可行域D上的极小点上的极小点,是在与可行域是在与可行域D有交集的等值线中找出具有有交集的等值线中找出具有最小值的等值线最小值的等值线.也就是在可行域也就是在可行域D上沿着上沿着f(x1,x2)的负梯度方向或某种下降方向上找取的负梯度方向或某种下降方向上找取得最小值得最小值c的点的点.3838理论分析求目标函数z=f(x1,x2)在可行域D上的极小点安康学院数学与统计系 应用数学教研室例例1.3.1解解 首先画出可行域首先画出可行域D,目标函数的等值线是以目标函数的等值线是以点点(1,2)为圆心的一族圆为圆心的一族圆.f(x1,x2)的梯度为的梯度为3939例1.3.1解 首先画出可行域D,目标函数的等值线是以点(1安康学院数学与统计系 应用数学教研室例例1.3.1负梯度方向（负梯度方向（下下降方向降方向）指向等）指向等值线圆心值线圆心,所以等所以等值线与可行域值线与可行域D的的边界相切的点边界相切的点x*=(1/2,3/2)T 是此是此问题的最优解问题的最优解,目目标函数的最优值标函数的最优值为为1/2.4040例1.3.1负梯度方向（下降方向）指向等值线圆心,所以等值线安康学院数学与统计系 应用数学教研室例例1.3.2解解 首先画出可行域首先画出可行域D的图形的图形.D为凸多边形为凸多边形 ODEFGO.再以再以c为参数画出目标函数的等值为参数画出目标函数的等值线线2x1+3x2=c.4141例1.3.2解 首先画出可行域D的图形.D为凸多边形 安康学院数学与统计系 应用数学教研室例例1.3.2目标函数目标函数c的值由的值由小到大逐渐增加小到大逐渐增加,等等值线沿着目标函数值线沿着目标函数的梯度方向平行移的梯度方向平行移动动.当移动到点当移动到点E时时,再移动就与可行域再移动就与可行域D不相交了不相交了,所以顶所以顶点点E就是最优点就是最优点,最最优值为优值为14.4242例1.3.2目标函数c的值由小到大逐渐增加,等值线沿着目标函安康学院数学与统计系 应用数学教研室例例1.3.3解解 如图所示如图所示,可行域只能是可行域只能是圆弧圆弧ABE,其中点其中点A和点和点E是是等值线等值线x1x2+1=0和圆和圆x12+x22-9=0的交点的交点.注意到等注意到等值线是平行的抛物线值线是平行的抛物线,图中画图中画出了几条目标函数的等值线出了几条目标函数的等值线.容易看出容易看出B点是最优点点是最优点,所以所以最优解是最优解是(0,-3)T,最优值为最优值为-3.4343例1.3.3解 如图所示,可行域只能是圆弧ABE,其中点A安康学院数学与统计系 应用数学教研室1.4 一维搜索一维搜索44441.4 一维搜索44安康学院数学与统计系 应用数学教研室问题描述问题描述已知已知xk,并且求出了并且求出了xk处的可行下降方向处的可行下降方向pk,从从 xk出发出发,沿方向沿方向pk求目标函数的最优解求目标函数的最优解,即求解即求解问题问题:设其最优解为设其最优解为 k,于是得到一个新点于是得到一个新点xk+1=xk+k pk所以一维搜索是求解一元函数所以一维搜索是求解一元函数f f()的最优化问的最优化问题题(也叫一维最优化问题也叫一维最优化问题).我们来求解我们来求解令令()=0,求出求出 的值。的值。4545问题描述已知xk,并且求出了xk处的可行下降方向pk,从 安康学院数学与统计系 应用数学教研室在在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 4646在a,b内任取x1x2,1.安康学院数学与统计系 应用数学教研室黄金分割法黄金分割法若第一次选取的试点为若第一次选取的试点为x1x2,则下一步保留的则下一步保留的区间为区间为a,x2或或x1,b,两者的机会是均等的两者的机会是均等的.因此我们选取试点时希望因此我们选取试点时希望x2-a=b-x1.abx1x2设设x1=a+p(b-a),则则x2=a+(1-p)(b-a).4747黄金分割法若第一次选取的试点为x1x2,则下一步保留的区间安康学院数学与统计系 应用数学教研室黄金分割法黄金分割法另外另外,我们希望如果缩小的区间包含原来的试点我们希望如果缩小的区间包含原来的试点,则该试点在下一步被利用则该试点在下一步被利用.若保留的区间为若保留的区间为a,x2,前一次的试点前一次的试点x1在这个区在这个区间内间内.abx1x2abx24848黄金分割法另外,我们希望如果缩小的区间包含原来的试点,则该试安康学院数学与统计系 应用数学教研室黄金分割法黄金分割法abx1x2a b x2 我们希望原来我们希望原来的的x1,在缩小的在缩小的区间内成为新区间内成为新的的“x2”.我们根据这一我们根据这一条件来计算条件来计算p.计算计算x2的公式为的公式为x2=a+(1 p)(b a).因此我们希望因此我们希望a+p(b a)=a+(1p)(a+(1 p)(b a)a)x 2=a +(1 p)(b a).即即p2-3p+1=0化简得化简得4949黄金分割法abx1x2abx2我们希望原来的x1,在缩安康学院数学与统计系 应用数学教研室黄金分割法黄金分割法若保留区间为若保留区间为x1,b,我们得到的结果是一致的我们得到的结果是一致的.该方法称为黄金分割法该方法称为黄金分割法,实际计算取近似值实际计算取近似值:x1=a+0.382(b a),x2=a+0.618(b a),所以黄金分割法又称为所以黄金分割法又称为0.618法法.黄金分割法每次缩小区间的比例是一致的黄金分割法每次缩小区间的比例是一致的,每每次将区间长度缩小到原来的次将区间长度缩小到原来的0.618倍倍.5050黄金分割法若保留区间为x1,b,我们得到的结果是一致的.安康学院数学与统计系 应用数学教研室算法算法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.5151算法1.4.2 黄金分割法给定a,b(a0安康学院数学与统计系 应用数学教研室例例1.4.1 用黄金分割法求函数用黄金分割法求函数f(x)=x2-x+2在区间在区间-1,3上的极小值，要求区间长度不大于原始区间上的极小值，要求区间长度不大于原始区间长的长的0.08。5252例1.4.1 用黄金分割法求函数f(x)=x2-x+2在区间安康学院数学与统计系 应用数学教研室用用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.5545353用0.618法求解例1.4.1的数据表迭代次数a,bx1安康学院数学与统计系 应用数学教研室进退法进退法(寻找下单峰区间寻找下单峰区间)在一维搜索之前在一维搜索之前,必须先知道一个必须先知道一个f(x)的下单峰的下单峰区间区间.书中的算法书中的算法1.4.3给出了求函数的一般的下给出了求函数的一般的下单峰区间的算法单峰区间的算法.此处我们对算法此处我们对算法1.4.3加以改进加以改进,求出求出f(x)的一个形如的一个形如0,b形式的下单峰区间形式的下单峰区间因为我们关心的问题是因为我们关心的问题是:我们的目的是找出两个点我们的目的是找出两个点x10,x1=x0+D Dx.x0下面分两种情况讨论下面分两种情况讨论.(1)f(x1)f(x0)x1对应着图上用红线标出的一部分对应着图上用红线标出的一部分5555进退法(寻找下单峰区间)给定初始点x0=0,初始步长Dx0安康学院数学与统计系 应用数学教研室进退法进退法(寻找下单峰区间寻找下单峰区间)x0(1)f(x1)f(x0)此时此时x1取值小取值小,我们加大步长向右搜索我们加大步长向右搜索,取取D Dx=2D Dx,x2=x1+D Dx若若f(x1)f(x2),则我们要找的区间即为则我们要找的区间即为x0,x2x1x2D Dx2D2Dx5656进退法(寻找下单峰区间)x0(1)f(x1)f(x0)此时安康学院数学与统计系 应用数学教研室进退法进退法(寻找下单峰区间寻找下单峰区间)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 Dx2D2Dxx1x25757进退法(寻找下单峰区间)x0(1)f(x1)f(x0)若f安康学院数学与统计系 应用数学教研室进退法进退法(寻找下单峰区间寻找下单峰区间)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).x1x2x15858进退法(寻找下单峰区间)x0(2)f(x1)f(x0)此时安康学院数学与统计系 应用数学教研室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作为新区间作为新区间.59591.4.2 二分法若f(x)的导数存在且容易计算,则线性搜索安康学院数学与统计系 应用数学教研室1.4.3 抛物线法抛物线法在求一元函数的极小点问题上在求一元函数的极小点问题上,我们可以利用若我们可以利用若干点处的函数值来构造一个多项式干点处的函数值来构造一个多项式,用这个多项用这个多项式的极小点作为原来函数极小点的近似值式的极小点作为原来函数极小点的近似值.抛物线法就是一个用二次函数来逼近抛物线法就是一个用二次函数来逼近f(x)的方法的方法,这也是我们常说的二次插值法这也是我们常说的二次插值法.设在已知的三点设在已知的三点x1x0f0,f0f2过三点过三点(x1,f1),(x0,f0),(x2,f2)作二次函数作二次函数y=j j(x),即作即作一条抛物线一条抛物线,则可推导出：则可推导出：60601.4.3 抛物线法在求一元函数的极小点问题上,我们可以利用安康学院数学与统计系 应用数学教研室为求为求j j(x)的极小点的极小点,令令j j (x)=0,得得:6161为求j(x)的极小点,令j(x)=0,得:61安康学院数学与统计系 应用数学教研室若若 充分接近充分接近 ,即对于预先给定的精度即对于预先给定的精度 ,有有 ,则把则把 作为近似极小点作为近似极小点.否则计算否则计算 ,找出找出 和和 之间的大者之间的大者,去掉去掉 或或 ,使新的三点仍具有两端点的函数使新的三点仍具有两端点的函数值大于中间点的函数值的性质值大于中间点的函数值的性质.利用新的点再利用新的点再构造二次函数构造二次函数,继续进行迭代继续进行迭代.6262若 充分接近 ,即对于预先给定的精度 安康学院数学与统计系 应用数学教研室1.4.4 不精确的一维搜索不精确的一维搜索 前面介绍的得几种一维搜索方法前面介绍的得几种一维搜索方法,都是为都是为了获得一元函数了获得一元函数f(x)的最优解的最优解,所以习惯上称为所以习惯上称为精确一维搜索精确一维搜索.在解非线性规划问题中在解非线性规划问题中,一维搜索一般很难得一维搜索一般很难得到真正的精确值到真正的精确值.因此因此,不精确的一维搜索开始为人们所重视不精确的一维搜索开始为人们所重视.即在即在xk点确定了下降方向点确定了下降方向pk后后,只计算少量的只计算少量的几个函数就可得到一个满足几个函数就可得到一个满足f(xk+1)0,使使或用下面更强的条件代替或用下面更强的条件代替(1.7)式式:6767不精确一维搜索的Wolfe原则设f(x)可微,取m(0,1安康学院数学与统计系 应用数学教研室Wolfe原则原则关于满足关于满足Wolfe原则的步长原则的步长 k的存在性的存在性:定理定理1.4.2 设设f(x)有下界且有下界且 gkTpk0.令令m m(0,1/2),s s(m m,1),则存在区间则存在区间c1,c2,使得任意的使得任意的 c1,c2均满足式均满足式(1.6)和和(1.7)(也满足也满足(1.8).6868Wolfe原则关于满足Wolfe原则的步长ak的存在性:68安康学院数学与统计系 应用数学教研室不精确一维搜索不精确一维搜索Wolfe算法算法问题问题:设已知设已知xk和下降方向和下降方向pk,求问题求问题的近似值的近似值 k,使使 k 满足满足(1.6)和和(1.7).算法算法1.4.6 不精确一维搜索不精确一维搜索Wolfe算法算法step 1 给定给定m m(0,1),s s(m m,1),令令a=0,b=,=1,k=0;step2 xk+1=xk+pk,计算计算fk+1,gk+1;6969不精确一维搜索Wolfe算法问题:设已知xk和下降方向pk,安康学院数学与统计系 应用数学教研室 若若 满足满足(1.6)和和(1.7)式式,则令则令 k=;若若 不满足不满足(1.6)式式,则令则令k:=k+1,转转step 3;若若 不满足不满足(1.7)式式,则令则令k:=k+1,转转step 4;step 3 令令 转转step 2 step 4 令令 转转step 2.7070 若a 满足(1.6)和(1.7)式,则令a安康学院数学与统计系 应用数学教研室step 1 给定给定m m=0.1,s s=0.5,令令a=0,b=,=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的近似步长的近似步长 k.解解7171step 1 给定m=0.1,s=0.5,Wolf安康学院数学与统计系 应用数学教研室因为因为fkfk+1=1100=99m m gkTpk=0.2所以所以(1.6)式成立。转式成立。转step 3step 2 xk+1=xk+pk=(1,0)T,fk+1=f(1,0)=100step 3 令令b=1,=(a+)/2=(1+0)/2=0.5,转转step 2.重新计算重新计算xk+1.迭代四次得到满足迭代四次得到满足Wolfe条件的步长条件的步长 k=0.125xk+1=xk+k pk=(0.125,1)T.7272因为fkfk+1=1100=99ma gkTpk