Convert Quadratic Programming Problem to Second-Order Cone Program

Open Live Script

This example show how to convert a positive semidefinite quadratic programming problem to the second-order cone form used by the coneprog solver. A quadratic programming problem has the form

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

possibly subject to bounds and linear constraints. coneprog solves problems in the form

$\min_{x} f^{T} x$

such that

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

possibly subject to bounds and linear constraints.

To convert a quadratic program to coneprog form, first calculate the matrix square root of the matrix $H$ . Assuming that $H$ is a symmetric positive semidefinite matrix, the command

A = sqrtm(H);

returns a positive semidefinite matrix A such that A'*A = A*A = H. Therefore,

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

Modify the form of the quadratic program as follows:

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

where $t$ satisfies the constraint

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

Extend the control variable $x$ to $u$ , which includes $t$ as its last element:

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

Extend the second-order cone constraint matrices and vectors as follows:

$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$ .

Extend the coefficient vector $f$ as well:

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

In terms of the new variables, the quadratic programming problem becomes

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

where

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

This quadratic constraint becomes a cone constraint through the following calculation, which uses the earlier definitions of $A_{s c}$ , $d_{s c}$ , and $γ$ :

$\frac{1}{2} u^{T} A_{s c} u = \frac{1}{2} ‖ H x ‖^{2} \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)$

$‖ u ‖ \leq \pm (t - γ)$

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

The quadratic program has the same solution as the corresponding cone program. The only difference is the added term $- 1 / 2$ in the cone program.

Numerical Example

The quadprog documentation gives this example.

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.

fqp = -32.5000

Referring to the description at the beginning of this example, specify the second-order cone constraint variables, and then call the coneprog function.

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

The first three elements of the cone solution u are equal to the elements of the quadratic programming solution xqp, to display precision:

disp([xqp,u(1:(end-1))])

    1.0000    1.0000
    1.0000    1.0000
    1.0000    1.0000

The returned quadratic function value fqp is the returned cone value minus 1/2 when $2 t + 1$ is positive, or plus 1/2 when $2 t + 1$ is negative.

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

  -33.0000  -33.0000

Documentation

Convert Quadratic Programming Problem to Second-Order Cone Program

Numerical Example

See Also

Related Topics

Optimization Toolbox Documentation

Support