Conic solver (SOCP and beyond)

The ALGLIB numerical library includes an efficient, large-scale dense and sparse conic solver available in C++, C#, Java and other languages, capable of solving LP/QP/QCQP problems with additional conic constraints. 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 conic programming capabilities of ALGLIB. While it is also applicable to purely quadratic problems (QP and QCQP), a separate section on QP/QCQP provides more focused discussion.

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

Conic programming

Problem formulation

ALGLIB supports one of the most general and powerful formulations of a conic programming problem:

Let's break down this definition for clarity:

• Quadratic objective. GENIPM solver naturally supports quadratic objectives with both semidefinite and indefinite Q₀. Nonconvex problems are solved to local optimality.
• Box constraints. Having one/both bounds at infinity means that the corresponding bound is absent. It is better to specify infinite bounds than assigning large positive or negative values. The solver will be able to deal with big finite values, but will take somewhat longer to converge.
• Linear constraints. The two-sided constraint formulation provides significant flexibility, making it possible to specify linear equality, inequality and range constraints.
• Quadratic constraints. A unique feature of the GENIPM solver, that rarely appears in other conic solvers, is its ability to combine conic constraints with quadratic inequality/equality/range ones. It can also handle non-convex quadratic constraints (again, the problem is solved to local optimality).
• Conic constraints. The last line in the constraints list means that a subset of variables (with possible repetitions), multiplied by the scaling matrix and with shifts being added, is restricted to lie in a cone (a list of supported cone types is given below).

Cone types supported

As of ALGLIB 4.04, GENIPM supports the following cone types:

• Second-order cone, i.e. cone of the form .
• Generalized power cone, i.e. cone of the form .

Strictly speaking, a generalized power cone with ∑α_i<1 is not a cone, as it is not closed under positive scalar multiplication. For the definition to hold, ∑α_i=1 is required. However, constraints with ∑α_i<1 often appear in practice, with slack variables being used to make α sum to one. From the performance point of view, it is better to natively support such combinations in the GENIPM solver.

Differences from other conic solvers

The GENIPM quadratic/conic solver has several features that distinguish it from other conic solvers:

• 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.
• Support for non-convex problems. GENIPM can solve problems with non-convex objectives (Q₀ is indefinite) or non-convex quadratic constraints to local optimality. While the solver generally converges more slowly in the non-convex case compared to the convex case, it can still find a solution.

Dealing with nonconvexity

A convex optimization problem is one with convex objective and convex constraints. Convexity is an important property because it ensures that any local solution is also the global solution and that it can be efficiently found using interior point method. Conic programming is closely tied to convexity, as cones are convex by definition, and are designed to introduce structured nonlinearities into the convex optimization framework.

A problem becomes non-convex if its objective is non-convex (Q₀ is indefinite) or if it includes non-convex constraints. A convex quadratic constraint is defined as one with Q_i⪰0 and Q_L,i=-∞ (a positive semidefinite quadratic term without a lower bound). Any deviation from this rule introduces non-convexity. For instance, x²-y²≤1 is non-convex because the quadratic term is indefinite. What is interesting is that x²+y²≥1 is also non-convex as well as x²+y²=1.

Non-convexity is often associated with multiple extrema and NP-hardness. However, some non-convex problems may still have an unique local minimum that is also the global minimum. For example, the problem can be effectively convexified under constraints or minor non-convexities may exist without introducing multiple extrema. Thus, one can greatly benefit from being able to use conic constraints in a non-convex optimization framework.

An important caveat is that non-convex optimization also includes smooth problems that are effectively mixed-integer due to quadratic constraints enforcing integrality of variables. E.g., the constraint x²=1 restricts x to {-1,+1}, dividing the feasible set into disjoint regions. The GENIPM solver is not intended for such problems because it needs a smooth connected feasible set to explore. A specialized mixed integer solver should be used in such cases.

Some solvers address the challenge of mixed-integer tasks pretending to be smooth ones by prohibiting any non-convexity in the problem formulation. This approach allows them to focus on delivering reliable solutions to convex problems. At ALGLIB we take a different approach, prioritizing the provision of the most versatile and powerful solver, even if this occasionally results in its misuse.

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.