Simple-Robotics / proxsuite

The Advanced Proximal Optimization Toolbox
BSD 2-Clause "Simplified" License
414 stars 50 forks source link

Add box constraint interface for dense backend #238

Closed Bambade closed 1 year ago

Bambade commented 1 year ago

Add a specific feature for handling more efficiently box inequality constraints with ProxQP dense backend as suggested by #47 (i.e., all matrix vector operations are simplified).

The feature is documented on simple examples (and overloaded so that not to break current frontend API), and also unit tested in C++ and python.

A benchmark is added as well to compare the timings of using or not this feature on randomly generated problems On my machine (11th Gen Intel(R) Core(TM) i7-11850H @ 2.50GHz), I get for now:

Dense QP
dim: 100 n_eq: 50 n_in: 50 box: 100
timings QP with box constraints feature :   3.3986ms
timings QP without box constraints feature :    3.53994ms
dim: 200 n_eq: 100 n_in: 100 box: 200
timings QP with box constraints feature :   15.1796ms
timings QP without box constraints feature :    16.6479ms
dim: 300 n_eq: 150 n_in: 150 box: 300
timings QP with box constraints feature :   48.8814ms
timings QP without box constraints feature :    53.5706ms
dim: 400 n_eq: 200 n_in: 200 box: 400
timings QP with box constraints feature :   105.749ms
timings QP without box constraints feature :    115.168ms
dim: 500 n_eq: 250 n_in: 250 box: 500
timings QP with box constraints feature :   186.053ms
timings QP without box constraints feature :    198.098ms
dim: 600 n_eq: 300 n_in: 300 box: 600
timings QP with box constraints feature :   360.792ms
timings QP without box constraints feature :    379.857ms
dim: 700 n_eq: 350 n_in: 350 box: 700
timings QP with box constraints feature :   523.554ms
timings QP without box constraints feature :    563.047ms
dim: 800 n_eq: 400 n_in: 400 box: 800
timings QP with box constraints feature :   792.55ms
timings QP without box constraints feature :    868.172ms
dim: 900 n_eq: 450 n_in: 450 box: 900
timings QP with box constraints feature :   1126.91ms
timings QP without box constraints feature :    1241.98ms
dim: 1000 n_eq: 500 n_in: 500 box: 1000
timings QP with box constraints feature :   1587.73ms
timings QP without box constraints feature :    1730.66ms
jcarpent commented 1 year ago

In general, this feature helps to save 10% in computational timings, which might impact both small and large problems. Very nice work @Bambade !