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, including convex quadratically constrained quadratic programming (QCQP) problems. That is the reason why it can be highly utilized in a broad range of fields, like finance. At Mark 29.3 of the NAG Library, NAG introduces a performance update to the SOCP solver (nag_opt_handle_solve_socp_ipm) which has been shown to be particularly effective for portfolio optimization.

1. SOCP in the NAG Library Introduction

Second-order cone programming is one of the main methods for solving QCQP problems, which arises in applications such as portfolio construction. The standard form convex QCQP problem is:

\begin{matrix} \underset{x \in ℝ^{n}}{minimize} & \frac{1}{2} x^{T} Q_{0} x + r_{0}^{T} x \\ subject to & \frac{1}{2} x^{T} Q_{i} x + r_{i}^{T} x + s_{i} \leq 0 for i = 1, \dots, m, \\ Ax = b, \end{matrix}

where $Q_{o},…, Q_{m} $ are positive semidefinite $n$ x $n$ matrices.

Figure 1: Feasible region of an SOCP problem with three variables. The feasible region of an SOCP problem (which may, for instance, be a transformed QCQP problem) can be seen in Figure 1. The feasible region here is the intersection of the green polyhedron and a cone. The curve represents the added quadratic information which makes SOCP more complicated, but at the same time more powerful than LP. In terms of the implementation of NAG’s SOCP solver, a path-following homogeneous self-dual algorithm is used. This is both robust and efficient and can detect infeasibility and unboundedness of the model. Also, NAG 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 nag_opt_handle_solve_socp_ipm [1].

2. Usage of SOCP in Portfolio Optimization

It is rare that a second-order cone (SOC) would appear naturally in the model, yet through a model reformulation, many portfolio optimization problems and constraints can be handled by SOCP. We discuss several of these below, for more examples see [2].

2.1 Optimization with norms

The leverage constraint:

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

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

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

(1)

Where $p = l / m $ is a positive rational number with $ l ≥ m $. Inequality constraints (1) have SOC representation since they are equivalent to inequalities involving rational powers.

2.2 Quadratic constraint

The tracking error constraint

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

(2)

where $P$ ∈ $S^n$ is a positive semidefinite matrix is common in 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^TF $, (2) has an equivalent SOC representation as

t + q^{T} x + r = 0, (t, 1, Fx) \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.

2.3 More second-order cone representable functions

We have mentioned important SOC-representable functions above yet many more problems and constraints from portfolio optimization are SOC-representable. We list some below.

Maximize Sharpe ratio:

\max \frac{μ^{T} x}{\sqrt{x^{T} Σ x}} .

Holding and budget constraints:

0 \leq x \leq u, e^{T} x = b,

where $e$ is the vector of all ones.

Maximum position constraint:

\max | x | \leq m .

Market impact cost:

w^{T} | x - x_{0} |^{η} \leq u_{M} .

We encourage users to exploit their models thoroughly to reach a SOC-equivalent problem, thereby making the most of the versatility and practical performance of the NAG SOCP solver nag_opt_handle_solve_socp_ipm.

3. Performance of NAG SOCP solver

In this section, we show the performance of the NAG SOCP solver from the NAG Library for Python together with the NAG SOCP solver called from CVXPY and the default solver in CVXPY. While we used Python, the same NAG SOCP solver is available in many other environments (C, Java, Fortran, etc.). All solvers were at default settings with accuracy at $1 0^{- 8}$ and in single-threaded mode.

The solvers were used on $10$ classic portfolio optimization problems ranging from 1100 to 2900 assets. Randomly generated data was used in a Markowitz model whose objective involved a large covariance matrix and was subject to a long-only constraint and a budget constraint.

The computational time comparison can be found in Figure 2. Here it can be seen that the NAG solver called from CVXPY is faster than the standard CVXPY solver. Further, for smaller problems, the NAG solver called from Python is at least twice as fast as standard CVXPY, becoming as much as five times faster for larger problems.

Figure 2: Comparison of time on $10$ portfolio optimization problems.

In conclusion, SOCP is widely used in finance due to its powerful nature. At Mark 29.3, NAG introduces an updated SOCP solver (nag_opt_handle_solve_socp_ipm) that is highly performant on portfolio optimization problems. In some cases, reformulation of your problem is required, yet it is worth the effort. For further examples and reading visit our GitHub Local optimization page.

The solver is available for multiple languages and environments including C and C++, Python, Java, .NET and Fortran, on Windows, Linux and MacOS. See the Getting Started page for how to download and install.

References

[1] The NAG Library Manual, Mark 29.3 routine documentation for e04pt. https://support.nag.com/numeric/nl/nagdoc_latest/flhtml/e04/e04ptf.html.

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