# Convert Quadratic Programming Problem to Second-Order Cone Program

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

$‖{A}_{sc}x-{b}_{sc}‖\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=\left(Ax{\right)}^{T}Ax=‖Ax{‖}^{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}}\left[\left(t+1/2\right)+{f}^{T}x\right]$`

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\\ ⋮\\ 0\end{array}\right]$`

`${\mathit{d}}_{\mathrm{sc}}=\left[\begin{array}{c}0\\ ⋮\\ 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}}\left[1/2+{f}_{sc}^{T}u\right]$`

where

$u\left(end\right)+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}‖Hx{‖}^{2}=\frac{1}{2}{u}^{T}{A}_{sc}^{2}u\le t+\frac{1}{2}$`

`$‖Hx{‖}^{2}\le 2t+1$`

`$‖Hx{‖}^{2}+{t}^{2}\le {t}^{2}+2t+1=\left(t+1{\right)}^{2}$`

`$\sqrt{‖Hx{‖}^{2}+{t}^{2}}\le |t+1|=±\left(t+1\right)$`

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

`$‖{A}_{sc}u‖\le ±\left(t-\gamma \right)$`

$‖{A}_{sc}u‖\le ±\left({d}_{sc}^{T}u-\gamma \right)$.

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. ```
```xqp = 3×1 1.0000 1.0000 1.0000 ```
```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 ```