第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,点2 x=629, y=375,309.00 (1.30),864.3(2.0),飞机 x=?,y=?,点1 x=764, y=1393,161.20 (0.80),点3 x=1571, y=259,45.10 (0.60),北,点4 x=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,四、正定、负定、半定矩阵 设实对称阵An×n，各阶主子式为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.0279 xmax = 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.5000 ymax = 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.0000 f = 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_work126.com 2、文档和邮件命名相同：2+姓名+学号后四位 例如：2段冰琛0101 (.doc) 3、内容完整，应至少包含以下几部分： 各算法求解结果（表格）和结果分析 （参考课本78页例4） 附录：MATLAB程序,