二次 动态规划-图论.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
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 =
-

fval =
-
exitflag =
1
例2:求解:二次规划问题
min x12+2x22-2x1x2-4x1-12x2
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 =


fval =
-
exitflag =
1
练习1 求解下面二次规划问题

解:
则,,
在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 = %最优解


fval = %最优值
-
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]
>>
ans =


0
>>
ans =
0
0
说明第1、2个约束条件有效,其余无效。
练习2 求二次规划的最优解
max f (x1, x2)=x1x2+3
x1+x2-2=0
解:化成标准形式:
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 =


fval =
-
exitflag =
1
output