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.
258.0 次下载
更新时间 2022/2/27

Visitors

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

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.

引用格式

Royi Avital (2024). 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 默认分支的版本

版本 已发布 发行说明
1.0.0

要查看或报告此来自 GitHub 的附加功能中的问题,请访问其 GitHub 仓库
要查看或报告此来自 GitHub 的附加功能中的问题,请访问其 GitHub 仓库