二次-多目标-最大最小化

1、次、目标及动态规划§ 1二次规划模型数学模型：min - xT Hx f Txx 2A x空bAeq x = beqlb兰x兰ub其中H为二次型矩阵，A、Aeq分别为不等式约束与等式 约束系数矩阵，f,b,beq,lb,ub,x 为向量。求解二次规划问题函数为quadprog()调用格式：X= quadprog(H,f,A,b)X= quadprog(H,f,A,b,Aeq,beq)X= quadprog(H,f,A,b,Aeq,beq,lb,ub) X= quadprog(H,f,A,b,Aeq,beq,lb,ub,xO) X=quadprog(H,f,A,b,Aeq,beq,lb

2、,ub,xO,options)x,fval= quadprog( )x,fval,exitflag= quadprog( ) x,fval,exitflag,output= quadprog()x,fval,exitflag,output,lambda=quadprog()说明：输入参数中，x0为初始点；若无等式约束或无不 等式约束，就将相应的矩阵和向量设置为空； options 为指 定优化参数。输出参数中，x是返回最优解；fval是返回解所对应的目标函数值；exitflag是描述搜索是否收敛；output是返回包含优化信息的结构。Lambda是返回解x入包含拉格朗日乘子的参数。例1:求解：

3、二次规划问题2 2min f(x)= x1-3x 2+3x1 +4x2 -2x 1X2s.t 2x1+X2W 2-x 1 +4x2 < 3程序： f=1;-3H=6 -2;-2 8A=2 1;-1 4b=2;3X,fval,exitflag=quadprog(H,f,A,b) 结果： X =-0.04550.3636fval =-0.5682exitflag =1例 2：求解：二次规划问题22min x 1 +2x2 -2x 1x2-4x 1-12x 2 s.t x 1+X2W 2-x 1+2x2 < 22xi+X2< 3 0<x 1, 0 <x 2 程序： H=

4、2 -2;-2 4;f=-4;-12;A=1 1;-1 2;2 1;b=2;2;3;lb=zeros(2,1);x,fval,exitflag=quadprog(H,f,A,b,lb) 结果： x =0.66671.3333fval =-16.4444exitflag =1练习1求解下面二次规划问题min f(x) =2x x2x1x -2x6x2sub .toXi X2 岂 2-x1 2x2 <22xi x2 <30 _Xi,0 _X2解：f(x) =1 x Hx f x2在MATLAB中实现如下：>>H = 1-1; -1 2;>>f = -2； -6;

5、>>A = 1 1; -1 2; 2 1;>>b = 2; 2; 3;>>lb = zeros(2,1);>>x,fval,exitflag,output,lambda quadprog(H,f,A,b, , ,lb)结果为：x =%最优解0.66671.3333fval =%最优值-8.2222exitflag =%收敛1output =iterations: 3algorithm: 'medium-scale: active-set' firstorderopt: cgiterations: lambda =lower: 2x

6、1 doubleupper: 2x1 doubleeqlin: 0x1 doubleineqlin: 3x1 double>> lambda.ineqlinans =3.11110.44440>> lambda.lowerans =00说明 第 1、2 个约束条件有效，其余无效。练习2求二次规划的最优解max f (xi, X2)=xiX2+3sub.toX1 +X2-2=0解：化成标准形式:min f (x1 X2)一X1X2 3 誌凶 X2)0 X1 (0, 0) X1 32、-1 0丿凶丿X2丿sub .tox1+x2=2在 Matlab中实现如下：>>

7、;H=0,-1;-1,0;>>f=0；0；>>Aeq=1 1;>>beq=2;>>x,fval,exitflag,output,lambdaquadprog(H,f, , ,Aeq,beq)结果为：x =1.0000 1.0000fval =-1.0000 exitflag =output =1firstorderopt: 0iterati on s: 1cgiteratio ns: 1algorithm: 1x58 charlambda =eqli n: 1.0000in eqli n:lower:upper:§ 2最小二乘最优问题1

8、约束线性最小二乘有约束线性最小二乘的标准形式为min 1 Cx -d 2x 22subtoA x ZbAeq x =beqI b Ex Eub其中：C、A、Aeq 为矩阵；d、b、beq、lb、ub、x 是向量。函数 Isqlin格式 x = lsqlin(C,d,A,b)%求在约束条件a ib下，方程Cx = d的最小二乘解x。x = lsqlin(C,d,A,b,Aeq,beq) %Aeq、beq 满足等式约束Aeq x = beq，若没有不等式约束，则设A= ,b=。x = lsqlin(C,d,A,b,Aeq,beq,lb,ub) %lb、ub 满足lb乞xub，若没有等式约束，则 A

9、eq=, beq=。x = lsqlin(C,d,A,b,Aeq,beq,lb,ub,xO) % x0 为初始解 向量，若x没有界，则 lb= , ub=。x = lsqlin(C,d,A,b,Aeq,beq,lb,ub,xO,options) % options为指定优化参数x,resnorm = lsqlin( )%resnorm=norm(C*x-d)A2，即 2-范数。x,resnorm,residual=lsqlin()residual=C*x-d，即残差。x,resnorm,residual,exitflag=lsqlin( )%exitflag为终止迭代的条件x,resnorm,

10、residual,exitflag,output=lsqlin()% output表示输出优化信息x,resnorm,residual,exitflag,output,lambda=lsqlin()% lambda 为解x的Lagrange乘子例1求解下面系统的最小二乘解系统：Cx=d约束： A x辽b ； I b乞x乞ub先输入系统系数和X的上下界:C = 0.95010.76200.61530.4057;0.23110.45640.79190.9354;0.60680.01850.92180.9169;0.48590.82140.73820.4102;0.89120.44470.17620

11、.8936d = 0.0578; 0.3528; 0.8131; 0.0098; 0.1388;A = 0.20270.27210.74670.4659;0.19870.19880.44500.4186;0.60370.01520.93180.8462b = 0.5251; 0.2026; 0.6721;lb = -0.1*o nes(4,1);ub = 2*o nes(4,1);然后调用最小二乘命令：x,res norm,residual,exitflag,output,lambda lsqli n( C,d,A,b, , ,lb,ub);结果为：-0.1000-0.10000.2152x

12、=0.3502resnorm =0.1672 residual =0.04550.0764-0.35620.16200.0784 exitflag =1% 说明解 x 是收敛的output =iterations: 4 algorithm: 'medium-scale: active-set' firstorderopt: cgiterations: lambda =lower: 4x1 doubleupper: 4x1 double eqlin: 0x1 doubleineqlin: 3x1 double通过 lambda.ineqlin 可查看非线性不等式约束是否有效2非线

13、性数据（曲线）拟合非线性曲线拟合是已知输入向量 xdata和输出向量ydata, 并且知道输入与输出的函数关系为 ydata=F(x, xdata)，但不知道 系数向量X。今进行曲线拟合，求 x使得下式成立：min 1 |F(x, xdata) -ydata ：(F(x,xdatai) -ydata )2x 22 i函数 Isqcurvefit格式 x = Isqcurvefit(fun,xO,xdata,ydata)x = Isqcurvefit(fun,xO,xdata,ydata,Ib,ub)x = Isqcurvefit(fun,xO,xdata,ydata,Ib,ub,options

14、)x,resnorm = Isqcurvefit()x,resnorm,residuaI = Isqcurvefit()x,resnorm,residual,exitflag = Isqcurvefit()x,resnorm,residual,exitflag,output = Isqcurvefit()x,resnorm,residual,exitflag,output,lambda=Isqcurvefit()x,resnorm,residual,exitflag,output,lambda,jacobian =lsqcurvefit()参数说明：x0为初始解向量；xdata ,ydata为

15、满足关系ydata=F(x, xdata)的数据；lb、ub为解向量的下界和上界Ib x Ub，若没有指定界，则 lb= , ub=；options为指定的优化参数；fun为拟合函数，其定义方式为：x =lsqcurvefit(myfun,xO,xdata,ydata),其 中 myfun 已定义为function F =myfun(x,xdata)F =%计算x处拟合函数值fun的用法与前面相同；resnorm=sum (fun(x,xdata)-ydata)八2)，即在 x 处残差的平方和；residual=fun(x,xdata)-ydata，即在 x 处的残差；exitflag为终止迭

16、代的条件；output为输出的优化信息；lambda为解 x处的 Lagrange乘子；jacobian为解x处拟合函数fun的jacobian矩阵。例2求解如下最小二乘非线性拟合问题已知输入向量xdata和输出向量ydata，且长度都是 n，拟 合函数为ydata(i) =x(1) xdata(i)2x(2) sin(xdata(i) x(3) xdata(i)3即目标函数为 min 丄二(F(x, xdata)-ydataj2x2 i#其中： F(x, xdata) =x(1) xdata2 x(2) sin(xdata) x(3) xdata3初始解向量为x0=0.3, 0.4, 0.1

17、。解：先建立拟合函数文件，并保存为ff4.mfun cti on F = ff4(x,xdata)F = x(1)*xdata.八2 + x(2) *si n(xdata) + x(3)*xdata.八3;然后给出数据xdata和ydata>>xdata = 3.6 7.7 9.3 4.1 8.6 2.8 1.3 7.9 10.0 5.4;>>ydata = 16.5 150.6 263.1 24.7 208.5 9.9 2.7 163.9 325.054.3;>>x0 = 10,10,10;% 初始估计值>>x,res norm = lsqcu

18、rvefit(ff4,x0,xdata,ydata)结果为：Optimization terminated successfully:Relativefun cti onvaluecha ngingby lesstha nOPTIONS.TolF un0.22690.33850.3021 resnorm =6.29503非线性最小二乘非线性最小二乘（非线性数据拟合）的标准形式为mjn f (x) =f1(x)2 +f2(x)2 +fm(x)2 +L其中：L为常数在6.0版中使用函数Isqnonlin。 fi(x)设 F(X)= f 2(X)'fm(X) 一则目标函数可表达为min 1

19、F(x) 2 = V fi(x)2x 22 i其中：x为向量，F(x)为函数向量。函数 Isqnonlin格式 x = Isqnonlin(fun,x0) %x0为初始解向量；fun为 fi(x), i=1,2,m, fun返回向量值F，而不是平 方和值，平方和隐含在算法中，fun的定义与前面相同。x = Isqnonlin(fun,x0,lb,ub) %lb、ub 定义 x 的下界和上界：lb_x_ub。x = lsqnonlin(fun,xO,lb,ub,options) %options 为指定优化参数，若x没有界，则lb= ，ub=。x,resnorm = lsqnonlin()%re

20、snorm=sum(fun(x)八2)，即解x处目标函数值。x,resnorm,residual = lsqnonlin()%residual=fun(x)，即解 x 处 fun 的值。x,resnorm,residual,exitflag=lsqnonlin()%exitflag为终止迭代条件。x,resnorm,residual,exitflag,output=lsqnonlin()%output输出优化信息。x,resnorm,residual,exitflag,output,lambda=lsqnonlin()%lambda 为 Lagrage 乘子。x,resnorm,residua

21、l,exitflag,output,lambda,jacobian=lsqnonlin() %fun 在解 x 处的 Jacobian 矩 阵。k 10例3求下面非线性最小二乘问题、(2 2k _ekx1 _ekx2)2初始解k 4向量为 x0=0.3, 0.4。解：先建立函数文件，并保存为myfun.m，由于Isqnonlin中的fun为向量形式而不是平方和形式，因此，myfun函数应由fi(x)建立：fk(x)=2+2k-ekxi -ekx2k=1,2,10function F = ff5(x)k = 1:10;F = 2 + 2*k-exp(k*x(1)-exp(k*x(2);然后调用优

22、化程序：x0 = 0.3 0.4;x,res norm = Isqnon li n( ff5,x0)结果为：Optimization terminated successfully:Norm of the current step is less than OPTIONS.ToIX0.25780.2578res norm =%求目标函数值124.3622例 4.求 minf=4(X2-xd2+(X2-4)2，选择初始点 x°(1,1)程序：先建立m文件：Function f=ff6(x) f(1)=2*x(2)-2*x(1);f(2)=x(2)-4然后：调用x,resnorm, re

23、sidual=lsqnonlin(ff6,1,1) 结果： x =3.98963.9912resnorm =5.0037e-0094非负线性最小二乘非负线性最小二乘的标准形式为:minx21 Cx _d 2sub .tox _o其中：矩阵C和向量d为目标函数的系数，向量x为非负独立变量在6.0版中则用函数lsqnonne®函数 lsqnonneg格式 x = lsqnonneg(C,d) %C为实矩阵，d为实向量x = lsqnonneg(C,d,x0) % x0 为初始值且大于 0x = lsqnonneg(C,d,x0,options) % options 为指定 优化参数x,r

24、esnorm = lsqnonneg()% resnorm=norm(C*x-d)A2x,resnorm,residual=lsqnonneg()%residual=C*x-dx,resnorm,residual,exitflag = Isqnonneg()x,resnorm,residual,exitflag,output = Isqnonneg()x,resnorm,residual,exitflag,output,lambda=lsqnonneg()例5 一个最小二乘问题的无约束与非负约束解法的比较。 先输入数据：>>C = 0.0372 0.2869; 0.68610.70

25、71; 0.6233 0.6245;0.6344 0.6170;>>d = 0.8587; 0.1781; 0.0747; 0.8405;>> Cd, Is qnonn eg(C,d)ans =-2.562703.11080.6929注意：1。当问题为无约束线性最小二乘问题时，使用MATLAB 下的“ ”运算即可以解决。2.对于非负最小二乘问 题，调用 lsqnonneg(C,d)求解。§ 3多目标规划模型多目标规划定义为在一组约束下，多个不同的目标函数进行优化设计。数学模型：minfO, f2(x), fm(x)丨s.t g j (x) < 0 j=1

26、,2,k其中x=(x i ,x 2，,x n)为一个n维向量；f i(x)为目标函 数,i=1,2,m; g j (x)为系统约束,j=1,2,k 。当目标函数处于冲突状态时， 不存在最优解使所有目标函 数同时达到最优。于是我们寻求有效解(又称非劣解或非支配解或帕累托解)定义：若x“( x“ Q )的邻域内不存在 x ,使得 (x + A x Q )，且Fi x : :-x < Fi x i =1/ , mFj x -x : Fj x* 对某些 j则称x“为有效解。多目标规划问题的几种常用解法：(1) 主要目标法其基本思想是：在多目标问题中，根据问题的实际情况， 确定一个目标为主要目标，

27、而把其余目标作为次要目标，并 且根据经验，选取一定的界限值。这样就可以把次要目标作 为约束来处理，于是就将原来的多目标问题转化为一个在新 的约束下的单目标最优化问题(2) 线性加权和法f i(x) (i=1,2,m)的入j(j=1,2,m)然后相其基本思想是：按照多目标 重要程度，分别乘以一组权系数加作为目标函数而构成单目标规划问题mmin f = ' . j f j (x)jy其中例1:某钢铁厂准备用5000万用于A、B两个项目的技 术改造投资。设X2分别表示分配给项目A、B的投资。据专家预估计，投资项目A、B的年收益分别为70%和66% 同时，投资后总的风险损失将随着总投资和单项投

28、资的增加 而增加，已知总的风险损失为0.02x12+0.01x22+0.04(x1+x2)2,问应如何分配资金才能使期望的收益最大，同时使风险损失 为最小。建立数学模型max f1(x)=70x 1+66x2min f2(x)= 0.02x 12+0.01x22+0.04(x1+x2)2s.tx1+x2< 50000< x1,0 <x2线性加权构造目标函数：max f=0.5f 1(x) £.5f2(x)化最小值问题：min (-f)=- 0.5f 1(x) +0.5f 2(x)首先编辑目标函数 M文件ffll.mfunction f=ff11(x)f=-0.5*(

29、70*x(1)+66*x(2)+0.5*(0.02*x(1)A2+0.01*x(2F2 +0.04*(x(1)+x(2)A2);调用单目标规划求最小值问题的函数X0=1000,1000A=1 1; b=5000; lb=zeros(2,1);x,fval, exitflag=fmincon(ff11,x0, A,b,|,|,lb,|)f1=70*x(1)+66*x(2)f2=0.02*x(1)A2+0.01*x(2)A2+0.04*(x(1)+x(2)A2结果：x =307.1428 414.2857fval =-1.2211e+004exitflag =1f1 =4.8843e+004f2

30、=2.4421e+004(3) 极大极小法其基本思想是：对于极小化的多目标规划，让其中最大 的目标函数值尽可能地小，为此，对每个x R我们先求诸目标函数值fi(x)的最大值，然后再求这些最大值中的最 小值。即构造单目标规划：min f =咼諮fj(x)(4) 目标达到法对于多目标规划：minf1(x), f2(x)，fm(x)】s.t g j (x)< 0 j=1,2,n先设计与目标函数相应的一组目标值理想化向量* * *(f1,f2, fm),再设Y为一松弛因子标量。设W=(Wi，W2,，Wm)为权值系数向量。于是多目标规划问题化为：minfj x Wj - f j* j 1, 2,

31、, mgj(x)乞 0j =1,2, ,k在Matlab的优化工具箱中，fgoalattain函数用于解决此类问题。其数学模型形式为：min 丫F(x)- weight 丫 W goalc(x) w 0ceq(x)=0A x WbAeq x=beqlb WxW ub其中，x,weight,goal,b,beq,lb 和 ub 为向量，A 和 Aeq 为矩阵，c(x),ceq(x) 和F(x)为函数，调用格式：x=fgoalattain(F,x0,goal,weight)x=fgoalattain(F,x0,goal,weight,A,b) x=fgoalattain(F,x0,goal,wei

32、ght,A,b,Aeq,beq) x=fgoalattain(F,x0,goal,weight,A,b,Aeq,beq,lb,ub) x=fgoalattain(F,x0,goal,weight,A,b,Aeq,beq,lb,ub,nonlcon)x=fgoalattain(F,x0,goal,weight,A,b,Aeq,beq,lb,ub,nonlcon options)x=fgoalattain(F,x0,goal,weight,A,b,Aeq,beq,lb,ub,nonlcon,op tions,P1,P2)x,fval=fgoalattain() x,fval,attainfacto

33、r=fgoalattain() x,fval,attainfactor,exitflag,output=fgoalattain() x,fval,attainfactor,exitflag,output,lambda=fgoalattain()说明：F为目标函数；x0为初值；goal为F达到的指定 目标； weight 为参数指定权重； A、b 为线性不等式约束的矩 阵与向量； Aeq 、beq 为等式约束的矩阵与向量； lb、ub 为变 量 x 的上、下界向量； nonlcon 为定义非线性不等式约束函 数c(x)和等式约束函数ceq(x); options中设置优化参数。x 返回最优解；

34、fval 返回解 x 处的目标函数值； attainfactor 返回解 x 处的目标达到因子； exitflag 描述计算的退出条件； output 返回包含优化信息的输出参数； lambda 返回包含拉格 朗日乘子的参数。例2:某化工厂拟生产两种新产品A和B,其生产设备费用分别为 2 万元/ 吨和 5 万元/ 吨。这两种产品均将造成环境 污染，设由公害所造成的损失可折算为A为4万元/吨，B为1万元/吨。由于条件限制，工厂生产产品A和B的最大生产 能力各为每月 5 吨和 6 吨，而市场需要这两种产品的总量每 月不少于 7 吨。试问工厂如何安排生产计划，在满足市场需 要的前提下，使设备投资和公

35、害损失均达最小。该工厂决策 认为，这两个目标中环境污染应优先考虑，设备投资的目标 值为 20 万元，公害损失的目标为 12 万元。建立数学模型：设工厂每月生产产品 A为xi吨，B为X2吨，设备投资费为 f(x 1), 公害损失费为 f(x 2), 则问题表达为多目标优化问题：min f 1(x)=2x 1+5x2min f 2(x)=4x 1+x2s.t x i< 5x 2< 6X1+X27Xi ,x 2>0程序：首先编辑目标函数 M文件ff12.mfunction f=ffi2(x)f(i)= 2*x(1)+5*x(2); f(2)= 4*x(1) +x(2);按给定目标取

36、： goal=20,12; weight=20,12; x0=2,2A=1 0; 0 1;-1 -1;b=5 6 -7;lb=zeros(2,1);x,fval,attainfactor,exitflag=fgoalattain(ff12,x0,g oal,weight,A,b,lb,)结果： x =2.9167 4.0833fval =26.2500 15.7500attainfactor =0.3125exitflag =1例 3： 某工厂生产两种产品甲和乙，已知生产甲产品100公斤需 6个工时，生产乙产品 100 公斤需 8个工时。假定每 日可用的工时数为 48 工时。这两种产品每 10

37、0 公斤均可获 利 100 元。乙产品较受欢迎，且若有个老顾客要求每日供应 他乙种产品 500 公斤，问应如何安排生产计划？建立数学模型：设生产甲、乙两种产品的数量分别为x1和x2(以100公斤计) ，要使生产计划比较合理，应考虑用工时尽量少，获 利尽量大，其用多目标规划描述这：min f 1=6x1+8x2max f2=100(x1+x2)max f3=x2s.t 6x1+8x2< 48x2> 5x1 ,x2> 0将其标准化为：min f1=6x1+8x2min - f 2=-100(x1+x2)min - f 3=-x2s.t 6x1+8x2< 48-X2 w -5

38、Xi ,X2> 0程序：首先编辑目标函数M文件ff13.mfunction f=ff13(X)f(1)= 6*x(1)+8*x(2);f(2)= -100*(x(1) +x(2);f(3)=-x(2);按给定目标取：goal=48 -1000 -5;weight=48 -1000 -5;x0=2 2;A=6 8; 0 -1;b=48 -5; lb=zeros(2,1);x,fval,attainfactor,exitflag=fgoalattain(ff13,x0,goal,weigh t,A,b,lb,)结果： X =1.3333 5.0000fval =48.0000 -633.33

39、33-5.0000attainfactor =1.6338e-008eXitflag =1即生产计划为每日生产甲产品 133.33 公斤，生产乙产品500 公斤。§ 4 最大最小化模型基本思想：在对策论中， 我们常遇到这样的问题： 在最不 利的条件下，寻求最有利的策略。在实际问题中也有许多求 最大值的最小化问题。例如急救中心选址问题就是要规划其 到所有地点最大距离的最小值。在投资规划中要确定最大风 险的最低限度等等。为此，对每个x R,我们先求诸目标值f i(X) 的最大值，然后再求这些最大值中的最小值。最大最小化问题的数学模型:minxmaxF ix :s tC ( X )乞 0c

40、eq ( x )二0Ax乞bAeqx 二beqlbx 岂ub求解最大最小化问题的函数为fminimax调用格式：x=fminimax(F,x0Jx=fminimax(F,x0,A,b) x=fminimax(F,x0,A,b,Aeq,beq) x=fminimax(F,x0,A,b,Aeq,beq,lb,ub) x=fminimax(F,x0,A,b,Aeq,beq,lb,ub,nonlcon) x=fminimax(F,x0,A,b,Aeq,beq,lb,ub,nonlcon,options) x=fminimax(F,x0,A,b,Aeq,beq,lb,ub,nonlcon,options

41、,P1,P2) x,fval=fminimax( )x,fval,maxfval=fminimax( ) x,fval,maxfval,exitflag,output=fminimax() x,fval,maxfval,exitflag,output,lambda=fminimax()说明：F为目标函数；x0为初值；A、b为线性不等式 约束的矩阵与向量；Aeq、beq为等式约束的矩阵与向量；lb、 ub为变量x的上、下界向量；nonIcon为定义非线性不等式 约束函数c(x)和等式约束函数ceq(x) ； options中设置优化参 数。x返回最优解；fval返回解x处的目标函数值；maxfv

42、al返回解x处的最大函数值；exitflag描述计算的退出条件； output返回包含优化信息的输出参数；lambda返回包含拉格朗日乘子的参数。例1求解下列最大最小值问题：min maxfi（x）, f2（x）, f3（x）, f4（x）f2（x）5XX2 - 4x22f3（x）二 Xi6X2712x1x< 20其中 f“（x）二 3x； 2x2 12x1 35f4（x） = 4xf + 9x；-首先编辑 M文件ff14.mfunction f=ff14(x)f(1)=3*x(1)八2+2*x(2)八2-12*x(1)+35; f(2)=5*x(1)*x(2)-4*x(2)+7; f(3)=x(1)A2+6*x(2); f(4)=4*x(1)A2+9*x(2)A2-12*x(1)*x(2)+20;