Quadratic programming

The ALGLIB numerical library encompasses an efficient, large-scale dense and sparse QP solver available in C++, C#, Java and other languages. The solver implements numerous algorithmic improvements, has long development history and was extensively tested on many industrial optimization problems. ALGLIB is dual-licensed, with free and commercial editions.

QP solver overview

Features

The ALGLIB QP solver is:

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

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.

Algorithms

The ALGLIB QP solver suite includes several quadratic programming algorithms designed to handle different types of QP problems:

• Interior point method, available in both dense (DENSE-IPM) and sparse (SPARSE-IPM) versions, is 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). It offers the best precision and performance, with its sparse version scaling beyond a million variables. It is the recommended option when solving semidefinite or strictly convex QP 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 problems: any mix of bounded, ranged, fixed or free variables with equality, inequality, or ranged linear constraints. An notable feature of the library is its efficient handling of difficult cases, such as two-sided (range) linear constraints, free variables and dense rows/columns. Unlike some solvers, ALGLIB QP solver incurs no additional performance penalties in such cases.

QP solver API

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.