第5讲无约束优化

1、1无约束最优化无约束最优化数学建模与数学实验数学建模与数学实验2实验目的实验目的实验内容实验内容2、掌握用数学软件包求解无约束最优化问题。、掌握用数学软件包求解无约束最优化问题。1、了解无约束最优化基本算法。、了解无约束最优化基本算法。1 1、无约束优化基本思想及基本算法。、无约束优化基本思想及基本算法。4 4、实验作业。、实验作业。3、用、用MATLAB求解无约束优化问题。求解无约束优化问题。2、MATLAB优化工具箱简介优化工具箱简介3 无约束最优化问题无约束最优化问题返回4 XfnEXmin 其中 1:EEfn标准形式：标准形式：求解无约束最优化问题的基本思想求解无约束最优化问题的基本思

2、想求解的基本思想求解的基本思想 ( 以二元函数为例 )1x2x)(21xxf01x2x05310X1X2X)(0Xf)(1Xf)(2Xf连续可微 XfnEXmax = minXfnEX 56多局部极小298.0f0f298.0f 唯一极小(全局极小)2122212121322)(xxxxxxxxf7搜索过程搜索过程21221221)1 ()(100)(minxxxxxf最优点 (1 1)初始点 (-1 1)1x2xf-114.00-0.790.583.39-0.530.232.60-0.180.001.500.09-0.030.980.370.110.470.590.330.200.800.6

3、30.050.950.90 0.0030.990.991E-40.9990.9981E-50.9997 0.9998 1E-8返回8 给定初始点nEX 0，允许误差0,令 k=0； 计算kXf； 检验是否满足收敛性的判别准则： kXf， 若满足，则停止迭代，得点kXX*，否则进行； 令kkXfS，从kX出发，沿kS进行一维搜索， 即求k使得： kkkkkSXfSXf0min； 令kkkkSXX1，k=k+1 返回.无约束优化问题的基本算法无约束优化问题的基本算法 最速下降法是一种最基本的算法，它在最优化方法中占有重要地位.最速下降法的优点是工作量小，存储变量较少,初始点要求不高；缺点是收敛慢，

4、最速下降法适用于寻优过程的前期迭代或作为间插步骤，当接近极值点时，宜选用别种收敛快的算法. 1 1最速下降法（共轭梯度法）算法步骤：最速下降法（共轭梯度法）算法步骤：92 2牛顿法算法步骤：牛顿法算法步骤：(1) 选定初始点nEX 0，给定允许误差0，令 k=0；(2) 求kXf,12kXf,检验：若kXf,则 停止迭代,kXX*.否则, 转向(3)；(3) 令 kkkXfXfS12（牛顿方向） ； (4) kkkSXX1,1 kk,转回(2). 如果f是对称正定矩阵A的二次函数，则用牛顿法经过一次迭代一次迭代就可达到最优点,如不是二次函数，则牛顿法不能一步达到极值点，但由于这种函数在极值点附

5、近和二次函数很近似,因此牛顿法的收敛速度还是很快的. 牛顿法的收敛速度虽然较快，但要求Hessian矩阵要可逆，要计算二阶导数和逆矩阵，就加大了计算机计算量和存储量.103 3拟牛顿法拟牛顿法 为克服牛顿法的缺点，同时保持较快收敛速度的优点，利用第 k 步和第 k+1 步得到的kX，1kX，)(kXf，)(1kXf，构造一个正定矩阵1kG近似代替)(2kXf,或用1kH近似代替12)(kXf，将牛顿方向改为： 1kG1kS=-)(1kXf，1kS=-1kH)(1kXf从而得到下降方向.11 通常采用迭代法计算1kG，1kH，迭迭代代公公式式为:B BF FG GS S（Boryden-Flet

6、cher-Goldfarb-Shanno）公式 kkTkkTkkkkTkTkkkkxGxGxxGxfffGG)()()()(1 kTkTkkkTkkkTkkkxfxxxffHfHH)()()()(11 kTkTkkkkTkkxfxfHHfx)()()(12 D DF FP P（Davidon-Fletcher-Powell）公式： kTkTkkkTkkkTkkkXffffXXGXGG)()()()(11 kTkTkkkkTkkfXfXGGXf)()()( kkTkkTkkkkTkTkkkkfHfHffHXfXXHH)()()()(1 计算时可置IH 1（单位阵） ，对于给出的1X利 用上面的公

7、式进行递推.这种方法称为拟牛顿法拟牛顿法. . 返回13MatlabMatlab优化工具箱简介优化工具箱简介1.MATLAB1.MATLAB求解优化问题的主要函数求解优化问题的主要函数类 型模 型基本函数名一元函数极小Min F（x）s.t.x1xx2x=fminbnd(F,x1,x2)无约束极小Min F(X)X=fminunc(F,X0)X=fminsearch(F,X0)线性规划Min XcTs.t.AX=bX=linprog(c,A,b)二次规划Min 21xTHx+cTxs.t. Ax=bX=quadprog(H,c,A,b)约束极小（非线性规划）Min F(X)s.t. G(X)=

8、0X=fmincon(FG,X0)达到目标问题Min rs.t. F(x)-wr=goalX=fgoalattain(F,x,goal,w)极小极大问题Min max Fi(x)X Fi(x)s.t. G(x)0,则x为解;否则,x不是最终解,它只是迭代制止时优化过程的值所有优化函数fval解x处的目标函数值linprog,quadprog,fgoalattain,fmincon,fminimax,lsqcurvefit,lsqnonlin, fminbndexitflag描述退出条件: exitflag0,表目标函数收敛于解x处 exitflag=0,表已达到函数评价或迭代的最大次数 exi

9、tflag0,表目标函数不收敛output包含优化结果信息的输出结构. Iterations:迭代次数 Algorithm:所采用的算法 FuncCount:函数评价次数所有优化函数164 4控制参数控制参数optionsoptions的设置的设置 (3) MaxIterMaxIter: 允许进行迭代的最大次数,取值为正整数.OptionsOptions中常用的几个参数的名称、含义、取值如下中常用的几个参数的名称、含义、取值如下: : (1)DisplayDisplay: 显示水平.取值为off时,不显示输出; 取值为iter时,显示每次迭代的信息;取值为final时,显示最终结果.默认值为f

10、inal.(2)MaxFunEvalsMaxFunEvals: 允许进行函数评价的最大次数,取值为正整数.17例：opts=optimset(Display,iter,TolFun,1e-8) 该语句创建一个称为opts的优化选项结构,其中显示参数设为iter, TolFun参数设为1e-8. 控制参数控制参数optionsoptions可以通过函数可以通过函数optimsetoptimset创建或修改。命创建或修改。命令的格式如下：令的格式如下：(1) options=optimset(optimfun)options=optimset(optimfun) 创建一个含有所有参数名,并与优化函

11、数optimfun相关的默认值的选项结构options.（2）options=optimset(param1,value1,param2,value2,.)options=optimset(param1,value1,param2,value2,.) 创建一个名称为options的优化选项参数,其中指定的参数具有指定值,所有未指定的参数取默认值.(3)options=optimset(oldops,param1,value1,param2,options=optimset(oldops,param1,value1,param2, value2,.) value2,.) 创建名称为oldops的

12、参数的拷贝,用指定的参数值修改oldops中相应的参数.返回18用用MatlabMatlab解无约束优化问题解无约束优化问题 1. 一一元元函函数数无无约约束束优优化化问问题题: : min f（x） 21xxx 其中（3）、（4）、（5）的等式右边可选用（1）或（2）的等式右边。 函数fminbnd的算法基于黄金分割法和二次插值法，它要求目标函数必须是连续函数，并可能只给出局部最优解。常用格式如下：常用格式如下：（1）x= fminbnd (x= fminbnd (fun,xfun,x1 1,x,x2 2) )（2）x= fminbnd (x= fminbnd (fun,xfun,x1 1,

13、x,x2 2 ，options)options)（3）xx，fval= fminbndfval= fminbnd（.）（4）xx，fvalfval，exitflag= fminbndexitflag= fminbnd（.）（5）xx，fvalfval，exitflagexitflag，output= fminbndoutput= fminbnd（.）19运行结果： xmin = 3.9270 ymin = -0.0279 xmax = 0.7854 ymax = 0.6448To Matlab(wliti1) 例例 1 1 求 f = 2xexsin在 0 x8 中的最小值与最大值 主程序为主

14、程序为wliti1.m:wliti1.m: f=2*exp(-x).*sin(x); fplot(f,0,8); %作图语句 xmin,ymin=fminbnd (f, 0,8) f1=-2*exp(-x).*sin(x); xmax,ymax=fminbnd (f1, 0,8)20例例2 2 对边长为3米的正方形铁板，在四个角剪去相等的正方形以制成方形无盖水槽，问如何剪法使水槽的容积最大？设剪去的正方形的边长为x，则水槽的容积为：xx )23(2建立无约束优化模型为：min y=-xx )23(2， 0 x 0，且a11 a12；同理， p2 = b2 - a21 x1- a22 x2 ，b

15、2，a21，a22 0，且a22 a21 .2 2成本与产量成负指数关系成本与产量成负指数关系甲的成本随其产量的增长而降低,且有一个渐进值,可以假设为负指数关系,即: 0,11111111crcerqx 同理， 0,22222222crcerqx30 模型建立模型建立 若根据大量的统计数据,求出系数b1=100,a11=1,a12=0.1,b2=280,a21=0.2,a22=2,r1=30,1=0.015,c1=20, r2=100,2=0.02,c2=30,则问题转化为无约束优化问题：求甲,乙两个牌号的产量x1，x2，使总利润z最大. 为简化模型,先忽略成本,并令a12=0,a21=0,问

16、题转化为求: z1 = ( b1 - a11x1 ) x1 + ( b2 - a22x2 ) x2 的极值. 显然其解为x1 = b1/2a11 = 50, x2 = b2/2a22 = 70,我们把它作为原问题的初始值.总利润为：总利润为： z z( (x x1 1,x,x2 2)=()=(p p1 1-q-q1 1) )x x1 1+(+(p p2 2-q-q2 2) )x x2 231 模型求解模型求解 1.建立M-文件fun.m: function f = fun(x) y1=(100-x(1)- 0.1*x(2)-(30*exp(-0.015*x(1)+20)*x(1); y2=(2

17、80-0.2*x(1)- 2*x(2)-(100*exp(-0.02*x(2)+30)*x(2); f=-y1-y2; 2.输入命令: x0=50,70; x=fminunc(fun,x0), z=fun(x) 3.计算结果: x=23.9025, 62.4977, z=6.4135e+003 即甲的产量为23.9025,乙的产量为62.4977,最大利润为6413.5.To Matlab(wliti5)返回32实验作业实验作业1. 求下列函数的极小点： 1) 2123222118294xxxxxXf；2) 212122212223xxxxxxXf；3) 224121 xXf. 第1） ，2）

18、题的初始点可任意选取， 第3）题的初始点取为TX1 , 00.332 2. . 梯梯子子长长度度问问题题一楼房的后面是一个很大的花园. 在花园中紧靠着楼房有一个温室,温室伸入花园 2m,高 3m,温室正上方是楼房的窗台. 清洁工打扫窗台周围,他得用梯子越过温室,一头放在花园中,一头 靠在楼房的墙上. 因为温室是不能承受 a 梯子压力的,所以梯子太短是不行的. 现清洁工只有一架 7m 长的梯子, b 你认为它能达到要求吗? 能 满足要求的梯子的最小 长度为多少? 343 3. . 陈陈酒酒出出售售的的最最佳佳时时机机问问题题某酒厂有批新酿的好酒,如果现在就出售,可得总收入 R0=50 万元(人民币),如果窖藏起来待来日(第 n 年)按陈酒价格出售,第 n 年末可得总收入60neRR (万元),而银行利率为 r=0.05,试分析这批好酒窖藏多少年后出售可使总收入的现值最大. (假设现有资金 X 万元,将其存入银行,到第 n 年时增值为 R(n)万元,则称 X 为 R(n)的现值.)并填下表：35第一种方案：将酒现在出售，所获 50 万元本金存入银行；第二种方案：将酒窖藏起来，待第 n 年出售。（1） 计算 15 年内采用两种方案，50 万元增值的数目并 填入表 1，2 中；（2） 计算 15 年内陈酒出