将二次规划问题转换为二阶锥规划
此示例说明如何将半正定二次规划问题转换为 coneprog
求解器使用的二阶锥形式。二次规划问题的形式为
,
可能受到边界和线性约束的影响。coneprog
求解问题的形式为
使得
,
可能受到边界和线性约束的影响。
要将二次程序转换为 coneprog
形式,首先计算矩阵 的矩阵平方根。假设 是对称半正定矩阵,则命令
A = sqrtm(H);
返回一个半正定矩阵 A
,使得 A'*A = A*A = H
。因此,
.
将二次规划的形式修改如下:
其中 满足约束
.
将控制变量 扩展为 ,其中包括 作为其最后一个元素:
.
将二阶锥约束矩阵和向量扩展如下:
.
扩展向量 :
.
就新变量而言,二次规划问题变为
其中
.
通过以下计算,该二次约束变为锥约束,该计算使用了 、 和 的先前定义:
但是 。因此,回想一下 和 的定义,不等式就变成
.
二次规划具有与相应的锥规划相同的解。唯一的区别是在锥规划中添加了项 。
数值示例
quadprog
文档给出了此示例。
H = [1,-1,1 -1,2,-2 1,-2,4]; f = [-7;-12;-15]; lb = zeros(3,1); ub = ones(size(lb)); Aineq = [1,1,1]; bineq = 3; [xqp fqp] = quadprog(H,f,Aineq,bineq,[],[],lb,ub)
Minimum found that satisfies the constraints. Optimization completed because the objective function is non-decreasing in feasible directions, to within the value of the optimality tolerance, and constraints are satisfied to within the value of the constraint tolerance.
xqp = 3×1
1.0000
1.0000
1.0000
fqp = -32.5000
参考本示例开头的描述,指定二阶锥约束变量,然后调用 coneprog
函数。
Asc = sqrtm(H); Asc((end+1),(end+1)) = 1; d = [zeros(size(f(:)));1]; gamma = -1; b = zeros(size(d)); qp = secondordercone(Asc,b,d,gamma); Aq = Aineq; Aq(:,(end+1)) = 0; lb(end+1) = -Inf; ub(end+1) = Inf; [u,fval,eflag] = coneprog([f(:);1],qp,Aq,bineq,[],[],lb,ub)
Optimal solution found.
u = 4×1
1.0000
1.0000
1.0000
1.0000
fval = -33.0000
eflag = 1
锥体解 u
的前三个元素等于二次规划解 xqp
的元素,为了显示精度:
disp([xqp,u(1:(end-1))])
1.0000 1.0000 1.0000 1.0000 1.0000 1.0000
返回的二次函数值 fqp
在 为正数时为返回的锥体值减去 1/2,在 为负数时为返回的锥体值加上 1/2。
disp([fqp-sign(2*u(end)+1)*1/2 fval])
-33.0000 -33.0000
另请参阅
quadprog
| coneprog
| secondordercone