Main Content

Convert Quadratic Constraints to Second-Order Cone Constraints

This example shows how to convert a quadratic constraint to the second-order cone constraint form. A quadratic constraint has the form

xTQx+2qTx+c0.

Second-order cone programming has constraints of the form

Asc(i)x-bsc(i)dsc(i)x-γ(i).

The matrix Q must be symmetric and positive semidefinite for you to convert quadratic constraints. Let S be the square root of Q, meaning Q=S*S=ST*S. You can compute S using sqrtm. Suppose that there is a solution b to the equation STb=q, which is always true when Q is positive definite. Compute b using b = -S\q.

xTQx+2qTx+c=xTSTSx-2(STb)Tx+c=(Sx-b)T(Sx-b)-bTb+c=Sx-b2+c-bTb.

Therefore, if bTb>c, then the quadratic constraint is equivalent to the second-order cone constraint with

  • Asc=S

  • bsc=b

  • dsc=0

  • γ=-bTb-c

Numeric Example

Specify a five-element vector f representing the objective function fTx.

f = [1;-2;3;-4;5];

Set the quadratic constraint matrix Q as a 5-by-5 random positive definite matrix. Set q as a random 5-element vector, and take the additive constant c=-1.

rng default % For reproducibility
Q = randn(5) + 3*eye(5);
Q = (Q + Q')/2; % Make Q symmetric
q = randn(5,1);
c = -1;

To create the inputs for coneprog, create the matrix S as the square root of Q.

S = sqrtm(Q);

Create the remaining inputs for the second-order cone constraint as specified in the first part of this example.

b = -S\q;
d = zeros(size(b));
gamma = -sqrt(b'*b-c);
sc = secondordercone(S,b,d,gamma);

Call coneprog to solve the problem.

[x,fval] = coneprog(f,sc)
Optimal solution found.
x = 5×1

   -0.7194
    0.2669
   -0.6309
    0.2543
   -0.0904

fval = -4.6148

Compare this result to the result returned by solving this same problem using fmincon. Write the quadratic constraint as described in Anonymous Nonlinear Constraint Functions.

x0 = randn(5,1); % Initial point for fmincon
nlc = @(x)x'*Q*x + 2*q'*x + c;
nlcon = @(x)deal(nlc(x),[]);
[xfmc,fvalfmc] = fmincon(@(x)f'*x,x0,[],[],[],[],[],[],nlcon)
Local 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.
xfmc = 5×1

   -0.7196
    0.2672
   -0.6312
    0.2541
   -0.0902

fvalfmc = -4.6148

The two solutions are nearly identical.

See Also

| |

Related Topics