Quadratic Program Solver

バージョン 1.0.0 (26.7 KB) 作成者: Royi Avital
Solves a Quadratic Programming problem using Alternating Direction Method of Multipliers (ADMM). This is a MATLAB implementation of OSQP.

ダウンロード: 179

更新 2022/2/27

GitHub から

GitHub でライセンスを表示

Quadratic Program Solver

View Quadratic Program Solver on File Exchange

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


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


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().


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.


Royi Avital (2023). Quadratic Program Solver (https://github.com/RoyiAvital/QuadraticProgramSolver), GitHub. 取得済み .

MATLAB リリースの互換性
作成: R2021a
R2020b 以降のリリースと互換性あり
Windows macOS Linux
タグ タグを追加

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

GitHub の既定のブランチを使用するバージョンはダウンロードできません

バージョン 公開済み リリース ノート

この GitHub アドオンでの問題を表示または報告するには、GitHub リポジトリにアクセスしてください。
この GitHub アドオンでの問題を表示または報告するには、GitHub リポジトリにアクセスしてください。