Quadratic Program Solver
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:
<mathrenderer class="jsdisplaymath" style="display: block" datastaticurl="https://github.githubassets.com/static" datarunid="8ae59d8c86da4fb759c24b169f5148bc">$$\begin{aligned} \arg \min_{\boldsymbol{x}} & \quad \frac{1}{2} {\left A \boldsymbol{x}  \boldsymbol{b} \right}_{2}^{2} \\ \text{subject to} & \quad B \boldsymbol{x} \leq \boldsymbol{c} \\ & \quad D \boldsymbol{x} = \boldsymbol{e} \end{aligned}$$</mathrenderer>
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:
<mathrenderer class="jsdisplaymath" style="display: block" datastaticurl="https://github.githubassets.com/static" datarunid="8ae59d8c86da4fb759c24b169f5148bc">$$\begin{aligned} \arg \min_{\boldsymbol{x}} & \quad \frac{1}{2} \boldsymbol{x}^{T} P \boldsymbol{x} + \boldsymbol{x}^{T} \boldsymbol{q} \\ \text{subject to} & \quad \boldsymbol{l} \leq A \boldsymbol{x} \leq \boldsymbol{u} \end{aligned}$$</mathrenderer>
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
 Check if making
paramRho
a matrix has a real benefit.  Implement the scaling procedure from the reference paper.
 Optimize the solution to the linear system (Is there anything better than
pcg()
for this structure? LSMR style?).  Better reporting.
 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.
Cite As
Royi Avital (2024). Quadratic Program Solver (https://github.com/RoyiAvital/QuadraticProgramSolver), GitHub. Retrieved .
MATLAB Release Compatibility
Platform Compatibility
Windows macOS LinuxTags
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!Discover Live Editor
Create scripts with code, output, and formatted text in a single executable document.
Versions that use the GitHub default branch cannot be downloaded
Version  Published  Release Notes  

1.0.0 
