Convex/non-convex QP and QCQP solver
The ALGLIB numerical library features an efficient, large-scale dense and sparse QP/QCQP/SOCP/conic solver available in C++, C#, Java and other languages.
The solver implements numerous algorithmic improvements, has long development history and was extensively tested on various industrial optimization problems.
ALGLIB is dual-licensed, with free and commercial editions.
This section covers the quadratic programming and quadratically constrained quadratic programming capabilities of ALGLIB.
Additional details on its conic programming capabilities can be found in the separate section.
The ALGLIB QP solver is:
-
Powerful.
The solver is capable of solving QP and QCQP problems, including nonconvex problems with equality/range quadratic constraints
(in the latter case, a local solution is returned).
The solver also has powerful conic programming capabilities.
-
Efficient.
The solver utilizes the best algorithms suitable for both sparse and dense problems.
It can handle large-scale problems with over a million variables, and also has low overhead for small-scale tasks (100-1,000 variables).
-
Robust.
The solver reliably handles degenerate cases and performs internal integrity checks during its operation.
-
Self-contained.
The solver 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.
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.
The ALGLIB QP solver suite includes several quadratic programming algorithms:
-
General convex/non-convex interior point method, available in both dense (DENSE-GENIPM) and sparse (SPARSE-GENIPM) versions,
is designed for quadratic programming (QP) and quadratically constrained (QCQP) problems, as well as conic programming problems.
This solver is the most powerful and actively developed solver in the ALGLIB quadratic/conic optimization suite.
It offers the best precision and performance, with its sparse version scaling beyond a million variables.
The dense version can efficiently handle small and medium-scale dense problems, avoiding the overhead of maintaining sparse data structures.
Starting from ALGLIB 4.04, this solver is the recommended choice for solving QP or QCQP problems.
-
Basic interior point method, available in both dense (DENSE-IPM) and sparse (SPARSE-IPM) versions,
is an early incarnation of the interior point method intended for convex quadratic programming problems.
This includes QP problems with positive definite matrices, semidefinite problems, as well as problems with a zero quadratic term (i.e. LP problems).
-
Augmented Lagrangian QP solver is intended for medium-sized (up to a thousand variables) nonconvex quadratic programming problems.
For problems with multiple local extrema, it converges to a local solution.
-
QuickQP is a specialized QP solver for small-scale (up to several hundred variables) nonconvex dense QP problems with box constraints only.
For problems with multiple local extrema, it also converges to a local solution.
ALGLIB supports the most general formulation of quadratic programming (QP) and quadratically constrained quadratic programming (QCQP) problems:
any mix of bounded, fixed or free variables with equality, inequality, or ranged linear/quadratic constraints.
Having one of the bounds (L, U, etc) at infinity indicates that the corresponding bound is absent,
while setting the lower and upper bounds equal means an equality constraint.
Depending on the problem properties, the following cases can arise:
-
Linear programming (LP). A=0, Nq=0 (no quadratic terms).
ALGLIB efficiently solves LP problems using the interior point solver even when these problems are posed as quadratic ones with zero quadratic terms.
A globally optimal solution can be reliably and quickly found.
-
Convex quadratic programming (QP). A⪰0 (positive semidefinite objective), Nq=0 (no quadratic constraints).
Similarly to LP, a globally optimal solution can be easily found.
-
Convex quadratically constrained quadratic programming (QCQP). A⪰0 (positive semidefinite objective),
Qi⪰0 and QL,i=-∞ (positive semidefinite quadratic constraints with no lower bound).
Again, a globally optimal solution can be found.
-
Non-convex QP/QCQP problem that has only one local minimum.
If any of the convexity conditions above are violated, the problem becomes non-convex.
However, certain non-convex problems may still have an unique local minimum that is also the global minimum.
For instance, the problem can be effectively convexified under constraints or minor non-convexities may exist without introducing multiple extrema.
In such scenarios, the solver converges slightly slower than in the convex case but can still find the global solution.
-
Non-convex QP/QCQP problem with multiple local extrema.
In such cases, the solver converges to a random local solution.
The latter case (non-convex QCQP problems) also includes smooth QCQP problems that are effectively mixed-integer
due to quadratic constraints enforcing integrality of variables.
E.g., the constraint x2=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 quadratic 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.
The quadratic 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 solver API with detailed comments and examples.
