Second-order cone programming (SOCP)

The ALGLIB numerical library includes an efficient, large-scale dense and sparse SOCP solver available in C++, C#, Java and other languages. The solver implements numerous algorithmic improvements, is actively developed and has been extensively tested on various industrial optimization problems. ALGLIB is dual-licensed, with free and commercial editions.

This section focuses on the second-order cone programming capabilities of ALGLIB. However, our solver supports optimization problems beyond SOCP, including LP, QP/QCQP as well as more general conic problems.

SOCP solver overview

Features

GENIPM, ALGLIB's conic solver, is:

• Powerful and flexible: capable of solving problems that combine quadratic and conic terms, including nonconvex problems (in which case a local solution is returned). A second-order cone and a generalized power cone are supported.
• Efficient: utilizes state-of-the-art algorithms optimized for both sparse (SPARSE-GENIPM) and dense (DENSE-GENIPM) problems. It can handle large-scale problems with over a million variables, and operates with low overhead for small-scale tasks (100-1,000 variables).
• Robust: reliably handles degenerate cases and performs internal integrity checks during its operation.
• Self-contained: has no mandatory dependencies on external libraries and is ready to run out of the box.
• Free: the free version includes all features present in the commercial edition, along with exactly the same set of algorithmic improvements.

Programming languages supported

ALGLIB supports many programming languages, including C++, C#, Java, Python, and others:

• C++ version. Highly optimized, portable, self-contained library (x86/x64/ARM; works on Windows, Linux, and POSIX systems)
• C# version. Unified C# API for two backends: a fully managed C# implementation and a high-performance native computational core written in C
• Java, Python, and other languages. A wrapper for a high-performance native computational core written in C. Seamless integration with the target programming language

A distinctive feature of ALGLIB is that it provides the same API in all programming languages. This is achieved through our exclusive automatic code translation and wrapper generation technology.

Second-order cone programming

Standard problem formulation

The standard SOCP problem formulation is minimization of a linear objective subject to box, linear and non-overlapping second-order cone constraints:

This problem statement often appears in textbooks because it is easy to analyze and because it has nice primal-dual formulation. Despite its seeming simplicity, it allows to incorporate convex quadratic objectives and convex quadratic inequality constraints by reformulating them as second-order cone constraints. Thus, SOCP includes LP and convex QP/QCQP problem classes. However, it also supports nonlinearities beyond ones provided by QP/QCQP.

The standard SOCP problem is always convex, hence it always has a global solution that can be efficiently found using interior point methods.

Extended problem formulation

ALGLIB natively supports one of the most general and powerful formulations of a conic programming problem, extending the basic formulation above with quadratic terms and more flexible conic constraints:

A User Guide section about conic programming discusses general quadratic/conic formulation, including questions like various cone types support by ALGLIB and handling of non-convex problems. Here we focus on several important takeaways for a convex conically constrained case:

• Support for quadratic objective and constraints. Most conic solvers require the objective to be linear. While a convex quadratic objective or constraint can be reformulated as a second-order cone constraint (allowing a convex QCQP problem to be rewritten as a convex SOCP problem), this approach is cumbersome and potentially sparsity-breaking. GENIPM deals with quadratic terms directly, without reformulation.
• Support for overlapping cones. GENIPM allows variables to appear in multiple cones or multiple times in the same cone. In contrast, most open source conic solvers constrain cones to sequentially numbered variables, and do not permit cones to overlap. Support for overlapping cones allows us to work with more compact and expressive conic formulations.

Conic solver API

The QP/conic programming functionality is provided by the minqp subpackage of the Optimization package. The link above directs to the ALGLIB Reference Manual section, which includes a comprehensive description of the QP/conic solver API with detailed comments and examples.

This article is licensed for personal use only.