无约束规划

4.无约束规划无约束规划建模——引例无约束规划模型无约束规划的示意图无约束规划的性质无约束规划重要算法用MATLAB解无约束规划引例1：某城市要选定一个供应中心(供电、供水、公天然气、网络接入等)的位置，该中心向城市中由固定位置的m个用户提供服务。问如何确定这个中心的位置才是最合理的？解设用户位置为(ai,bi)(i=1,2,...,m)已知，而供应中心的位置是(x1,x2)；假设运输线路不受道路影响，只考虑直线距离，则可建立求总距离最短的数学模型为：miiibxaxxxf1222121),(min其中：c——运价(元/吨公里)；wi——第i个用户的需求量.miiiibxaxwcxxf1222121),(min若进一步考虑各单位的用量wi不同，而运价c按距离计算，则可建立求总总费用最小的数学模型为：“定位问题”——厂址选择等引例2：在某些实际问题中，往往要求决策变量x1,x2,...,xn满足(或近似满足)某些平衡条件，它表现为要求x1,x2,...,xn满足方程组pjxxfnj,,2,1,0),,(1即要求均方误差最小——最小二乘问题，包括线性最小二乘和非线性最小二乘问题，在数学建模中有非常重要的应用。mjnxxf121),,(min可转化为求解问题：“最小二乘问题”——解方程组无约束规划模型标准形式：XfnRXmin):(RRfn其中XfXfnnRXRXminmax转化：等高线1x2x)(21xxfO1x2x05310X1X2X)(0Xf)(1Xf)(2Xf无约束规划的示意图多局部极小298.0f0f298.0f唯一极小(全局极小)2122212121322)(xxxxxxxxf22221222222212122122122)()(nnnnnxfxxfxxfxxfxfxxfxxfxxfxfXHXf无约束规划的性质梯度TnxXfxXfxXfXf)(,,)(,)()(21列向量梯度的特点：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)选定初始点X0，令k＝0；(2)在Xk处选定下降方向Sk(若找不到则终止算法);(3)从Xk出发沿Sk一维搜索,找到Xk+1=Xk+λkSk,使得f(Xk+1)f(Xk)；(4)从k=k+1,转(2).kX1kX2kX1kSkS2kSkkS无约束规划的基本算法一维搜索基本原则：1)最优原则：2)可接受点原则：)(min)(:0kkkkkkSXfSXf)()(:kkkkkXfSXf一维搜索方法：0.618法、插值法等下降方向：与梯度点乘为负值的方向0)(kTkSXf0)()()()(SoSXfXfSXfT无约束规划的基本算法下降方向选择方法——算法分类0)()()()()(22SoSXfSSXfXfSXfTT1.最速下降法——梯度法)(kkXfS2.共轭梯度法(包含多种方法)——梯度法的修正3.牛顿法)()(12kkkXfXfS牛顿法特点：二次函数1次收敛；单步迭代计算量大，且要求海森矩阵可逆。无约束规划的基本算法3.拟牛顿法拟牛顿法特点：较梯度法收敛速度快速，较牛顿法稳定且计算量小。为克服牛顿法的缺点，同时保持较快收敛速度的优点，利用第k步和第k+1步得到的kX，1kX，)(kXf，)(1kXf，构造一个正定矩阵1kH近似代替12))((kXf，将牛顿方向改为：)(111kkkxfHS从而得到下降方向.4.信赖域算法——对大型问题稳定性好，有成功的应用无约束规划的基本算法两个著名的拟牛顿迭代公式:kTkTkkkkTkkkTkTkkkTkkkTkkkXgXgHHgXXgXxxggHgHH)()()()()()()(11kkTkkTkkkkTkTkkkkgHgHggHXgXXHH)()()()(1)()(11kkkkkkXfXfgXXX其中：BFGSDFP)(111kkkXfHSMatlab求解无约束规划问题类型模型基本函数名一元函数极小MinF(x)s.t.x1xx2x=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由优化函数求得的值.若exitflag0,则x为解;否则,x不是最终解,它只是迭代终止时优化过程的值fval解x处的目标函数值exitflag描述退出条件:exitflag0,表目标函数收敛于解x处exitflag=0,表已达到函数计算或迭代的最大次数exitflag0,表目标函数不收敛output包含优化结果信息的输出结构.Iterations:迭代次数Algorithm:所采用的算法FuncCount:计算函数值次数(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解无约束优化问题1.一元函数无约束优化问题:minf（x）21xxx函数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求f=2xexsin在0x8中的最小值与最大值主程序为test.m:f='2*exp(-x).*sin(x)';f1='-2*exp(-x).*sin(x)';fplot(f,[0,8],'*-');%作图语句holdon,fplot(f1,[0,8],'^-');%作图语句[xmin,ymin]=fminbnd(f,0,8)[xmax,ymax]=fminbnd(f1,0,8)运行结果：xmin=3.9270ymin=-0.0279xmax=0.7854ymax=0.6448命令格式为:(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’，最速下降法例3minf(x)=(4x12+2x22+4x1x2+2x2+1)*exp(x1)1、编写M-文件fun1.m:functionf=fun1(x)f=exp(x(1))*(4*x(1)^2+2*x(2)^2+4*x(1)*x(2)+2*x(2)+1);2、输入M文件test.m如下:x0=[-1,1];x=fminunc(‘fun1’,x0);y=fun1(x)3、运行结果:x=0.5000-1.0000y=1.3029e-10例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