ProxSuite is a collection of open-source, numerically robust, precise, and efficient numerical solvers (e.g., LPs, QPs, etc.) rooted in revisited primal-dual proximal algorithms. Through ProxSuite, we aim to offer the community scalable optimizers that deal with dense, sparse, or matrix-free problems. While the first targeted application is Robotics, ProxSuite can be used in other contexts without limits.

ProxSuite is actively developped and supported by the Willow and Sierra research groups, joint research teams between Inria, École Normale Supérieure de Paris and Centre National de la Recherche Scientifique localized in France.

ProxSuite is already integrated into: - CVXPY modeling language for convex optimization problems, - CasADi's symbolic framework for numerical optimization in general and optimal control. ProxQP is available in CasADi as a plugin to solve quadratic programs, - TSID: robotic software for efficient robot inverse dynamics with contacts and based on Pinocchio.

We are ready to integrate ProxSuite within other optimization ecosystems.

ProxSuite main features

Proxsuite is fast:

• C++ template library,
• cache-friendly.

Proxsuite is versatile, offering through a unified API advanced algorithms specialized for efficiently exploiting problem structures:

• dense, sparse, and matrix-free matrix factorization backends,
• advanced warm-starting options (e.g., equality-constrained initial guess, warm-start or cold-start options from previous results),

with dedicated features for - handling more efficiently box constraints, linear programs, QP with diagonal Hessian, or with far more constraints than primal variables, - solving nonconvex QPs, - solving batches of QPs in parallel, - solving the closest feasible QP if the QP appears to be primal infeasible, - differentiating feasible and infeasible QPs.

Proxsuite is flexible:

• header only,
• C++ 14/17/20 compliant,
• Python and Julia bindings for easy code prototyping without sacrificing performance.

Proxsuite is extensible. Proxsuite is reliable and extensively tested, showing the best performances on the hardest problems of the literature. Proxsuite is supported and tested on Windows, Mac OS X, Unix, and Linux.

Documentation

The online ProxSuite documentation of the last release is available here.

Getting started

ProxSuite is distributed to many well-known package managers.

Quick install with :

   pip install proxsuite

This approach is available on Linux, Windows and Mac OS X.

Quick install with :

   conda install proxsuite -c conda-forge

This approach is available on Linux, Windows and Mac OS X.

Quick install with :

   brew install proxsuite

This approach is available on Linux and Mac OS X.

Alternative approaches

Installation from source is presented here.

Compiling a first example program

For the fastest performance, use the following command to enable vectorization when compiling the simple example.

g++ -O3 -march=native -DNDEBUG -std=gnu++17 -DPROXSUITE_VECTORIZE examples/first_example_dense.cpp -o first_example_dense $(pkg-config --cflags proxsuite)

Using ProxSuite with CMake

If you want to use ProxSuite with CMake, the following tiny example should help you:

cmake_minimum_required(VERSION 3.10)

project(Example CXX)
find_package(proxsuite REQUIRED)
set(CMAKE_CXX_STANDARD 17) # set(CMAKE_CXX_STANDARD 14) will work too

add_executable(example example.cpp)
target_link_libraries(example PUBLIC proxsuite::proxsuite)

# Vectorization support via SIMDE and activated by the compilation options '-march=native' or `-mavx2 -mavx512f`
add_executable(example_with_full_vectorization_support example.cpp)
target_link_libraries(example_with_full_vectorization_support PUBLIC proxsuite::proxsuite-vectorized)
target_compile_options(example_with_full_vectorization_support PUBLIC "-march=native")

If you have compiled ProxSuite with the vectorization support, you might also use the CMake target proxsuite::proxsuite-vectorized to also link against SIMDE. Don't forget to use -march=native to get the best performance.

ProxQP

The ProxQP algorithm is a numerical optimization approach for solving quadratic programming problems of the form:

$$ \begin{align} \min_{x} & ~\frac{1}{2}x^{T}Hx+g^{T}x \ \text{s.t.} & ~A x = b \ & ~l \leq C x \leq u \end{align} $$

where $x \in \mathbb{R}^n$ is the optimization variable. The objective function is defined by a positive semidefinite matrix $H \in \mathcal{S}^n_+$ and a vector $g \in \mathbb{R}^n$. The linear constraints are defined by the equality-contraint matrix $A \in \mathbb{R}^{n_\text{eq} \times n}$ and the inequality-constraint matrix $C \in \mathbb{R}^{n_\text{in} \times n}$ and the vectors $b \in \mathbb{R}^{n_\text{eq}}$, $l \in \mathbb{R}^{n_\text{in}}$ and $u \in \mathbb{R}^{n_\text{in}}$ so that $b_i \in \mathbb{R},~ \forall i = 1,...,n_\text{eq}$ and $l_i \in \mathbb{R} \cup { -\infty }$ and $u_i \in \mathbb{R} \cup { +\infty }, ~\forall i = 1,...,n_\text{in}$.

Citing ProxQP

If you are using ProxQP for your work, we encourage you to cite the related paper.

Numerical benchmarks

The numerical benchmarks of ProxQP against other commercial and open-source solvers are available here.

For dense Convex Quadratic Programs with inequality and equality constraints, when asking for relatively high accuracy (e.g., 1e-6), one obtains the following results.

On the y-axis, you can see timings in seconds, and on the x-axis dimension wrt to the primal variable of the random Quadratic problems generated (the number of constraints of the generated problem is half the size of its primal dimension). For every dimension, the problem is generated over different seeds, and timings are obtained as averages over successive runs for the same problems. This chart shows for every benchmarked solver and random Quadratic program generated, barplot timings, including median (as a dot) and minimal and maximal values obtained (defining the amplitude of the bar). You can see that ProxQP is always below over solvers, which means it is the quickest for this test.

For hard problems from the Maros Meszaros testset, when asking for high accuracy (e.g., 1e-9), one obtains the results below.

The chart above reports the performance profiles of different solvers. It is classic for benchmarking solvers. Performance profiles correspond to the fraction of problems solved (on the y-axis) as a function of certain runtime (on the x-axis, measured in terms of a multiple of the runtime of the fastest solver for that problem). So the higher, the better. You can see that ProxQP solves the quickest over 60% of the problems (i.e., for $\tau=1$) and that for solving about 90% of the problems, it is at most 2 times slower than the fastest solvers solving these problems (i.e., for $\tau\approx2$).

Note: All these results have been obtained with a 11th Gen Intel(R) Core(TM) i7-11850H @ 2.50GHz CPU.

QPLayer

QPLayer enables to use a QP as a layer within standard learning architectures. More precisely, QPLayer differentiates over $\theta$ the primal and dual solutions of QP of the form

$$ \begin{align} \min_{x} & ~\frac{1}{2}x^{T}H(\theta)x+g(\theta)^{T}x \ \text{s.t.} & ~A(\theta) x = b(\theta) \ & ~l(\theta) \leq C(\theta) x \leq u(\theta) \end{align} $$

where $x \in \mathbb{R}^n$ is the optimization variable. The objective function is defined by a positive semidefinite matrix $H(\theta) \in \mathcal{S}^n_+$ and a vector $g(\theta) \in \mathbb{R}^n$. The linear constraints are defined by the equality-contraint matrix $A(\theta) \in \mathbb{R}^{n_\text{eq} \times n}$ and the inequality-constraint matrix $C(\theta) \in \mathbb{R}^{n_\text{in} \times n}$ and the vectors $b \in \mathbb{R}^{n_\text{eq}}$, $l(\theta) \in \mathbb{R}^{n_\text{in}}$ and $u(\theta) \in \mathbb{R}^{n_\text{in}}$ so that $b_i \in \mathbb{R},~ \forall i = 1,...,n_\text{eq}$ and $l_i \in \mathbb{R} \cup { -\infty }$ and $u_i \in \mathbb{R} \cup { +\infty }, ~\forall i = 1,...,n_\text{in}$.

QPLayer is able to learn more structured architectures. For example, $\theta$ can consists only in learning some elements of $A$ while letting $b$ fixed (see e.g., the example about how to include QPLayer into a learning pipeline). QPLayer can also differentiates over LPs. QPLayer allows for parallelized calculus over CPUs, and is interfaced with PyTorch.

Citing QPLayer

If you are using QPLayer for your work, we encourage you to cite the related paper.

Installation procedure

Please follow the installation procedure here.

Changelog

All notable changes to this project will be documented in this file.

The format is based on Keep a Changelog.

Unreleased

What's Changed

• Change from torch.Tensor to torch.empty or torch.tensor and specify type explicitly (#308)
• Fix handling of batch of inequality constraints in QPFunctionFn_infeas. The derivations in qplayer was done for single-sided constraints, that's the reason for the concatenation but the expansion of batchsize dimension was not working properly (#308)
• Switch from self-hosted runner for macos-14-ARM to runner from github (#306)

0.6.4 - 2024-03-01

What's Changed

• Changed primal_infeasibility_solving to False for feasible QPs (#302)

0.6.3 - 2024-01-23

Fixed

• Fix Python tests with scipy>=1.12 (#299)

0.6.2 - 2024-01-22

Fixed

• Fix Windows build (#290)
• Fix math formulae in documentation (#294)
• Restore correc values for infeasibility (#292)
• Handles CPU/GPU transfer in QPFunctionFn's backward function (#297)

0.6.1 - 2023-11-16

What's Changed

• [pre-commit.ci] pre-commit autoupdate by @pre-commit-ci (#280)
• Templating power iteration algorithm by matrix storage order by @quentinll (#279)

New Contributors

• @quentinll made their first contribution (#279)

0.6.0 - 2023-11-13

News

We add the implementation of QPLayer. QPLayer enables to use a QP as a layer within standard learning architectures. QPLayer allows for parallelized calculus over CPUs, and is interfaced with PyTorch. QPLayer can also differentiate over LPs.

What's Changed

• QPLayer: efficient differentiation of convex quadratic optimization by @fabinsch, @Bambade and @quentinll (#264)

0.5.1 - 2023-11-09

What's Changed

• [pre-commit.ci] pre-commit autoupdate by @pre-commit-ci (#265)
• [pre-commit.ci] pre-commit autoupdate by @pre-commit-ci (#268)
• [pre-commit.ci] pre-commit autoupdate by @pre-commit-ci (#269)
• Check model is_valid up to eps by @fabinsch (#272)

0.5.0 - 2023-09-26

This release adds support for nonconvex QPs, along with healthy fixes.

What's Changed

• Fix compilation (veg/memory) for gcc 7 and clang 7 by @costashatz (#255)
• Estimate minimal eigenvalue of quadratic cost hessian by @Bambade (#257)
• Fix typo #254 by @Bambade (#258)
• [pre-commit.ci] pre-commit autoupdate by @pre-commit-ci (#260)
• Sync submodule cmake by @jcarpent (#261)

New Contributors

• @costashatz made their first contribution (#255)

0.4.1 - 2023-08-02

What's Changed

• [pre-commit.ci] pre-commit autoupdate by @pre-commit-ci (#247)
• Add Iros on ROS CI by @jcarpent (#248)
• Update default value for update_preconditioner by @jcarpent (#250)

0.4.0 - 2023-07-10

What's Changed

• [pre-commit.ci] pre-commit autoupdate by @pre-commit-ci (#225)
• add generalized primal dual augmented Lagrangian (gpdal) for dense backend by @Bambade (#228)
• optimize dense iterative refinement by @Bambade (#230)
• Add dense LP interface by @Bambade (#231)
• Enable solving QP (#229)
• Add small dense LP Python example by @stephane-caron (#235)
• Fix typo (#234)
• ci check all jobs pass by @fabinsch (#236)
• [pre-commit.ci] pre-commit autoupdate by @pre-commit-ci (#232)
• Add box constraint interface for dense backend by @Bambade (#238)
• Improve dense backend and simplify calculus when using a Diagonal Hessian by @Bambade (#239)
• Add infeasibility solving feature for dense and sparse backends by @Bambade (#241)
• cmake: fix path to find-external/OpenMP by @fabinsch (#240)
• More information (#242)
• Fix warning and clean // solvers API by @jcarpent (#243)

0.3.7 - 2023-05-05

What's Changed

• [pre-commit.ci] pre-commit autoupdate by @pre-commit-ci (#206)
• Define PROXSUITE_AS_SUBPROJECT as ON by @amiller27 (#207)
• Sync submodule cmake by @jcarpent (#208)
• [pre-commit.ci] pre-commit autoupdate by @pre-commit-ci (#210)
• Set default CMAKE_BUILD_TYPE value by @jcarpent (#211)
• [pre-commit.ci] pre-commit autoupdate by @pre-commit-ci (#214)
• [pre-commit.ci] pre-commit autoupdate by @pre-commit-ci (#215)
• Set simde dependency for ROS2 Iron as well by @wxmerkt (#218)
• Sync submodule CMake by @jcarpent (#219)

New Contributors

• @amiller27 made their first contribution (#207)

0.3.6 - 2023-03-14

What's Changed

• ci/linux-wheels: fix naming for artifacts by @fabinsch (#198)
• pip wheels for aarch64 by @fabinsch (#202)

0.3.5 - 2023-03-06

What's Changed

• doc: pip install available on windows by @fabinsch (#189)
• set compute_timings = true by @fabinsch (#191)
• [minor] Clean up invalid link from pyproject.toml by @stephane-caron (#193)
• ci/linux: fix linux wheel compatibility by @fabinsch (#196)

0.3.4 - 2023-03-01

What's Changed

• CI: pip wheels on windows by @fabinsch (#185)
• [CI] ROS: Add friendly names; add TSID on Rolling as downstream test by @wxmerkt (#184)
• CI: simplify workflow on self-hosted M1 by @fabinsch (#187)

[0.3.3] - 2023-02-25

What's Changed

• [pre-commit.ci] pre-commit autoupdate by @pre-commit-ci (#172)
• [pre-commit.ci] pre-commit autoupdate by @pre-commit-ci (#174)
• cmake: add option BUILD_DOCUMENTATION by @fabinsch (#177)
• linalg/ldlt : mark p() and pt() permutation matrix getters const by @ManifoldFR (#180)
• feat: enable simde (#21)](https://github.com/wep21))) (#178)
• [CI] ROS: Activate prerelease by @wxmerkt (#181)

New Contributors

• @ManifoldFR made their first contribution (#180)
• @wep21 made their first contribution (#178)

0.3.2 - 2023-01-17

What's Changed

• Expose check_duality_gap (#167)
• Add duality-gap thresholds by @stephane-caron (#169)

New Contributors

• @stephane-caron made their first contribution (#167)

0.3.1 - 2023-01-09

What's Changed

• Fix package.xml and add ROS-CI by @wxmerkt (#158)
• ROS-CI: Debug and Release builds, fix warnings by @wxmerkt (#159)
• Fix computation of duality gap quantity by @jcarpent (#163)
• Sync submodule cmake by @jcarpent (#164)

New Contributors

• @wxmerkt made their first contribution (#158)

0.3.0 - 2022-12-26

What's Changed

• Add serialization of dense qp model using cereal by @fabinsch (#152)
• transposeInPlace only if eigen >= 3.4.0 by @fabinsch (#153)
• Fix Windows C++20 compatibility by @jcarpent (#155)

0.2.16 - 2022-12-21

What's Changed

• Fix default parameter values for compute_timings by @jcarpent (#146)
• [pre-commit.ci] pre-commit autoupdate by @pre-commit-ci (#147)
• Fix packaging issue on Windows by @jcarpent (#149)

0.2.15 - 2022-12-15

What's Changed

• cmake/python: update library output paths by @fabinsch (#144)

0.2.14 - 2022-12-14

What's Changed

• [pre-commit.ci] pre-commit autoupdate by @pre-commit-ci (#134)
• update benchmarks random mixed qp by @fabinsch (#137)
• [pre-commit.ci] pre-commit autoupdate by @pre-commit-ci (#138)
• add is_valid function for dense model and fix example + unittest by @fabinsch (#139)

0.2.13 - 2022-11-29

What's Changed

• Enforce check for other architectures by @jcarpent (#132)
• Fix support for POWERPC by @jcarpent (#133)

0.2.12 - 2022-11-26

What's Changed

• Fix compilation with mingw by @jgillis (#130)

New Contributors

• @jgillis made their first contribution (#130)

0.2.11 - 2022-11-25

What's Changed

• Fix dimension check issues by @jcarpent (#125)
• [pre-commit.ci] pre-commit autoupdate by @pre-commit-ci (#124)
• Add is_initialized safeguard to workspace by @fabinsch (#126)
• Add simple cpp example by @fabinsch (#127)

0.2.10 - 2022-11-17

What's Changed

• Allow macOS Debug pipeline to fail -> checking for memory alloc by @fabinsch (#117)
• Devel by @jcarpent (#118)
• fix instructionset import by @fabinsch (#120)

0.2.9 - 2022-11-14

What's Changed

• Enforce robustness computation of duality gap by @jcarpent (#114)
• Assert primal/dual residual and dual gap != nan + add unittest by @fabinsch (#115)

0.2.8 - 2022-11-12

What's Changed

• Enforce constness and clean CMake by @jcarpent (#106)
• Add details on using ProxSuite with CMake projects by @jcarpent (#111)
• Add duality gap measure by @Bambade (#110)

0.2.7 - 2022-11-10

What's Changed

• CMakeLists: fix INTERFACE target compile definitions by @fabinsch (#97)
• sync submodule by @fabinsch (#98)
• Fixed temporaries (#100)
• Additional option to check eigen runtime malloc by @fabinsch (#93)

New Contributors

• @fennel-labs made their first contribution (#100)

0.2.6 - 2022-11-08

What's Changed

• User option sparse backend by @fabinsch (#84)
• CI for c++14 compatibility by @fabinsch (#88)
• Update README.md by @fabinsch (#89)
• CI: use v1.2 also for windows, add cxx_std to key by @fabinsch (#90)
• Fix heap allocation (#92)

0.2.5 - 2022-11-06

What's Changed

• C++14 compliant implementation of optional by @fabinsch (#78)
• C++14 compliant implementation of aligned_alloc by @fabinsch (#79)
• unittest/sparse-ruiz: replace checks with isApprox by @fabinsch (#83)
• Fix packaging for pip by @jcarpent (#82)
• Move optional.hpp to the right place by @jcarpent (#81)
• Fix logic and bug (#85)

0.2.4 - 2022-11-01

What's Changed

• Change eps_abs to a reasonable value by @jcarpent (#70)
• sparse/solver: use refactorize for matrix free solver by @fabinsch (#73)
• Enhance API by @jcarpent (#71)
• Correct documentation of bindings by @fabinsch (#72)
• Add pipeline with MSVC compiler by @fabinsch (#49)

[0.2.3] - 2022-10-29

What's Changed

• Fix epsilon relative stopping criteria by @fabinsch (#58)
• Handle empty inputs by @fabinsch (#59)
• Fix calculation of objection function value by @fabinsch (#60)
• Doc: matio link by @fabinsch (#61)
• Fix packaging issue by @jcarpent (#64)
• Change default model upper and lower bounds by @Bambade (#66)
• Fix API for bounds on the inequality constraints by @jcarpent (#67)

0.2.2 - 2022-10-19

What's Changed

• release: wheels for macos arm64 by @fabinsch (#53)
• Don't compile AVX Python bindings on non X86_64 arch by @jcarpent (#54)
• Fix existence of std::aligned_alloc on APPLE by @jcarpent (#55)

0.2.1 - 2022-10-18

What's Changed

• [pre-commit.ci] pre-commit autoupdate by @pre-commit-ci (#43)
• Sync ma(#42)
• Fix compile options export for Windows by @jcarpent (#44)
• benchmark: document speed up by vectorization by @fabinsch (#48)
• Support ARM64 architecture by @fabinsch (#50)

0.2.0 - 2022-10-08

This release introduces a notable change (#) As the API is not yet totally fixed, we have only increased the minor release version.

More to come (#)

What's Changed

• CI/release: fix uploading proxsuite wheels only by @fabinsch (#30)
• TEST-AUTOMERGE by @fabinsch (#31)
• Fix c++ documentation by @fabinsch (#32)
• Compilation MSVC by @aescande (#33)
• Add specific compile option for MSVC by @jcarpent (#35)
• Sync submodule CMake by @jcarpent (#37)
• Remove sparse sparse overload for dense backend by @Bambade (#36)
• change qp.init(H,g,A,b,C,u,l) into qp.init(H,g,A,b,C,l,u) by @Bambade (#39)
• Fix packaging issues and remove useless test files by @jcarpent (#40)

New Contributors

• @aescande made their first contribution (#33)

0.1.2 - 2022-09-26

What's Changed

• Support python 3.7 for proxsuite wheels by @fabinsch (#27)
• Add default proximal step sizes by @Bambade (#26)
• Sync submodule cmake by @jcarpent (#28)

0.1.1 - 2022-09-09

What's Changed

• add missing includes by @nim65s (#21)
• update README and sync submodule by @Bambade (#20)
• Fix packaging issues by @jcarpent (#23)
• Fix preconditioner by @fabinsch (#24)
• [pre-commit.ci] pre-commit autoupdate by @pre-commit-ci (#25)
• Add more unittests by @fabinsch (#22)

New Contributors

• @nim65s made their first contribution (#21)
• @pre-commit-ci made their first contribution (#25)

0.1.0 - 2022-08-24

What's Changed

• Fix aligned alloc for old version of OSX target deployment by @jcarpent (#3)
• Fix documentation and the publishing pipeline by @jcarpent (#4)
• Bindings: expose qp solver output by @fabinsch (#11)
• provide initialization of solvers with None entries by @Bambade (#12)
• Fix packaging issues and add more packaging test by @jcarpent (#17)
• Use PROXSUITE_VECTORIZE and change logic by @jcarpent (#18)

New Contributors

• @jcarpent made their first contribution (#3)
• @fabinsch made their first contribution (#11)
• @Bambade made their first contribution (#12)

[0.0.1] - 2022-08-11

The first release of ProxSuite.