Main Content

Convert Quadratic Constraints to Second-Order Cone Constraints

Open Live Script

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

x T Q x + 2 q T x + c ≤ 0 .

Second-order cone programming has constraints of the form

‖ A s c ( i ) ⋅ x - b s c ( i ) ‖ ≤ d s c ( 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 = S T * S . You can compute S usingsqrtm. Suppose that there is a solution b to the equation S T b = – q , which is always true when Q is positive definite. Compute b usingb = -S\q.

x T Q x + 2 q T x + c = x T S T S x - 2 ( S T b ) T x + c = ( S x - b ) T ( S x - b ) - b T b + c = ‖ S x - b ‖ 2 + c - b T b .

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

  • A s c = S

  • b s c = b

  • d s c = 0

  • γ = - b T b - c

Numeric Example

Specify a five-element vectorfrepresenting the objective function f T x .

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

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

rngdefault% For reproducibilityQ = randn(5) + 3*eye(5); Q = (Q + Q')/2;% Make Q symmetricq = randn(5,1); c = -1;

To create the inputs forconeprog, create the matrixSas the square root ofQ.

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);

Callconeprogto 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 usingfmincon. Write the quadratic constraint as described inAnonymous Nonlinear Constraint Functions.

x0 = randn(5,1);% Initial point for fminconnlc = @(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