第5章 无约束优化.ppt

1,第5章 无约束优化,目的,内容,2、掌握用MATLAB求解无约束优化问题,1、了解无约束优化基本算法,2、无约束优化的基本方法,3、用MATLAB求解无约束优化问题,1、实际问题中的无约束优化模型,2,优化问题的数学模型,可行解（只满足(2)）与 最优解（满足(1),(2)）,无约束优化（只有(1)）与 约束优化（(1),(2)）,实际问题一般总有约束，何时可用无约束优化处理？,3,实例1 产销量的最佳安排,某厂生产甲、乙两个牌号的同一种产品，在产销平衡的情况下，如何确定各自产量使利润最大？注：产销平衡指工厂的产量等于市场上的销量。,目标：利润,销量、（单件）价格产量、（单件）成本,4,乙的价格也有同样的规律,5,无约束(非线性)规划,x1,x2 0?,6,0,y,x,点2x=629,y=375,309.00(1.30),864.3(2.0),飞机x=?,y=?,点1x=764,y=1393,161.20(0.80),点3x=1571,y=259,45.10(0.60),北,点4x=155,y=987,飞机与监控台（图中坐标和测量距离的单位是“千米”）,实例2 飞机精确定位问题,7,8,不考虑误差因素,超定方程组，非线性最小二乘！,量纲不符！？,9,考虑误差因素,Min x;Min y;Max x;Max y.,非线性规划！,不等式组？,误差非均匀分布！？,10,以距离为约束，优化角度误差之和（或平方和）或以角度为约束，优化距离误差,有人也可能会采用其他目标，如：,仅部分考虑误差!角度与距离的“地位”不应不同！,11,误差一般服从什么分布？,正态分布！,不同的量纲如何处理？,无约束非线性最小二乘模型,归一化处理！,随着思考的深入，模型趋于合理,12,优化问题的数学模型,可行解（只满足(2)）与 最优解（满足(1),(2)）,无约束优化（只有(1)）与 约束优化（(1),(2)）,实际问题一般总有约束，何时可用无约束优化处理？,13,5.1 无约束优化的基本方法,给定一个函数 f(x),寻找 x*使得 f(x*)最小，即,其中,无约束非线性规划,多元函数无条件极值问题 极值问题的解（极值点），都是局部最优解 全局最优解从局部最优解的比较中得到 以后所谓最优解均指局部最优解,14,5.1.1 预备知识一、梯度（一阶导数）,其中,梯度方向是使函数f(x)在x处增长最快的方向，即函数变化率最大的方向；梯度的模是函数f(x)沿梯度方向的变化率；满足梯度 的点称为驻点。,15,二、黑赛（Hessian）矩阵（二阶导数）,当f在点x处的所有二阶偏导数连续时，有,此时，是n阶对称矩阵；,当f(x)是二次函数：,16,三、多元函数的泰勒展开式1、一阶展开式,2、二阶展开式,近似计算,17,四、正定、负定、半定矩阵设实对称阵Ann，各阶主子式为Ai，i=1,2,n正定矩阵：Ai 0,i=1,2,n半正定矩阵：Ai 0,i=1,2,n负定矩阵：Ai 0,i为偶数半负定矩阵：Ai 0,i为奇数 Ai 0,i为偶数,18,5.1.2 最优解条件1、必要条件设f在点x处可微。若x是最优解，则2、充分条件设f在点x处Hessian矩阵存在。若则x是最优解。注：对于有实际意义的极值问题，我们通常只用必要条件，理论上只需求解方程组 即可。,19,5.1.3 数值迭代法的基本思路,基本思想,x*,x,f(x)f(x*),20,迭代步骤,Step 1 初始化：初始点x0，终止条件等,Step 2 迭代改进：搜索方向pk，步长 tk,Step 3 若 xk+1 满足终止条件，则停止迭代；否则，令 k:=k+1 转 Step2,不同的算法在于pk,tk选择不同 算法的关键在于寻找搜索方向pk,基本迭代格式,21,终止迭代条件,（1）根据相继两次迭代的绝对误差|xk+1-xk|e1|f(xk+1)-f(xk)|e2（2）根据相继两次迭代的相对误差|xk+1-xk|/|xk|e3|f(xk+1)-f(xk)|/|f(xk)|e4（3）根据目标函数梯度的模足够小,其中e1,e2,e3,e4,e5为给定足够小的正数,22,线性（一维）搜索(Line Search)确定步长方法,问题,已知当前点 xk 和搜索方向 pk,确定步长tk,使得,优化算法,近似黄金分割(0.618)法、Fibonacci法、Newton法、2次或3次插值法等,一维优化问题,5.1.4 搜索步长的确定,23,一、0.618法（近似黄金分割法）,单谷函数与单谷区间,若存在一个t*a,b，使得f(t)在 a,t*上严格递减,且在 t*,b 上严格递增f(t)a,b上的单谷函数a,b f(t)的单谷区间,a t*b,24,性质,在a,b内任取两点t1,t2(t1t2)，并计算 f(t1),f(t2)，可出现以下两种情况：（1）若f(t1)f(t2)，则t*a,t2;（2）若f(t1)f(t2)，则t*t1,b。,a t*b,t1,t2,a t*b,t1,t2,25,在a,b内取两个不同点，并算出它们的函数值加以比较，就可以把区间缩小成a,t2或t1,b;继续计算函数在一些点（探索点）上的值，可将区间长度缩小到任意小；当缩小到一定程度后，可将区间中任一点的作为最优解t*的近似值输出。,关键,如何有效的选择探索点？,0.618法（近似黄金分割法）每次迭代中搜索区间按定比例0.618缩小,26,二、Fibonacci法 每次迭代中搜索区间按不同比例 1/Fn 缩小Fn Fibonacci数列F0=1，F1=1，Fn=Fn-1+Fn-2（n2）,理论上Fibonacci法比0.618法好，但0.618法实现比较简单，所以实践中更有用；0.618法和Fibonacci法收敛速度较慢。当函数具有较好解析性质(连续性,可微性)时，插值法效果较好。,27,三、插值法,基本思想,利用几个探索点的函数值或者一阶导数值，产生一个二次或三次多项式来逼近函数，然后用这个多项式的极小点作为新的探索点，用来逼近函数的极小点。,解析性质较好的函数，适用插值法 解析性质较差的函数，适用0.618法,28,四、Newton法 f(t)二次可微，且f(t)0,基本思想,用f(t)在探索点tk处的二阶泰勒展开式g(t)来近似代替f(t)，然后用g(t)的最小点作为新的探索点，逐步迭代,29,5.1.5 搜索方向的选择一、最速下降法（1847，Cauchy）,迭代算法的关键,基本思想,从当前点xk出发，取函数f(x)在点xk处下降最快的方向作为搜索方向,下降最快方向？,下 降 方 向,最速下降方向,(负梯度方向),30,基本迭代格式,算法特点,初始阶段改进较快，最优解附近改进较慢,最速下降法常与其他方法结合使用，在开始几步使用最速下降法，在接近最优解时，使用其他收敛速度较快的方法。,二、共轭梯度法 以迭代点处的负梯度方向为基础产生一组共轭方向，作为每次迭代的搜索方向,31,三、Newton法（设步长为1）,将f(xk+1)在xk点作泰勒展开至二阶项，用p替代pk,牛 顿 方 程,牛 顿 方 向,求p使f(xk+1)最小右端对p梯度为0,下 降 方 向,32,特点,在最优解附近收敛较快;需计算Hessian阵当Hessian阵病态时，不利于牛顿方程的求解当Hessian阵不正定时，pk 可能不是下降方向,基本迭代格式,目的,不计算Hessian阵，克服病态、不正定、计算复杂等缺陷，同时保持收敛较快的优点,四、拟牛顿法,33,牛 顿 方 向,按照 拟牛顿条件：,34,Davidon-Fletcher-Powell(DFP)公式,Broyden-Fletcher-Goldfarb-Shanno(BFGS)公式,35,5.1 无约束优化的基本方法,基本思想,基本迭代格式,搜索步长,近似黄金分割(0.618)法、Fibonacci法、Newton法、2次或3次插值法等,搜索方向,最速下降法(梯度法)、共轭梯度法、牛顿法、拟牛顿法(DFP公式、BFGS公式),36,5.2 用MATLAB优化工具箱解无约束优化问题一、一元函数无约束优化问题,fminbnd,x=fminbnd(fun,x1,x2),输入项,fun 由字符串定义的函数或M文件函数名中间输入项缺省用 占位,函数fminbnd的算法基于0.618法和二次插值法，它要求目标函数必须是连续函数，并可能只给出局部最优解。,37,x,fval=fminbnd(.)x,fval,exitflag,output=fminbnd(.),输出项,x 最优解；fval 最优值；exitflag 描述退出条件 0收敛,0达到最大迭代次数,0不收敛output 包含优化结果信息的输出结构 iterations 实际迭代次数 funcCount 实际函数调用次数 algorithm 实际采用的算法,38,例5-1 求f=2e-xsinx在0,8上的最小值与最大值,39,xmin=3.9270 fmin=-0.0279xmax=0.7854 fmax=0.6448,40,例5-2 对边长为3m的正方形铁板，在四个角剪去相等的正方形以制成方形无盖水槽，问如何剪法使水槽的容积最大？解：设剪去的正方形的边长为x，则水槽的容积为(3-2x)2x。建立无约束优化模型为：min y=-(3-2x)2x,x0,1.5,fexm0502.m,41,xmax=0.5000ymax=2.0000剪掉正方形边长为0.5m时，水槽容积最大为2m3,42,二、多元函数无约束优化问题,fminunc,fminsearch,输入项,x=fminunc(fun,x0)x=fminsearch(fun,x0)x=fminunc(fun,x0,options)x=fminsearch(fun,x0,options),fun 同fminbnd用法x0 初始点;x 最优解中间输入项缺省用 占位,43,控制参数options的设置,(2)MaxIter:允许进行迭代的最大次数,取值为正整数；,options中常用的几个参数的名称、含义、取值如下:,(1)Display:显示水平。取值为off时,不显示输出;取值为iter时,显示每次迭代的信息;取值为final时,显示最终结果。默认值为final；,(3)TolFun:函数值的控制精度。,44,控制参数options可以通过函数 optimset 创建或修改。命令的格式如下：,(1)options=optimset(optimfun)创建一个含有所有参数名,并与优化函数optimfun有相同默认值的选项结构options。,（2）options=optimset(param1,value1,param2,value2,.)创建一个名称为options的优化选项参数,其中指定的参数具有指定值,所有未指定的参数取默认值。,45,例：opts=optimset(Display,iter,TolFun,1e-8)该语句创建一个名称为opts的优化选项结构,其中显示参数设为iter,TolFun参数设为1e-8。,(3)options=optimset(oldops,param1,value1,param2,value2,.)创建名称为oldops的参数选项的拷贝,用指定的参数值修改oldops中相应的参数。,46,使用fminunc和fminsearch可能会得到局部最优解 fminsearch是用单纯形法寻优；fminunc的算法见以下几点说明：,（1）fminunc 提供了大型和中型优化算法，由options中的参数 LargeScale 控制：LargeScale=on（默认值）,使用大型算法 LargeScale=off,使用中型算法,算法选择：optimset 中参数控制,47,（2）fminunc 为中型优化算法的搜索方向提供了以下算法，由options中的参数HessUpdate控制：HessUpdate=bfgs(默认值),拟牛顿法的BFGS公式 HessUpdate=dfp,拟牛顿法的DFP公式 HessUpdate=steepdesc,最速下降法,（3）fminunc为中型优化算法的步长一维搜索提供了两种算法，由options中参数LineSearchType控制：LineSearchType=quadcubic(默认值)混合的2、3多项式插值；LineSearchType=cubicpoly，3次多项式插值,48,输出项,x,fval=fminunc()x,fval=fminsearch()x,fval,exitflag,output=fminunc()x,fval,exitflag,output=fminsearch(),Output iterations 实际迭代次数 funcCount 实际函数调用次数 algorithm 实际采用的算法 cgiterations 实际PCG迭代次数（大型优化算法）stepsize 最后迭代步长（中型优化模算法）firstorderopt 一阶最优条件（梯度的模）message 收敛信息等,49,例5-3 min f(x)=(4x12+2x22+4x1x2+2x2+1)*exp(x1),fexm0503.m,50,x=0.5000-1.0000f=1.3028e-010,例5-4 Rosenbrock函数（香蕉函数）f(x1,x2)=100(x2-x12)2+(1-x1)2的精确极小点为x*=(1,1)，极小值为f*=0。试用不同算法（搜索方向和搜索步长）求数值最优解。初值选为x0=(-1.2,2)。,51,52,最速下降法的结果最差,53,算法选择 BFGS公式，混合2，3次插值，一般较好。,值得注意的问题,改变初始值 由一个初值出发通常得到局部最优解，如果函数存在多个局部最优解，只有改变初值，对局部最优进行比较，才有可能得到全局最优解。,54,第二次上机作业,求解 min f(x)=(4x12+2x22+4x1x2+2x2+1)*exp(x1)，初值(-1,1)，对不同算法（搜索方向和搜索步长）的结果进行分析、比较。,55,作业要求：1、15周之前，以word文档形式提交至邮箱：jianmo_2、文档和邮件命名相同：2+姓名+学号后四位 例如：2段冰琛0101(.doc)3、内容完整，应至少包含以下几部分：各算法求解结果（表格）和结果分析（参考课本78页例4）附录：MATLAB程序,