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).
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\( {^m} {^x} {^n} \), \(1_{A} \), \(u_{A}\) \(^m\), \(c, 1_{x}, u_{x} \) \(^n\) are the problem data and 𝒦 = 𝒦\(^n{^1} \) ×⋯× 𝒦 \(^n{^r} \) × \({^n}{^1} \) where 𝒦 \(^n{^i} \) is either a second-order cone
or a rotated second-order cone
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 [1, 2, 3]. 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].
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].
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:
\(1_{1}\) – norm:
\(1_{2}\) – norm:
\(1_{∞}\) – norm:
The above norms can be viewed as special cases of general p-norm constraint on a vector \(x \) \(^n\) defined as
where \(p = 1 / m\) is a positive rational number with \( 1≥ 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].
The convex inequality
Where /(P∈𝒮^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
since \( (1/2) x^TPx ≤ t\) is equivalent to \( ||Fx|| _2^2 ≤ 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.
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 (x) \) and \(f_2 (x)\) are SOC-representable, then \(af_1 (x) (a ≥ 0), f_1 (x) + f_2 (x) \) and max {\(f_1 (x), f_2 (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.
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.
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 |
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.)
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.
NAG SOCP | SEDUMI | SDPT3 | NAG NLP (IPM) | |
Problems solved | 100% | 77.78% | 83.33 | 94.44% |
Table 2: Statistics on solvers’ status after run, percentage of successful solve attempts.
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.
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 |
Table 3: Indexing of problem ID in the test dataset
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. For further examples and reading visit our GitHub Local optimization page.