Standard Forms of SOCP

SOCP > SOC inequalities | Standard forms | Group sparsity | Applications

Second-order cone programs: standard forms
Quadratically constrained quadratic programming

Second-order cone programs: standard forms

Inequality form

A second-order cone program (or SOCP, for short) is an optimization problem of the form

displaystylemin_x : c^Tx ~:~ |A_i x + b_i |_2 le c_i^Tx + d_i, ;; i=1,ldots, m ,

where $A_i in mathbf{R}^{p_i times n}$ 's are given matrices, $b_i in mathbf{R}^p_i$ , $c_i in mathbf{R}^n$ vectors, and d_i 's scalars.

The problem is convex, since the constraint functions of the corresponding standard form

f_i(x) = |A_i x + b_i |_2 - (c_i^Tx + d_i), ;; i=1,ldots,m,

are.

Examples:

Conic form

We can put the above problem in the so-called ‘‘conic’’ format

$displaystylemin_x : c^Tx ~:~ (A_i x + b_i,c_i^Tx + d_i) in mathbf{K}_{p_i}, ;; i=1,ldots, m .$

Since the cones $mathbf{K}_{p_i}$ are convex, and the mappings x rightarrow (A_i x + b_i,c_i^Tx + d_i) are affine, the feasible set is convex.

Rotated second-order cone constraints

Since the rotated second-order cone can be expressed as some linear transformation of an ordinary second-order cone, we can include rotated second-order cone constraints, as well as ordinary linear inequalities or equalities, in the formulation. This allows to formulate LPs and QPs as special cases of SOCP.

Examples:

Quadratic program as SOCP.
Logarithmic Chebyschev approximation

Quadratically constrained quadratic programming

Definition

A quadratically constrained quadratic programming (QCQP for short) is a problem of the form

displaystylemin_x : a_0^Tx + x^TQ_0x ~:~ x^TQ_ix + a_i^Tx le b_i, ;; i=1,ldots, m ,

where Q_i succeq 0 , i=1,ldots,m . This condition ensures that the problem is convex. QCQPs contain LPs and QPs as special case.

Examples:

SOCP formulation

We can formulate QCQPs as SOCPs, by introducing new variables and affine equality constraints. (Proof).