## 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:

$$\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}$$

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:

$$\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}$$

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 (2022). Quadratic Program Solver (https://github.com/RoyiAvital/QuadraticProgramSolver), GitHub. Retrieved .

##### MATLAB Release Compatibility

##### Platform Compatibility

Windows macOS Linux##### Tags

### 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.

__GitHub Repository__.

__GitHub Repository__.