Solving Convex Problems with 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:

\begin{array}{l} \underset{x \in ℝ^{n}}{minimize} & c^{T} x \\ subject to & l_{A} \leq A x \leq u_{A}, \\ l_{x} \leq x \leq u_{x}, \\ x \in K, \end{array}

where $A \in ℝ^{m \times n}$ $ {^m} {^x} {^n} $, $1_{A} $, $u_{A}$ $A \in ℝ^{m \times n}$ $^m$, $c, 1_{x}, u_{x} $ $A \in ℝ^{m \times n}$ $^n$ are the problem data and 𝒦 = 𝒦$^n{^1} $ ×⋯× 𝒦 $^n{^r} $ × $A \in ℝ^{m \times n}$ ${^n}{^1} $ where 𝒦 $^n{^i} $ is either a second-order cone

K_{q}^{n_{i}} : = {x = (x_{1}, \dots, x_{n_{i}}) \in ℝ^{n_{i}} : x_{1}^{2} \geq \sum_{j = 2}^{n_{i}} x_{j}^{2}, x_{1} \geq 0},

or a rotated second-order cone

K_{r}^{n_{i}} : = {x = (x_{1}, \dots, x_{n_{i}}) \in ℝ^{n_{i}} : 2 x_{1} x_{2} \geq \sum_{j = 3}^{n_{i}} x_{j}^{2}, x_{1} \geq 0, x_{2} \geq 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 [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].

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:

$1_{1}$ – norm:

{∥ x ∥}_{1} = \sum_{i = 1}^{n} | x_{i} | \leq t \Leftrightarrow \sum_{i = 1}^{n} s_{i} \leq t, (s_{i}, x_{i}) \in K_{q}^{2}, i = 1, \dots, n .

$1_{2}$ – norm:

{∥ x ∥}_{2} = \sqrt{\sum_{i = 1}^{n} x_{i}^{2}} \leq t \Leftrightarrow (t, x) \in K_{q}^{n + 1} .

$1_{∞}$ – norm:

{∥ x ∥}_{\infty} = max {| x_{i} | : i = 1, \dots, n} \leq t \Leftrightarrow (t, x_{i}) \in 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 $ $A \in ℝ^{m \times n}$ $^n$ defined as

{∥ x ∥}_{p} : = {(\sum_{i = 1}^{n} {| x_{i} |}^{p})}^{1 ∕ p} \leq t,

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].

Quadratic constraint

The convex inequality

\frac{1}{2} x^{T} P x + q^{T} x + r \leq 0

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

t + q^{T} x + r = 0, (t, 1, F x) \in K_{r}^{n + 2}

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.

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 (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.

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.

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 ( $1 0^{- 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.

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.

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