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

打开实时脚本

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

$\min_{x} \frac{1}{2} x^{T} H x + f^{T} x$ ,

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

$\min_{x} f_{s c}^{T} x$

使得

$‖ A_{s c} x - b_{s c} ‖ \leq d_{s c}^{T} x - γ$ ,

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

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

A = sqrtm(H);

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

$x^{T} H x = x^{T} A^{T} A x = (A x)^{T} A x = ‖ A x ‖^{2}$ .

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

$\min_{x} \frac{1}{2} x^{T} H x + f^{T} x = - \frac{1}{2} + \min_{x, t} [(t + 1 / 2) + f^{T} x]$

其中 $t$ 满足约束

$t + 1 / 2 \geq \frac{1}{2} x^{T} H x$ .

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

$u = [\begin{array}{c} x \\ t \end{array}]$ .

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

$A_{sc} = [\begin{array}{c} A & 0 \\ 0 & 1 \end{array}]$

$b_{sc} = [\begin{array}{c} 0 \\ ⋮ \\ 0 \end{array}]$

$d_{sc} = [\begin{array}{c} 0 \\ ⋮ \\ 0 \\ 1 \end{array}]$

$γ = - 1$ .

扩展向量 $f$ ：

$f_{sc} = [\begin{array}{c} f \\ 1 \end{array}]$ .

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

$\min_{u} \frac{1}{2} u^{T} A_{s c}^{2} u + f_{s c}^{T} u = - 1 / 2 + \min_{u} [1 / 2 + f_{s c}^{T} u]$

其中

$u (e n d) + 1 / 2 \geq \frac{1}{2} u^{T} A_{s c} u$ .

通过以下计算，该二次约束变为锥约束，该计算使用了 $A_{s c}$ 、 $d_{s c}$ 和 $γ$ 的先前定义：

$\frac{1}{2} ‖ H x ‖^{2} = \frac{1}{2} u^{T} A_{s c}^{2} u \leq t + \frac{1}{2}$

$‖ H x ‖^{2} \leq 2 t + 1$

$‖ H x ‖^{2} + t^{2} \leq t^{2} + 2 t + 1 = (t + 1)^{2}$

$\sqrt{‖ H x ‖^{2} + t^{2}} \leq | t + 1 | = \pm (t + 1)$

但是 $‖ H x ‖^{2} + t^{2} = ‖ A_{s c} u ‖^{2}$ 。因此，回想一下 $γ = - 1$ 和 $d_{s c}$ 的定义，不等式就变成

$‖ A_{s c} u ‖ \leq \pm (t - γ)$

$‖ A_{s c} u ‖ \leq \pm (d_{s c}^{T} u - γ)$ .

二次规划具有与相应的锥规划相同的解。唯一的区别是在锥规划中添加了项 $- 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.

<stopping criteria details>

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.

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 在 $2 t + 1$ 为正数时为返回的锥体值减去 1/2，在 $2 t + 1$ 为负数时为返回的锥体值加上 1/2。

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

  -33.0000  -33.0000

另请参阅

quadprog | coneprog | secondordercone

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

数值示例

另请参阅

主题