无约束规划课件

4.无约束规划无约束规划建模——引例无约束规划模型无约束规划的示意图无约束规划的性质无约束规划重要算法用MATLAB解无约束规划引例1：某城市要选定一个供应中心(供电、供水、公天然气、网络接入等)的位置，该中心向城市中由固定位置的m个用户提供服务。问如何确定这个中心的位置才是最合理的？解设用户位置为(ai,bi)(i=1,2,...,m)已知，而供应中心的位置是(x1,x2)；假设运输线路不受道路影响，只考虑直线距离，则可建立求总距离最短的数学模型为：其中：c——运价(元/吨公里)；wi——第i个用户的需求量.若进一步考虑各单位的用量wi不同，而运价c按距离计算，则可建立求总总费用最小的数学模型为：“定位问题”——厂址选择等引例2：在某些实际问题中，往往要求决策变量x1,x2,...,xn满足(或近似满足)某些平衡条件，它表现为要求x1,x2,...,xn满足方程组即要求均方误差最小——最小二乘问题，包括线性最小二乘和非线性最小二乘问题，在数学建模中有非常重要的应用。可转化为求解问题：“最小二乘问题”——解方程组无约束规划的示意图多局部极小

唯一极小(全局极小)无约束规划的性质梯度列向量梯度的特点：1)函数f(X)在X处增长最快的方向，负梯度方向是函数f(X)在X处下降最快的方向；2)梯度的模是函数最快的变化率;3)梯度为零是驻点，极值点是驻点，驻点不一定是极值点。海森(Hessian)矩阵方、对称矩阵无约束规划的性质梯度为0向量的点可能是局部最优点，需要用海森矩阵类型进一步判定；凸函数的驻点必是全局最优点；补充1)f(X)是凸函数对任意定义域D中的元素X、Y和任意的数0≤a≤1，有： f(aX＋(1－a)Y)≤af(X)+(1－a)f(Y)

补充2)

对称矩阵的分类类别A正定A半正定A负定半负定不定定义特征值>0特征值≥

0(有0)特征值<0特征值≤0(有0)其它判别方法主子式都>0|A|=0;主子式≥0－A正定－A半正定无约束规划的基本算法一维搜索基本原则：1)最优原则：

2)可接受点原则：一维搜索方法：0.618法、插值法等下降方向：与梯度点乘为负值的方向无约束规划的基本算法3.拟牛顿法拟牛顿法特点：较梯度法收敛速度快速，较牛顿法稳定且计算量小。4.信赖域算法——对大型问题稳定性好，有成功的应用Matlab求解无约束规划问题类型模型基本函数名一元函数极小MinF(x)s.t.x1<x<x2x=fminbnd(‘F’,x1,x2)多元无约束极小MinF(X)X=fminunc(‘F’,X0)X=fminsearch(‘F’,X0)

[X,FVAL,EXITFLAG,OUTPUT]

=

fminbnd(FUN,x1,x2,OPTIONS,P1,P2,...)

[X,FVAL,EXITFLAG,OUTPUT,GRAD,HESSIAN]=

fminunc(FUN,X0,OPTIONS,P1,P2,...)[X,FVAL,EXITFLAG,OUTPUT]=

fminsearch(FUN,X0,OPTIONS,P1,P2,...)完整的调用格式：输出变量含义变量描述x由优化函数求得的值.若exitflag>0,则x为解;否则,x不是最终解,它只是迭代终止时优化过程的值fval解x处的目标函数值exitflag描述退出条件:exitflag>0,表目标函数收敛于解x处exitflag=0,表已达到函数计算或迭代的最大次数exitflag<0,表目标函数不收敛output包含优化结果信息的输出结构.Iterations:迭代次数Algorithm:所采用的算法FuncCount:计算函数值次数AlgorithmsLarge-ScaleOptimization——Bydefaultfminuncchoosesthelarge-scalealgorithmiftheusersuppliesthegradientinfun(andGradObjis'on'inoptions).Thisalgorithmisasubspacetrustregionmethodandisbasedontheinterior-reflectiveNewtonmethod.Medium-ScaleOptimization——fminuncwithoptions.LargeScalesetto'off'usestheBFGSQuasi-Newtonmethodwithamixedquadraticandcubiclinesearchprocedure.Thisquasi-NewtonmethodusestheBFGSformulaforupdatingtheapproximationoftheHessianmatrix.TheDFPformula,whichapproximatestheinverseHessianmatrix,isselectedbysettingoptions.HessUpdateto'dfp'(andoptions.LargeScaleto'off').Asteepestdescentmethodisselectedbysettingoptions.HessUpdateto'steepdesc'(andoptions.LargeScaleto'off'),althoughthisisnotrecommended.Thedefaultlinesearchalgorithm,i.e.,whenoptions.LineSearchTypeissetto'quadcubic',isamixedquadraticandcubicpolynomialinterpolationandextrapolationmethod.(3)MaxIter:允许进行迭代的最大次数,取值为正整数.options中常用的几个参数的名称、含义、取值如下:(1)Display:显示水平.取值为’off’时,不显示输出;取值为’iter’时,显示每次迭代的信息;取值为’final’时,显示最终结果.默认值为’final’.(2)MaxFunEvals:允许进行函数计算的最大次数,取值为正整数.例：opts=optimset(‘Display’,’iter’,’TolFun’,1e-8)该语句创建一个称为opts的优化选项结构,其中显示参数设为’iter’,TolFun参数设为1e-8.控制参数options可以通过函数optimset创建或修改.格式为options=optimset(‘param1’,value1,’param2’,value2,...)创建一个名称为options的优化选项参数,其中指定的参数具有指定值,所有未指定的参数取默认值.用Matlab解无约束优化问题函数fminbnd的算法基于0.618算法和二次插值法，它要求目标函数必须是连续函数，并可能只给出局部最优解。常用格式如下：(1)x=fminbnd(fun,x1,x2)(2)x=fminbnd(fun,x1,x2,options)(3)[x，fval]=fminbnd(...)(4)[x，fval，exitflag]=fminbnd(...)(5)[x，fval，exitflag，output]=fminbnd(...)命令格式为:(1)x=fminunc(fun,X0)；或x=fminsearch(fun,X0)(2)x=fminunc(fun,X0,options)；或x=fminsearch(fun,X0,options)(3)[x,fval]=fminunc(...)；或[x,fval]=fminsearch(...)(4)[x,fval,exitflag]=fminunc(...)；或[x,fval,exitflag]=fminsearch(5)[x,fval,exitflag,output]=fminunc(...)；或[x,fval,exitflag,output]=fminsearch(...)2、多元函数无约束优化问题标准型为：minF(X)[3]fminunc为中型优化算法的步长一维搜索提供了两种算法，由options中参数LineSearchType控制：LineSearchType=’quadcubic’(缺省值)混合的二次和三次多项式插值；LineSearchType=’cubicpoly’，三次多项式插使用fminunc和fminsearch可能会得到局部最优解.fminsearch是用单纯形法寻优.fminunc的算法见以下几点说明：[1]fminunc为无约束优化提供了大型优化和中型优化算法。由options中的参数LargeScale控制：LargeScale=’on’(默认值),使用大型算法(信赖域算法)LargeScale=’off’(默认值),使用中型算法[2]fminunc为中型优化算法的搜索方向提供了4种算法，由options中的参数HessUpdate控制a：HessUpdate=’bfgs’(默认值),拟牛顿法的BFGS公式；HessUpdate=’dfp’，拟牛顿法的DFP公式；HessUpdate=’steepdesc’，最速下降法例4Rosenbrock函数f(x1，x2)=100(x2-x12)2+(1-x1)2的最优解(极小)为x*=(1,1)，极小值为f*=0.试用不同算法(搜索方向和步长搜索)求数值最优解.初值选为x0=(-1.2,2).1.为获得直观认识,先画出Rosenbrock函数的三维图形,输入以下命令:[x,y]=meshgrid(-2:0.1:2,-1:0.1:3);z=100*(y-x.^2).^2+(1-x).^2;mesh(x,y,z)2.画出Rosenbrock函数的等高线图,输入命令：contour(x,y,z,20)holdonplot(-1.2,2,'o');text(-1.2,2,'startpoint')plot(1,1,'o')text(1,1,'solution')3.用fminsearch函数求解输入命令:f='100*(x(2)-x(1)^2)^2+(1-x(1))^2';[x,fval,exitflag,output]=fminsearch(f,[-1.22])运行结果:x=1.00001.0000fval=1.9151e-010exitflag=1output=iterations:108funcCount:202algorithm:'Nelder-Meadsimplexdirectsearch'使用fminunc函数见Matlab演示！简化得:——这是经济学中著名的柯布-道格拉斯(Cobb-Douglas)生产函数，其更一般的形式为:其中a,b,c由统计数据确定——最小二乘问题!现有统计数据(Qi,Ki,Li),i＝1,2,...,n.代入上式分别可得n个方程:由于统计特性，一般来说，这些等式不可能完全成立，记:最小二乘问题就是使得该误差项尽可能小，于是极小化：这是非线性最小二乘问题！对该式两端取对数，可得这样对统计数据(Qi,Ki,Li),i＝1,2,...,n.代入上式分别可得n个线性方程:使得以上等式误差项尽可能小，于是极小化：这样就转化为线性最小二乘问题！——这更容易求解模型验证美国马萨诸赛州1890－1926年统计数据(以1899年归1)tQKLtQKLtQKL18900.720.950.7819031.301.221.2219162.093.611.8618910.780.960.8119041.301.271.1719171.964.101.9318920.840.990.8519051.421.371.3019182.204.361.961893