Main Content

将二次规划问题转换为二阶锥规划

此示例说明如何将半正定二次规划问题转换为 coneprog 求解器使用的二阶锥形式。二次规划问题的形式为

minx12xTHx+fTx,

可能受到边界和线性约束的影响。coneprog 求解问题的形式为

minxfscTx

使得

Ascx-bscdscTx-γ,

可能受到边界和线性约束的影响。

要将二次程序转换为 coneprog 形式,首先计算矩阵 H 的矩阵平方根。假设 H 是对称半正定矩阵,则命令

A = sqrtm(H);

返回一个半正定矩阵 A,使得 A'*A = A*A = H。因此,

xTHx=xTATAx=(Ax)TAx=Ax2.

将二次规划的形式修改如下:

minx12xTHx+fTx=-12+minx,t[(t+1/2)+fTx]

其中 t 满足约束

t+1/212xTHx.

将控制变量 x 扩展为 u,其中包括 t 作为其最后一个元素:

u=[xt].

将二阶锥约束矩阵和向量扩展如下:

Asc=[A001]

bsc=[00]

dsc=[001]

γ=-1.

扩展向量 f

fsc=[f1].

就新变量而言,二次规划问题变为

minu12uTAsc2u+fscTu=-1/2+minu[1/2+fscTu]

其中

u(end)+1/212uTAscu.

通过以下计算,该二次约束变为锥约束,该计算使用了 Ascdscγ 的先前定义:

12Hx2=12uTAsc2ut+12

Hx22t+1

Hx2+t2t2+2t+1=(t+1)2

Hx2+t2|t+1|=±(t+1)

但是 Hx2+t2=Ascu2。因此,回想一下 γ=-1dsc 的定义,不等式就变成

Ascu±(t-γ)

Ascu±(dscTu-γ).

二次规划具有与相应的锥规划相同的解。唯一的区别是在锥规划中添加了项 -1/2

数值示例

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

返回的二次函数值 fqp2t+1 为正数时为返回的锥体值减去 1/2,在 2t+1 为负数时为返回的锥体值加上 1/2。

disp([fqp-sign(2*u(end)+1)*1/2 fval])
  -33.0000  -33.0000

另请参阅

| |

相关主题