Simple-Robotics / proxsuite

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

Improve dense backend and simplify calculus when using a Diagonal Hessian #239

Closed Bambade closed 1 year ago

Bambade commented 1 year ago

Adds a new backend (named PrimalLdl) for solving quicker QPs with far more constraints than primal variables (the current one is named PrimalDualLdl).

As a benchmark I get on randomly generated problems on my machine (11th Gen Intel(R) Core(TM) i7-11850H @ 2.50GHz):

dim: 100 n_eq: 200 n_in: 200 box: 100
timings QP PrimalLdl backend :  3.45787ms
timings QP PrimalDualLdl:       3.83495ms
timings QP Automatic :          3.2373ms
dim: 200 n_eq: 400 n_in: 400 box: 200
timings QP PrimalLdl backend :  18.2621ms
timings QP PrimalDualLdl:       24.4886ms
timings QP Automatic:           18.4161ms
dim: 300 n_eq: 600 n_in: 600 box: 300
timings QP PrimalLdl backend :  51.3537ms
timings QP PrimalDualLdl:   69.2859ms
timings QP Automatic:           51.7177ms
dim: 400 n_eq: 800 n_in: 800 box: 400
timings QP PrimalLdl backend :  113.751ms
timings QP PrimalDualLdl:   163.189ms
timings QP Automatic:           114.063ms
dim: 500 n_eq: 1000 n_in: 1000 box: 500
timings QP PrimalLdl backend :  237.171ms
timings QP PrimalDualLdl:   336.581ms
timings QP Automatic:           235.475ms

An automatic choice is proposed by default for dense QP constructors. It compares as an heuristic a typical complexity when using PrimalLdl or PrimalDualLdl backend and takes the cheaper choice.

Simplify as well Hessian vector computation when the Hessian appears to be diagonal.

As a benchmark one can get the following results on random problems:

dim: 100 n_eq: 50 n_in: 50 box: 100
timings QP with diagonal hessian feature :  2.67296ms
timings QP without diagonal hessian feature :   2.8467ms
dim: 200 n_eq: 100 n_in: 100 box: 200
timings QP with diagonal hessian feature :  20.2506ms
timings QP without diagonal hessian feature :   21.2964ms
dim: 300 n_eq: 150 n_in: 150 box: 300
timings QP with diagonal hessian feature :  52.7303ms
timings QP without diagonal hessian feature :   54.59ms
dim: 400 n_eq: 200 n_in: 200 box: 400
timings QP with diagonal hessian feature :  125.668ms
timings QP without diagonal hessian feature :   129.86ms
dim: 500 n_eq: 250 n_in: 250 box: 500

The modifications are unit tested in c++ and python and documented as well.