Quadratic Program Solver

Solves a Quadratic Programming problem using Alternating Direction Method of Multipliers (ADMM). This is a MATLAB implementation of OSQP.

Quadratic Program Solver

Solves a Quadratic Programming problem using Alternating Direction Method of Multipliers (ADMM).
This is a MATLAB implementation of the paper - OSQP: An Operator Splitting Solver for Quadratic Programs.

Remark: Any Quadratic Program Solver can solve Constrained Least Squares problem as well (With linear and convex constraints).

Motivation

I needed for some Signal / Image Processing projects a solver of a problem of the form:

<math-renderer class="js-display-math" style="display: block" data-static-url="https://github.githubassets.com/static" data-run-id="8ae59d8c86da4fb759c24b169f5148bc">$$\begin{aligned} \arg \min_{\boldsymbol{x}} &amp; \quad \frac{1}{2} {\left| A \boldsymbol{x} - \boldsymbol{b} \right|}_{2}^{2} \\ \text{subject to} &amp; \quad B \boldsymbol{x} \leq \boldsymbol{c} \\ &amp; \quad D \boldsymbol{x} = \boldsymbol{e} \end{aligned}$$</math-renderer>

I could use MATLAB's quadprog() or lsqlin() yet both are part of the Optimization Toolbox which isn't widely accessible.
When I learned about ADMM, Projection and Optimization in general I played with some implementations for this problem but they were pretty slow and sensitive to parameters.
When OSQP became available it showed those problem can be solved.
It requires compiling and even defining GCC as the compiler on Windows which isn't easy to everyone.
Hence I thought it would be nice to replicate the paper (As the C code is way beyond me) in MATLAB.
Within few hours I had a first working code though without all the features (See To Do).

The goal is to have a viable alternative to MATLAB's quadprog().
While in most cases quadprog() will be faster choice, this implementation should be good enough and free solution.

Implementation in High Level Language might assist with faster integration of better optimization and flexibility (For instance, supporting non sparse matrices).

The Code

The solver is implemented in the function SolveQuadraticProgram().
It uses MATLAB's argument block and requires MATLAB R2020b (Ver 9.9) to the least.
Users of previous MATLAB versions might try remove this block (Be careful about the parameters).

The function solves the following form of Quadratic Program:

<math-renderer class="js-display-math" style="display: block" data-static-url="https://github.githubassets.com/static" data-run-id="8ae59d8c86da4fb759c24b169f5148bc">$$\begin{aligned} \arg \min_{\boldsymbol{x}} &amp; \quad \frac{1}{2} \boldsymbol{x}^{T} P \boldsymbol{x} + \boldsymbol{x}^{T} \boldsymbol{q} \\ \text{subject to} &amp; \quad \boldsymbol{l} \leq A \boldsymbol{x} \leq \boldsymbol{u} \end{aligned}$$</math-renderer>

Where $ P \in \mathbb{S}_{+}^{n} $ (A symmetric positive semi definite matrix).

Documentation

In Progress...

Look inside the function SolveQuadProgram() and see the reference paper.

Unit Test

The unit tests implemented in SolveQuadraticProgramUnitTest.m.
The script requires CVX and Optimization Toolbox.
It basically generates a problem and verify the solution of SolveQuadraticProgram() vs. the other 2 references.

To Do

1. Check if making paramRho a matrix has a real benefit.
2. Implement the scaling procedure from the reference paper.
3. Optimize the solution to the linear system (Is there anything better than pcg() for this structure? LSMR style?).
4. Better reporting.
5. Implement last step as Projected Gradient Descent in order to be strictly feasible.

Julia Code

The project implements the method in Julia Language as well (The .jl files).
The goal is to have a Julia package on its own. But it will happen only once performance will be in parity with the C code.
Julia has the potential to have even better performance than MATLAB's quadprog().

Reference

The code is an implementation of the paper Stellato, B. and Banjac, G. and Goulart, P. and Bemporad, A. and Boyd, S. - {OSQP}: An Operator Splitting Solver for Quadratic Programs.
This is a really great paper as the writers gave all the little details to create a truly competitive solver with ADMM.
Their work is really amazing.