apozharski/piqp

An Proximal Interior Point Quadratic Programming solver

PIQP

PIQP is a Proximal Interior Point Quadratic Programming solver, which can solve dense and sparse quadratic programs of the form

$$ \begin{aligned} \min_{x} \quad & \frac{1}{2} x^\top P x + c^\top x \\ \text {s.t.}\quad & Ax=b, \\ & Gx \leq h, \\ & x_{lb} \leq x \leq x_{ub}, \end{aligned} $$

Combining an infeasible interior point method with the proximal method of multipliers, the algorithm can handle ill-conditioned convex QP problems without the need for linear independence of the constraints.

Features

• PIQP is written in header only C++ 14 leveraging the Eigen library for vectorized linear algebra.
• Dense and sparse problem formulations are supported. For small dense problems, vectorized instructions and cache locality can be exploited more efficiently.
• Interface to Python with many more to follow.
• Allocation free problem updates and re-solves.
• Open source under the BSD 2-Clause License.

Interfaces

PIQP support a wide range of interfaces including

• C/C++ (with Eigen support)
• Python
• Matlab
• R
• Julia (soon)
• Rust (soon)

Credits

PIQP is developed by the following people:

• Roland Schwan (main developer)
• Yuning Jiang (methods and maths)
• Daniel Kuhn (methods and maths)
• Colin N. Jones (methods and maths)

All contributors are affiliated with the Laboratoire d'Automatique and/or the Risk Analytics and Optimization Chair at EPFL, Switzerland.

This work was supported by the Swiss National Science Foundation under the NCCR Automation (grant agreement 51NF40_180545).

PIQP is an adapted implementation of work by Spyridon Pougkakiotis and Jacek Gondzio, and is built on the following open-source libraries:

• Eigen: It's the work horse under the hood, responsible for producing optimized numerical linear algebra code.
• ProxSuite: The code structure (folder/namespace structure, etc.), some utility functions/helper macros, and the instruction set optimized python bindings are based on ProxSuite.
• SuiteSparse - LDL (modified version): Used for solving linear systems in the sparse solver.
• pybind11: Used for generating the python bindings.
• cpu_features: Used for run-time instruction set detection in the interface bindings.
• OSQP: The C and Matlab interface is inspired by OSQP.
• Clarabel: Parts of the iterative refinement scheme are inspired by Clarabel's implementation.

Citing our Work

If you found PIQP useful in your scientific work, we encourage you to cite our accompanying paper:

@INPROCEEDINGS{schwan2023piqp,
  author={Schwan, Roland and Jiang, Yuning and Kuhn, Daniel and Jones, Colin N.},
  booktitle={2023 62nd IEEE Conference on Decision and Control (CDC)}, 
  title={{PIQP}: A Proximal Interior-Point Quadratic Programming Solver}, 
  year={2023},
  volume={},
  number={},
  pages={1088-1093},
  doi={10.1109/CDC49753.2023.10383915}
}

The benchmarks are available in the following repo: piqp_benchmarks

License

PIQP is licensed under the BSD 2-Clause License.