1、约束优化约束优化constrained optimization的简单分类的简单分类数学规划数学规划mathematical programming或连续优化或连续优化continuous optmization 线性规划线性规划(LP)目标和约束均为线性函数目标和约束均为线性函数 Linear programming 非线性规划非线性规划(NLP)目标或约束中存在非线性函数目标或约束中存在非线性函数 Nonlinear programming 二次规划二次规划(QP)目标为二次函数、约束为线性目标为二次函数、约束为线性 Quadratic programming一般优化问题概述整数规划整数规
2、划(IP)决策变量决策变量(全部或部分全部或部分)为整数为整数Integer programming 整数整数线性线性规划规划(ILP)，整数，整数非线性非线性规划规划(INLP)纯整数规划纯整数规划(PIP),混合整数规划混合整数规划(MIP)Pure(mixed)Integer programming 一般整数规划，一般整数规划，0-1（整数）规划（整数）规划Zero-one programming离散优化离散优化discrete optimization或组合优化或组合优化combinatorial optimization一般优化问题概述 无约束最优化问题无约束最优化问题求解无约束最优
3、化问题的的基本思想求解无约束最优化问题的的基本思想*无约束最优化问题的基本算法无约束最优化问题的基本算法返回 XfnEXmin 其中 1:EEfn标准形式：标准形式：求解无约束最优化问题的基本思想求解无约束最优化问题的基本思想求解的基本思想求解的基本思想 (以二元函数为例)1x2x)(21xxf01x2x05310X1X2X)(0Xf)(1Xf)(2Xf连续可微 XfnEXmax=minXfnEX 多局部极小298.0f0f298.0f 唯一极小(全局极小)2122212121322)(xxxxxxxxf搜索过程搜索过程21221221)1()(100)(minxxxxxf最优点 (1 1)初
4、始点 (-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.630.050.950.90 0.0030.990.991E-40.9990.9981E-50.9997 0.9998 1E-8返回 给定初始点nEX 0，允许误差0,令 k=0；计算kXf；检验是否满足收敛性的判别准则：kXf，若满足，则停止迭代，得点kXX*，否则进行；令kkXfS，从kX出发，沿kS进行一维搜索，即求k使得：kkkkkSXfSXf0min；令kkkkSXX1，k=k+1
5、 返回.无约束优化问题的基本算法无约束优化问题的基本算法 最速下降法是一种最基本的算法，它在最优化方法中占有重要地位.最速下降法的优点是工作量小，存储变量较少,初始点要求不高；缺点是收敛慢，最速下降法适用于寻优过程的前期迭代或作为间插步骤，当接近极值点时，宜选用别种收敛快的算法.1 1最速下降法（共轭梯度法）算法步骤：最速下降法（共轭梯度法）算法步骤：2 2牛顿法算法步骤：牛顿法算法步骤：(1)选定初始点nEX 0，给定允许误差0，令 k=0；(2)求kXf,12kXf,检验：若kXf,则 停止迭代,kXX*.否则,转向(3)；(3)令 kkkXfXfS12（牛顿方向）；(4)kkkSXX1,
6、1 kk,转回(2).如果f是对称正定矩阵A的二次函数，则用牛顿法经过一次迭代一次迭代就可达到最优点,如不是二次函数，则牛顿法不能一步达到极值点，但由于这种函数在极值点附近和二次函数很近似,因此牛顿法的收敛速度还是很快的.牛顿法的收敛速度虽然较快，但要求Hessian矩阵要可逆，要计算二阶导数和逆矩阵，就加大了计算机计算量和存储量.MatlabMatlab优化工具箱简介优化工具箱简介1.MATLAB1.MATLAB求解优化问题的主要函数求解优化问题的主要函数类 型模 型基本函数名一元函数极小Min F（x）s.t.x1xx2x=fminbnd(F,x1,x2)无约束极小Min F(X)X=fm
7、inunc(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)=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,qu
8、adprog,fgoalattain,fmincon,fminimax,lsqcurvefit,lsqnonlin,fminbndexitflag描述退出条件:exitflag0,表目标函数收敛于解x处 exitflag=0,表已达到函数评价或迭代的最大次数 exitflag0,表目标函数不收敛output包含优化结果信息的输出结构.Iterations:迭代次数 Algorithm:所采用的算法 FuncCount:函数评价次数所有优化函数用用MatlabMatlab解无约束优化问题解无约束优化问题 1.一元函数无约束优化问题一元函数无约束优化问题:min f（x）21xxx 其中（3）、（
9、4）、（5）的等式右边可选用（1）或（2）的等式右边。函数fminbnd的算法基于黄金分割法和二次插值法，它要求目标函数必须是连续函数，并可能只给出局部最优解。常用格式如下：常用格式如下：（1）x=fminbndx=fminbnd(fun,xfun,x1 1,x,x2 2)（2）x=fminbndx=fminbnd(fun,xfun,x1 1,x,x2 2 ，options)options)（3）xx，fval=fminbndfval=fminbnd（.）（4）xx，fvalfval，exitflag=fminbndexitflag=fminbnd（.）（5）xx，fvalfval，exitf
10、lagexitflag，output=fminbndoutput=fminbnd（.）运行结果：xmin=3.9270 ymin=-0.0279 xmax=0.7854 ymax=0.6448To Matlab(wliti1)例例 1 1 求 f=2xexsin在 0 x8 中的最小值与最大值 主程序为主程序为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)例例2 2 对边长为3米的正方形
11、铁板，在四个角剪去相等的正方形以制成方形无盖水槽，问如何剪法使水槽的容积最大？设剪去的正方形的边长为x，则水槽的容积为：xx)23(2建立无约束优化模型为：min y=-xx)23(2，0 x 0，且a11 a12；同理，p2=b2-a21 x1-a22 x2，b2，a21，a22 0，且a22 a21.2 2成本与产量成负指数关系成本与产量成负指数关系甲的成本随其产量的增长而降低,且有一个渐进值,可以假设为负指数关系,即:0,11111111crcerqx 同理，0,22222222crcerqx 模型建立模型建立 若根据大量的统计数据,求出系数b1=100,a11=1,a12=0.1,b2
12、=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,问题转化为求: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 2 模型求解模型求解 1.
13、建立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=(280-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)返回练习练习1.求下列函数的极小点：1)2
14、123222118294xxxxxXf；2)212122212223xxxxxxXf；3)224121 xXf.第 1），2）题的初始点可任意选取，第 3）题的初始点取为TX1,00.（1）线性逼近法）线性逼近法基本思想：基本思想：将目标函数和约束函数近似为线性函数，转将目标函数和约束函数近似为线性函数，转化为线性规划问题求解，重复这个过程。化为线性规划问题求解，重复这个过程。步骤：步骤：给定控制误差给定控制误差0，初始可行点，初始可行点xk,初始步长初始步长k0,在在xk线性化得线性规划问题：线性化得线性规划问题：min .0,1,0,1,TkkkTikikkTjkjkkkkfxfxxxs
15、txxxxikxxxxjkmxx 非线性规划有约束问题 求出此线性规划问题得最优解求出此线性规划问题得最优解xk1，检验，检验是否为原问题的的可行解，若是转是否为原问题的的可行解，若是转，否则缩短，否则缩短步长转步长转；判断精度。判断精度。1,kkxx 若若则取则取最优解最优解x*=xk+1,停，否则令停，否则令k=k+1转转。12211221 min .0 0fXxxs tgxxxgxx 例例：非线性规划有约束问题（2）罚函数法）罚函数法转化为无约束最优化问题：转化为无约束最优化问题：22min,min 0,ijF x MfxMxMx M为足够大的正数。称为为足够大的正数。称为罚因子罚因子。
16、算法分析：算法分析：设可行域为设可行域为S，构造函数：，构造函数：20 ,1iixSuximxxS 非线性规划有约束问题 iixux 令令 求无约束问题得最优解为求无约束问题得最优解为X(M),直观看出，直观看出，只有当只有当X(M)S才可能真正取得极小值，若才可能真正取得极小值，若 ,X MS 就就加大加大罚因子罚因子M，使，使X(M)向向S逼近，逼近，当当M时，点列时，点列 。外外趋趋于于最最优优解解从从*XSMXK非线性规划有约束问题计算步骤计算步骤：（第：（第k次迭代）次迭代）。优优解解，求求解解无无约约束束问问题题得得最最取取kkXM01 .,*k121转转，否则取，否则取则则若若k
17、kkkMMXXxM 12211221 min .0 0fXxxs tgxxxgxx 例例：2111,min,2124 1TXSX MMMM 非线性规划有约束问题有约束问题matlab解法ubxlbbeqxAeqbAxxceqxctosubjuctxf0)(0)()(minx,fval=fmincon(myfun,x0,A,b)x,fval=fmincon(myfun,x0,A,b,Aeq,beq)x,fval=fmincon(myfun,x0,A,b,Aeq,beq,lb,ub)x,fval=fmincon(myfun,x0,A,b,Aeq,beq,lb,ub,comfun)缺省的用代替myf
18、un与confun是M-函数的地址具体如:目标函数：Function f=myfun(x)非线性约束：function c,ceq=confun(x)%Nonlinear inequality constraintsc=c1(x);c2(x);.;%Nonlinear equality constraintsceq=ceq1(x);ceq2(x);.;M-函数1先建立先建立M文件文件 fun4.m,定义目标函数定义目标函数:function f=fun4(x);f=exp(x(1)*(4*x(1)2+2*x(2)2+4*x(1)*x(2)+2*x(2)+1);)12424()(22122211
19、xxxxxexfx x1+x2=0 s.t.1.5+x1x2-x1-x2 0 -x1x2 10 0例例32再建立再建立M文件文件mycon.m定义非线性约束：定义非线性约束：function g,ceq=mycon(x)g=x(1)+x(2);1.5+x(1)*x(2)-x(1)-x(2);-x(1)*x(2)-10;例4 100 ,50 07 025 .2min 21222122221121xxxxXgxxXgtsxxXf1先建立先建立M-文件文件fun.m定义目标函数定义目标函数:function f=fun(x);f=-2*x(1)-x(2);2再建立再建立M文件文件mycon2.m定义
20、非线性约束：定义非线性约束：function g,ceq=mycon2(x)g=x(1)2+x(2)2-25;x(1)2-x(2)2-7;应用实例：应用实例：供应与选址供应与选址 某公司有6个建筑工地要开工，每个工地的位置（用平面坐标系a，b表示，距离单位：千米）及水泥日用量d(吨)由下表给出。目前有两个临时料场位于A(5,1)，B(2,7)，日储量各有20吨。假设从料场到工地之间均有直线道路相连。（1）试制定每天的供应计划，即从A，B两料场分别向各工地运送多少吨水泥，使总的吨千米数最小。（2）为了进一步减少吨千米数，打算舍弃两个临时料场，改建两个新的，日储量各为20吨，问应建在何处，节省的吨
21、千米数有多大？工地位置（a，b）及水泥日用量 d 1 2 3 4 5 6 a 1.25 8.75 0.5 5.75 3 7.25 b 1.25 0.75 4.75 5 6.5 7.25 d 3 5 4 7 6 11 （一）、建立模型（一）、建立模型 记工地的位置为记工地的位置为(ai，bi)，水泥日用量为，水泥日用量为di，i=1,6;料场位置为料场位置为(xj，yj)，日储量为，日储量为ej，j=1,2；从料场；从料场j向工地向工地i的运送量为的运送量为Xij。目标函数为：216122)()(minjiijijijbyaxXf 约束条件为：2,1 ,6,2,1 ,6121jeXidXjiij
22、ijij 当用临时料场时决策变量为：Xij，当不用临时料场时决策变量为：Xij，xj，yj。（二）使用临时料场的情形（二）使用临时料场的情形 使用两个临时料场A(5,1)，B(2,7).求从料场j向工地i的运送量为Xij，在各工地用量必须满足和各料场运送量不超过日储量的条件下，使总的吨千米数最小，这是线性规划问题.线性规划模型为：2161),(minjiijXjiaaf2,1 ,6,2,1 ,s.t.6121jeXidXjiijijij其中 22)()(),(ijijbyaxjiaa，i=1,2,6,j=1,2,为常数。设X11=X1,X21=X 2,X31=X 3,X41=X 4,X51=X
23、 5,X61=X 6X12=X 7,X22=X 8,X32=X 9,X42=X 10,X52=X 11,X62=X 12 编写程序gying1.mMATLAB（gying1）计算结果为：计算结果为：x=3.0000 5.0000 0.0000 7.0000 0.0000 1.0000 0.0000 0.0000 4.0000 0.0000 6.0000 10.0000fval=136.2275即由料场A、B向6 个工地运料方案为：1 2 3 4 5 6 料场A 3 5 0 7 0 1 料场B 0 0 4 0 6 10 总的吨千米数为136.2275。（三）改建两个新料场的情形（三）改建两个新料
24、场的情形 改建两个新料场，要同时确定料场的位置(xj,yj)和运送量Xij，在同样条件下使总吨千米数最小。这是非线性规划问题。非线性规划模型为：216122)()(minjiijijijbyaxXf2,1 ,6,2,1 ,.6121jeXidXtsjiijijij设 X11=X1,X21=X 2,X31=X 3,X41=X 4,X51=X 5,X61=X 6 X12=X 7,X22=X 8,X32=X 9,X42=X 10,X52=X 11,X62=X 12 x1=X13,y1=X14,x2=X15,y2=X16 （1）先编写M文件liaoch.m定义目标函数。MATLAB（liaoch）(2
25、)取初值为线性规划的计算结果及临时料场的坐标:x0=3 5 0 7 0 1 0 0 4 0 6 10 5 1 2 7;编写主程序gying2.m.MATLAB（gying2）(3)计算结果为：x=3.0000 5.0000 0.0707 7.0000 0 0.9293 0 0 3.9293 0 6.0000 10.0707 6.3875 4.3943 5.7511 7.1867fval=105.4626exitflag=1即两个新料场的坐标分别为(6.3875,4.3943),(5.7511,7.1867),由料场 A、B 向 6 个 工地运料方案为：1 2 3 4 5 6 料场 A 3 5
26、0.0707 7 0 0.9293 料场 B 0 0 3.9293 0 6 10.0707 总的吨千米数为105.4626。比用临时料场节省约 31 吨千米.(4)若修改主程序gying2.m,取初值为上面的计算结果:x0=3.0000 5.0000 0.0707 7.0000 0 0.9293 0 0 3.9293 0 6.0000 10.0707 6.3875 4.3943 5.7511 7.1867得结果为:x=3.0000 5.0000 0.3094 7.0000 0.0108 0.6798 0 0 3.6906 0 5.9892 10.3202 5.5369 4.9194 5.829
27、1 7.2852fval=103.4760exitflag=1总的吨千米数比上面结果略优.(5)若再取刚得出的结果为初值,却计算不出最优解.MATLAB（gying2）MATLAB（gying2）(6)若取初值为:x0=3 5 4 7 1 0 0 0 0 0 5 11 5.6348 4.8687 7.2479 7.7499,则计算结果为:x=3.0000 5.0000 4.0000 7.0000 1.0000 0 0 0 0 0 5.0000 11.0000 5.6959 4.9285 7.2500 7.7500fval=89.8835exitflag=1总的吨千米数89.8835比上面结果更好.通过此例可看出fmincon函数在选取初值上的重要性.MATLAB（gying2）返回返回
