二次_动态规划-图论.doc

§1 二次规划模型 数学模型： 其中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,x0) X= quadprog(H,f,A,b,Aeq,beq,lb,ub,x0,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： min f(x)= x1-3x2+3x12+4x22-2x1x2 s.t 2x1+x2≤2 -x1+4x2≤3 程序： f=[1;-3]; H=[6 -2;-2 8]; A=[2 1;-1 4]; b=[2;3]; [X,fval,exitflag]=quadprog(H,f,A,b) 结果： X = -0.0455 0.3636 fval = -0.5682 exitflag = 1 例2： min x12+2x22-2x1x2-4x1-12x2 s.t x1+x2≤2 -x1+2x2≤2 2x1+x2≤3 0≤x1, 0≤x2 程序： H=[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.6667 1.3333 fval = -16.4444 exitflag = 1 练习1 求解下面二次规划问题 sub.to 解： 则，， 在MATLAB中实现如下： H = [1 -1; -1 2] ; f = [-2; -6]; 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.6667 1.3333 fval = %最优值 -8.2222 exitflag = %收敛 1 output = iterations: 3 algorithm: medium-scale: active-set firstorderopt: [ ] cgiterations: [ ] lambda = lower: [2x1 double] upper: [2x1 double] eqlin: [0x1 double] ineqlin: [3x1 double] lambda.ineqlin ans = 3.1111 0.4444 0 lambda.lower ans = 0 0 说明 第1、2个约束条件有效，其余无效。 练习2 求二次规划的最优解 max f (x1, x2)=x1x2+3 sub.to x1+x2-2=0 解：化成标准形式： sub.to x1+x2=2 在Matlab中实现如下： H=[0,-1;-1,0]; f=[0;0]; Aeq=[1 1]; beq=2; [x,fval,exitflag,output,lambda] = quadprog(H,f,[ ],[ ],Aeq,beq) 结果为： x = 1.0000