Second-order cone programming is a branch of convex optimization in which a linear function is minimized subject to linear constraints and the intersection of second-order (Lorentz or the ice cream) cones. In contrast to LP, second-order cones allow users to bring curvature information into the model to solve more complicated problems. The standard form of the SOCP problem is

where $A\in {ℝ}^{m\times n}$, $l_A,u_A\in {ℝ}^m$, $c,l_x,u_x\in {ℝ}^n$ are the problem data, and $\mathcal{K}={\mathcal{K}}^{n_1}\times \cdots \times {\mathcal{K}}^{n_r}\times {ℝ}^{n_l}$ where ${\mathcal{K}}^{n_i}$ is either a second-order cone

$${\mathcal{K}}_q^{n_i}:=\left\{x=\left(x_1,\dots ,x_{n_i}\right)\in {ℝ}^{n_i}:x_1^2\ge \sum _{j=2}^{n_i}{x}_j^2,x_1\ge 0\right\},$$

or a rotated second-order cone

$${\mathcal{K}}_r^{n_i}:=\left\{x=\left(x_1,\dots ,x_{n_i}\right)\in {ℝ}^{n_i}:2x_1{x}_2\ge \sum _{j=3}^{n_i}{x}_j^2,x_1\ge 0,x_2\ge 0\right\}.$$

It is rare that a second-order cone (SOC) would appear naturally in the model and is more frequent that a reformulation is needed. Here we show only the most common cases, for more examples see [5].

Optimization with norms

Several problems including data/parameter fitting will use norms in the objective function or as a constraint. Here we mention three cases that might appear frequently in models from various applications:

• $l_1$-norm: $${\parallel x\parallel }_1=\sum _{i=1}^n\left|x_i\right|\le t\iff \sum _{i=1}^n{s}_i\le t,\left(s_i,x_i\right)\in {\mathcal{K}}_q^2,i=1,\dots ,n.$$
• $l_2$-norm: $${\parallel x\parallel }_2=\sqrt{\sum _{i=1}^n{x}_i^2}\le t\iff \left(t,x\right)\in {\mathcal{K}}_q^{n+1}.$$
• $l_{\infty }$-norm: $${\parallel x\parallel }_{\infty }=max\left\{\left|x_i\right|:i=1,\dots ,n\right\}\le t\iff \left(t,x_i\right)\in {\mathcal{K}}_q^2,i=1,\dots ,n.$$

The above norms can be viewed as special cases of general p-norm constraint on a vector $x\in {ℝ}^n$ defined as

where $p=l∕m$ is a positive rational number with $l\ge m$. Inequality constraint (1) has SOC representation since they are equivalent to inequalities involving rational powers. Details on how to transform a general p-norm constraint can be found in [2].

Quadratic constraint

The convex inequality

where $P\in {\mathcal{S}}^n$ is a positive semidefinite matrix arises from applications such as portfolio optimization. Using routines handle_set_qconstr (e04rs) and handle_set_qconstr_fac (e04rt) introduced at Mark 27.1 of the NAG Library, users can easily define quadratic objective functions and/or constraints and seamlessly integrate them with other constraints. Then what will happen under the hood is as follows. Assume the matrix $P$ has factorization $P=F^{T}F$, (2) has an equivalent SOC representation as

$$t+q^{T}x+r=0,\left(t,1,Fx\right)\in {\mathcal{K}}_r^{n+2}$$

since $\left(1∕2\right)x^{T}Px\le t$ is equivalent to ${\parallel Fx\parallel }_2^2\le 2t$. Thus, adding auxiliary variables $y=Fx$ will transform the quadratic constraint into a standard cone constraint.

For more details, see our mini article on QCQP and the python examples on portfolio optimization involving quadratic functions.

Second-order cone representable functions

We have mentioned several important SOC-representable functions above. Many more functions and sets such as hyperbolic constraints, harmonic mean of positive affine functions, sum of quadratic/linear fractions, etc. are all SOC-representable [5]. In general, if functions $f_1\left(x\right)$ and $f_2\left(x\right)$ are SOC-representable, then $\alpha f_1\left(x\right)(\alpha \ge 0)$, $f_1\left(x\right)+f_2\left(x\right)$ and $max\{f_1\left(x\right),f_2\left(x\right)\}$ are also SOC-representable. We encourage users to exploit their models thoroughly to reach a SOC-equivalent problem, therefore make the most of the versatility and practical performance of the NAG SOCP solver nag_opt_handle_solve_socp_ipm.

In this section, we show the performance of NAG SOCP solver together with two state-of-the-art convex optimization solvers SEDUMI [3] and SDPT3 [6], which are general solvers for linear programming, second-order cone programming and semidefinite programming. We also solved the same models with a NAG general nonlinear programming (NLP) solver since SOCP can be viewed also as a general NLP problem. All four solvers were at default settings and the tests were run on a Windows laptop of 16GB memory and Intel Core i7-7500 2.7GHz CPU in single-threaded mode.

For SEDUMI and SDPT3, tests were run in MATLAB; since both solvers are written in MATLAB. For NAG solvers we used the NAG Library for Python to conduct the tests, however, the same solver is available in many other environments (C, Java, Fortran, etc.). The test data comes from 18 DIMACS problems that are widely used to test convex optimization solvers. The general statistics of the problems can be found in Table 1. The problem data is in SEDUMI format but can be easily transformed into SDPT3 and NAG input format.

As shown in Table 2, the NAG SOCP solver managed to solve all the problems to the required accuracy ($10^{-8}$) while other solvers failed on some of the test cases.

The computational time comparison can be found in Figure 2. We picked 11 problems that all four solvers solved successfully and Table 3 shows the problem ID and its corresponding problem name in the dataset. As shown in Figure 2, even general NLP solvers could solve SOCP in some cases, it is still recommended to use a specialized solver for SOCP to gain maximum performance.

In conclusion, SOCP is widely used in a broad range of applications due to its powerful nature. NAG introduces, at Mark 27, a new robust and efficient SOCP solver (e04pt) that should be considered for problems with intrinsic quadratic information. Certain reformulation is required, yet it is worth the effort. For further examples and reading visit our GitHub Local optimization page.