Main Content

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

$$\underset{x}{\mathrm{min}}\frac{1}{2}{x}^{T}Hx+{f}^{T}x$$,

possibly subject to bounds and linear constraints. `coneprog`

solves problems in the form

$$\underset{x}{\mathrm{min}}{f}_{sc}^{T}x$$

such that

$$\Vert {A}_{sc}x-{b}_{sc}\Vert \le {d}_{sc}^{T}x-\gamma $$,

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}Hx={x}^{T}{A}^{T}Ax=(Ax{)}^{T}Ax=\Vert Ax{\Vert}^{2}$$.

Modify the form of the quadratic program as follows:

$$\underset{x}{\mathrm{min}}\frac{1}{2}{x}^{T}Hx+{f}^{T}x=-\frac{1}{2}+\underset{x,t}{\mathrm{min}}[(t+1/2)+{f}^{T}x]$$

where $$t$$ satisfies the constraint

$$t+1/2\ge \frac{1}{2}{x}^{T}Hx$$.

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

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

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

$${\mathit{A}}_{\mathrm{sc}}=\left[\begin{array}{cc}\mathit{A}& 0\\ 0& 1\end{array}\right]$$

$${\mathit{b}}_{\mathrm{sc}}=\left[\begin{array}{c}0\\ \vdots \\ 0\end{array}\right]$$

$${\mathit{d}}_{\mathrm{sc}}=\left[\begin{array}{c}0\\ \vdots \\ 0\\ 1\end{array}\right]$$

$\gamma =-1$.

Extend the coefficient vector $$f$$ as well:

${\mathit{f}}_{\mathrm{sc}}=\left[\begin{array}{c}\mathit{f}\\ 1\end{array}\right]$.

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

$$\underset{u}{\mathrm{min}}\frac{1}{2}{u}^{T}{A}_{sc}^{2}u+{f}_{sc}^{T}u=-1/2+\underset{u}{\mathrm{min}}[1/2+{f}_{sc}^{T}u]$$

where

$$u(end)+1/2\ge \frac{1}{2}{u}^{T}{A}_{sc}u$$.

This quadratic constraint becomes a cone constraint through the following calculation, which uses the earlier definitions of $${A}_{sc}$$, $${d}_{sc}$$, and $$\gamma $$:

$$\frac{1}{2}\Vert Hx{\Vert}^{2}=\frac{1}{2}{u}^{T}{A}_{sc}^{2}u\le t+\frac{1}{2}$$

$$\Vert Hx{\Vert}^{2}\le 2t+1$$

$$\Vert Hx{\Vert}^{2}+{t}^{2}\le {t}^{2}+2t+1=(t+1{)}^{2}$$

$$\sqrt{\Vert Hx{\Vert}^{2}+{t}^{2}}\le |t+1|=\pm (t+1)$$

But $$\Vert Hx{\Vert}^{2}+{t}^{2}=\Vert {A}_{sc}u{\Vert}^{2}$$. So, recalling that $$\gamma =-1$$ and the definition of $${d}_{sc}$$, the inequality becomes

$$\Vert {A}_{sc}u\Vert \le \pm (t-\gamma )$$

$$\Vert {A}_{sc}u\Vert \le \pm ({d}_{sc}^{T}u-\gamma )$$.

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.

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.

`xqp = `*3×1*
1
1
1

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.

`u = `*4×1*
1.0000
1.0000
1.0000
1.0000

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 $$2t+1$$ is positive, or plus 1/2 when $$2t+1$$ is negative.

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

-33.0000 -33.0000

`quadprog`

| `coneprog`

| `secondordercone`