Second-Order Cone Optimization

Conic Optimization > LP | Overview | SOCP | SDP

Definitions
Examples

Definitions

Standard form

We say that a problem is a second-order cone optimization problem (SOCP) if it is a tractable conic optimization problem of the form (ref{eq:conic-pb-def-L6}), where the cone {cal K} is a product of second-order cones and possibly the non-negative orthant $mathbf{R}^n_+$ .

A standard form for the SOCP model is
min_x : c^Tx ~:~ Ax=b, ;; |C_ix+d_i|_2 le e_i^Tx + f_i, ;; i=1,ldots,m,
where we see that the variables (C_ix+d_i,e_i^Tx+f_i) should belong to a second-order cone of appropriate size. This corresponds to a convex problem in standard form, with the constraint functions f_i(x) = |C_ix+d_i|_2 - (e_i^Tx + f_i) .

SOCPs contain LPs as special cases, as seen from the standard form above, with C_i,d_i all zero.

Special case: convex quadratic optimization

Convex quadratic optimization (often written QP for short) corresponds to the convex optimization model
min_x : x^TQx + c^Tx ~:~ Cx le d, ;; Ax = b,
where Q = Q^T succeq 0 . Thus, QPs are extensions of LPs where a convex, quadratic term is added to the linear objective.

We can view QPs as special cases of SOCP: first, we express the problem in a way to make the objective linear:
$min_{x,t} : t + c^Tx ~:~ Cx le d, ;; Ax = b, ;; t ge x^TQx,$
then we observe that the last constraint can be expressed using a rotated second-order cone. Precisely, we have if and only if $(Q^{1/2}x,t,1) in {cal Q}_{rm rot}^n$ .

Quadratically constrained, convex quadratic optimization

QCQPs, as they are know by their acronym, correspond to problems of the form
min_x : q_0(x) ~:~ q_i(x) le 0, ;; i=1,ldots,m,
where the functions q_0,ldots,q_m are all convex and quadratic:
q_i(x) = x^TQ_ix+2p_i^Tx+r_i, ;; i=1,ldots,m,
with Q_i succeq 0 . Using rotated second-order cones, we can cast such problems as SOCPs.

Note that SOCPs cannot, in general, be cast as QCQPs. Consider a single SOC constraint of the form
|Cx+d|_2 le e^Tx+f.
One may be tempted to square the SCO constraints and obtain a quadratic constraint of the form
|Cx+d|_2^2 le (e^Tx+f)^2 , ;; e^Tx+f ge 0.
While the above constraints are equivalent to the original SOC constraint, the first is not convex.

Examples

Risk-return trade-off in portfolio optimizatio

Consider the problem of investing in assets, whose returns over one period (say, a month) are described as a random variable $y in mathbf{R}^n$ , with mean hat{y} and covariance matrix Sigma . A portfolio is described as a vector $x in mathbf{R}^n$ , with x_i the amount invested in asset (if no short-selling is allowed, we impose x ge 0 ; in general, we might impose that the portfolio vector belongs to a given polyhedron {cal P} ). The return of the portfolio is then x^Ty , and is a random variable with mean $x^That{y}$ and variance x^TSigma x . The problem introduced by Markowitz seeks to find a trade-off between the expected return and the risk (variance) of the portfolio:
$max_{x in {cal P}} : hat{y}^Tx - gamma x^T Sigma x,$
where gamma >0 is a ‘‘risk-aversion’’ parameter. The above is a QP (convex quadratic program), a special case of SOCP.

Robust half-space constraint

Consider a constraint on $x in mathbf{R}^n$ of the form a^Tx le b , with $a in mathbf{R}^n$ and b in mathbf{R} . Now assume that is only known to belong to an ellipsoid ${cal E} = { hat{a} + Ru ::: |u|_2 le 1}$ , with center $hat{a} in mathbf{R}^n$ and $R in mathbf{R}^{ntimes k}$ given. How can we guarantee that, irrespective of the choice of a in {cal E} , we still have a^Tx le b ?

The answer to this question hinges on the condition
$b ge max_{a in {cal E}} : a^Tx = hat{a}^Tx + max_{|u|_2 le 1} : x^TR u = hat{a}^Tx + |R^Tx|_2.$
The above constraint is a second-order cone constraint.

The robust feasible set associated to a linear optimization problem with row-wise spherical uncertainty on the coefficient matrix. The original feasible set is a polyhedron, with boundary shown in blue line. The robust feasible set is the intersection of robust half-space constraints, with boundaries shown as red dotted lines.

Robust linear programming

Consider a linear optimization problem of the form
min_x : c^Tx ~:~ a_i^Tx le b_i, ;; i=1,ldots,m.
In practice, the coefficient vectors a_i may not be known perfectly, as they are subject to noise. Assume that we only know that $a_i in {cal E}_i$ , where ${cal E}_i$ are given ellipsoids. In robust optimization, we seek to minimize the original objective, but we insist that each constraint be satisfied, irrespective of the choice of the corresponding vector $a_i in {cal E}_i$ . Based on the earlier result, we obtain the second-order cone optimization problem
$min_x : c^Tx ~:~ hat{a}_i^Tx + |R_i^Tx|_2 le b_i, ;; i=1,ldots,m,$
where ${cal E}_i = { hat{a}_i + R_iu ::: |u|_2 le 1}$ . In the above, we observe that the feasible set is smaller than the original one, due to the terms involving the l_2 -norms.

The figure above illustrates the kind of feasible set one obtains in a particular instance of the above problem, with spherical uncertainties (that is, all the ellipsoids are spheres, R_i = rho I for some rho >0 ). We observe that the robust feasible set is indeed contained in the original polyhedron.

Robust separation

We have discussed the problem of linear separation of two classes of points here. We revisit this example, assuming now that each point x_i , i=1,ldots,m , is only known to belong to an ellipsoid ${cal E}_i ={ hat{x}_i + R_iu ::: |u|_2 le 1}$ , where $hat{x}_i$ is the ‘‘nominal’’ value, and matrix R_i describes the ellipsoidal uncertainty around it. The condition for an hyperplane ${cal H}(w,b) = { x ::: w^Tx + b le 0 }$ , where $w in mathbf{R}^n$ , w ne 0 , and bin mathbf{R} , to separate the ellipsoids is
$forall : i=1,ldots,m, ;; forall : x in {cal E}_i ~:~ y_i(w^Tx_i + b) ge 0,$
which is equivalent to the second-order cone constraints
$w^That{x}_i +b ge |R_i^Tw|_2, ;; i=1,ldots,m.$
begin{figure}t begin{center} includegraphics= 00, height = 2.7in, width=3.5in{Figures/robl2svm.pdf} caption{label{fig:rob-sphere-svm-L6} A linear classifier that separates data points with maximal spherical uncertainty around them.} end{center} end{figure} Consider the special case when all the ellipsoids are spheres of given radius rho , that is, R_i = rho I , i=1,ldots,m . Now look for the hyperplane that is maximally robust, that is, tolerates the largest amount of uncertainty in the data points (as measured by rho ). Our problem writes
$max_{rho, w, b} : rho ~:~ w^That{x}_i +b ge rho |w|_2, ;; i=1,ldots,m.$
Since the constraints are homogeneous in (w,b) , we can without loss of generality impose rho |w|_2 = 1 . We then formulate the above problem as the LP
$min_{w,b} : |w|_2 ~:~ w^That{x}_i +b ge 1, ;; i=1,ldots,m.$
The quantity rho = 1/|w^ast|_2 is called the margin of the optimal classifier, and gives the largest amount of spherical uncertainty the data points can tolerate before they become not separable.