Second-order Cone Programming (SOCP)

Second-order cone programming (SOCP) offers a robust and efficient way of solving several types of convex problems, such as convex quadratically constrained quadratic programming (QCQP), robust linear programming (LP), parameter fitting and various norm-related optimization problems. That is the reason why it can be highly utilized in a broad range of fields including finance, engineering and control. NAG introduces a new SOCP solver, nag_opt_handle_solve_socp_ipm (e04pt), at Mark 27 of the NAG Library based on interior point method (IPM).

SOCP in the NAG Library Introduction

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

minimize xn cTx subject to lA Ax uA , lx x ux , xK ,

where A m×n , lA , uA m , c , l x , u x n are the problem data, and K = K n1 × × K nr × nl where K ni is either a second-order cone

K q ni := { x = x 1 , , x ni ni : x 1 2 j=2 ni x j 2 , x 1 0 } ,

or a rotated second-order cone

K r ni := { x = x 1 , , x ni ni : 2 x1 x2 j=3 ni x j 2 , x 1 0 , x 2 0 } .

As shown in Figure 1, the feasible region of an SOCP problem that has three variables is the intersection of the green polyhedron (corresponding to the linear inequality and bound constraints) and a cone. The curve represents the added quadratic information which makes SOCP more complicated, but at the same time more powerful than LP.

Second-order cone programming has been well researched since 1990s and the most popular methods to solve it may be the interior point methods (IPM) due to their theoretical polynomial complexity and practical performance. The main computational cost of IPM comes from solving a (potentially sparse) linear system for computing the Newton search direction. For more theoretical background and results, see [123]. NAG implements a path-following homogeneous self-dual algorithm that is both robust and efficient and can detect infeasibility and unboundedness of the model. Also, the solver exploits the sparsity pattern of the problem thoroughly which makes the solver efficient, especially on large and sparse problems. For more details on implementation, see the NAG Library routine documentation for NAG SOCP solver e04pt [4].

Reformulation Examples

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: x1 = i=1 n | x i | t i=1 n s i t , s i , xi Kq2,i = 1,,n.
  • l2-norm: x2 = i=1nxi2 t t,x Kqn+1.
  • l-norm: x = max{|xi| : i = 1,,n} t t,xi Kq2,i = 1,,n.

The above norms can be viewed as special cases of general p-norm constraint on a vector x n defined as

 
xp :=( i=1n|xi|p)1p t,
(1)
 

where p = lm is a positive rational number with l 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

 
1 2xTPx + qTx + r 0
(2)
 

where P Sn is a positive semidefinite matrix arises from applications such as portfolio optimization. Assume the matrix P has factorization P = FTF, (2) has an equivalent SOC representation as t + qTx + r = 0, t,1,Fx K rn+2

since (12)xTPx t is equivalent to Fx 2 2 2t. Thus, adding auxiliary variables y = Fx will transform the quadratic constraint into a standard cone constraint.

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 f1(x) and f2(x) are SOC-representable, then αf1(x)(α0), f1(x)+f2(x) and max { f1 (x) , f2 (x) } 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.

NAG Library SOCP Solver Performance

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.

Table 1: DIMACS problem statistics. 18 test problems in 4 classes. (n number of variables, m number of linear constraints, nc number of quadratic cone constraints.)
Prob. class No. of prob. Avg. n Avg. m Avg. nc
nb 4 3098.75 321 906
nql 3 86102 49440 12300
qssp 3 99486 49471 24871
sched 8 17712.5 8448.5 1.5

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.

Table 2: Statistics on solvers’ status after run, percentage of successful solve attempts.
  NAG SOCP SEDUMI SDPT3 NAG NLP (IPM)
Problems solved 100% 77.78% 83.33% 94.44%

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.

Table 3: Indexing of problem ID in the test dataset
Problem ID Problem name
1 nb
2 nb_L1
3 nql30
4 nql60
5 qssp30
6 qssp60
7 sched_100_100_scaled
8 sched_100_50_scaled
9 sched_200_100_scaled
10 sched_50_50_orig
11 sched_50_50_scaled
Figure 2
Figure 2: Execution time results
 

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.

References

[1]   F Alizadeh and SH Schmieta. Optimization with semidefinite, quadratic and linear constraints. In RUTCOR, RUTGERS UNIVERSITY. Citeseer, 1997.

[2]   Farid Alizadeh and Donald Goldfarb. Second-order cone programming. Mathematical programming, 95(1):3–51, 2003.

[3]   Jos F Sturm. Implementation of interior point methods for mixed semidefinite and second order cone optimization problems. Optimization Methods and Software, 17(6):1105–1154, 2002.

[4]   The NAG Library Manual, Mark 27 routine documentation for e04pt

[5]   Miguel Sousa Lobo, Lieven Vandenberghe, Stephen Boyd, and Hervé Lebret. Applications of second-order cone programming. Linear algebra and its applications, 284(1-3):193–228, 1998.

[6]   Kim-Chuan Toh, Michael J Todd, and Reha H Tütüncü. On the implementation and usage of sdpt3–a matlab software package for semidefinite-quadratic-linear programming, version 4.0. In Handbook on semidefinite, conic and polynomial optimization, pages 715–754. Springer, 2012.