qpswift / qpswift

qpSWIFT is a light-weight sparse quadratic programming solver

qpSWIFT

Light-weight sparse Quadratic Programming Solver

Introduction

qpSWIFT is light-weight sparse Quadratic Programming solver targetted for embedded and robotic applications. It employs Primal-Dual Interioir Point method with Mehrotra Predictor corrector step and Nesterov Todd scaling. For solving the linear system of equations, sparse LDL' factorization is used along with approximate minimum degree heuristic to minimize fill-in of the factorizations

Wiki

For more information, please check the repo wiki.

Problem Structure

qpSWIFT is designed to solve Quadratic Programs of the following form

+

Features

• Written in ANSI-C
• Fully functional Quadratic Programming solver for embedded applications
• Code Generation for target platform
• Tested on multiple target architectures
  • x86
  • x86_64
  • ARM
• Support for multiple interfaces
  • c/c++
  • python
  • matlab
  • simulink

Note

The project is still in active development. Feedback is highly appreciated. For any queries and suggestions please write to [email protected], [email protected] or [email protected]

Citing qpSWIFT

If you like qpSWIFT and are using it in your work, please cite the following paper
@article{pandala2019qpswift,
title = {qpSWIFT: A Real-Time Sparse Quadratic Program Solver for Robotic Applications},
author = {Pandala, Abhishek Goud and Ding, Yanran and Park, Hae-Won},
journal = {IEEE Robotics and Automation Letters},
volume = {4},
number = {4},
pages = {3355--3362},
year = {2019},
publisher = {IEEE}
}

qpswift's Issues

Warm Start Support

Thanks for your recent updates.
I have used your QP solver in my autonomous vehicle research and it performs well.
Is it possible to add warm start support because in many cases several feasible solution can be easily get, and this approach might possibly accelerate the solving process?

The solve efficiency of the C++ interface is lower than that of the matlab

In recent use, I found that the solve efficiency of the c++ interface is much lower than that of matlab. I did a comparative experiment with the open source RF_MPC, which is solved by matlab, and the c++ QP problem constructed in our project.In RF_MPC, I set the robot to take a trot gait and set the horizon to 10. Matlab spent 1.5ms to solve this QP problem with 240 variables, 240 inequality constrains, and 120 equality constrains. I constructed another QP problem with 180 variables, 120 inequality constrains, and 120 equality constrains in the C++ project. However, it takes more than 10ms for the computer to solve the QP problem. And occasionally the phenomenon of Maximum Iterations reached occurs during the solving process. What is the reason for this? I want to ask for your help. In addition, when qpSWIFT is called in a c++ project, the parameters are all used in Eigen form matrix. Could this be one of the reasons?

Quadratic programs with only equality constraints

Congratulations for qpSWIFT! 👏 It is a very promising solver.

I have started integrating it in qpsolvers and it compares favorably to the others: in the small benchmark from the README, it is the fastest solver on the small dense problem, second fastest on a sparse problem, and on a family of random problems its performance scales like this.

API-wise, the only point where it is not on-par with the other solvers is handling QPs with only equality constraints. I see that this is part of your future updates, and wanted to open an issue here to keep track of how this is going.

Max iter always reached on humanoid MPC problem

I'm comparing QP solvers on a classical humanoid model predictive control problem.

• Code: model_predictive_control.py.
• QP matrices it produces: humanoid_mpc_matrices.zip (names are for a call to qpSWIFT.run(q, h, P, G, opts=opts))
• qpSWIFT's output: qpSWIFT-output.txt

Other solvers handle this problem fine, but qpSWIFT always fails with exit code 2 (MAXITER reached).

The default setting for this parameter is 100 iterations. I have tried setting it to its allowed maximum of 199, but the solver still fails. If we look at the last iterations, primal and dual step sizes oscillate:

It: 168 || pcost : 1.153087e+03 || rx:7.793081e+00   ||  ry:0.000000e+00 ||  rz:1.414214e+03 || mu:2.652561e-47
      || Primal Step Size : 0.503682 || Dual Step Size   : 0.000000
...
It: 190 || pcost : 2.567155e+03 || rx:2.370485e+01   ||  ry:0.000000e+00 ||  rz:1.414214e+03 || mu:4.891264e-44
      || Primal Step Size : 0.000263 || Dual Step Size   : 0.000263
...
It: 198 || pcost : 2.632743e+03 || rx:2.229404e+01   ||  ry:0.000000e+00 ||  rz:1.414214e+03 || mu:3.183775e-57
      || Primal Step Size : 0.059123 || Dual Step Size   : 0.060551

So, it seems qpSWIFT does not converge on this problem? Maybe the default tolerance settings are too tight? 🤔

Solving Linear Programs using qpSWIFT

Hello,
Thanks for making your solver public. It is of great use in my research. I had a question regarding using qpSWIFT as a linear programming solver. For my application, I need to solve both an LP and a QP at real time rates. So I was thinking of using qpSWIFT as a common solver with the LP being solved by setting the P matrix to zero. Do you expect any efficiency shortcomings as a result? Thanks again!

pip install qpswift

This feature request to mention that there would be some downstream demand to be able to pip install qpswift in Python.

For instance, it would help with continuous integration of QP solvers, where qpSWIFT is currently one of the few solvers not covered:

Keep up the good work with qpSWIFT!

RELTOL is actually an absolute feasibility tolerance?

Judging from equation (21) in the paper, and the corresponding use I found in the code:

qpSWIFT/src/qpSWIFT.c

Lines 518 to 534 in dc70705

	/* Checks Exit condition if rx < ABSTOL rz < FEASTOl and s'z/m < 1e-6 */
	if (myQP->p)
	{
	if (myQP->stats->n_rx < myQP->options->reltol / sqrt(3.0) && myQP->stats->n_rz < myQP->options->reltol / sqrt(3.0) && myQP->stats->n_ry < myQP->options->reltol / sqrt(3.0) && myQP->stats->n_mu < myQP->options->abstol)
	{
	myQP->stats->Flag = QP_OPTIMAL;
	break;
	}
	}
	else
	{
	if (myQP->stats->n_rx < myQP->options->reltol / sqrt(3.0) && myQP->stats->n_rz < myQP->options->reltol / sqrt(3.0) && myQP->stats->n_mu < myQP->options->abstol)
	{
	myQP->stats->Flag = QP_OPTIMAL;
	break;
	}
	}

Isn't RELTOL rather an absolute feasibility tolerance parameter? 🤔

I'm asking this question as part of a note I'm writing on tolerance parameters in QP solvers. Feel free to check that the statements made there are accurate, all feedback welcome 🙂

sparse python interface

Let me start off by saying that your solver is great! I've tried a couple qp solvers for my motion planner project https://github.com/SemRoCo/giskardpy and qpSWIFT seems to be the fastest for my use case.

However, I currently have to waste a lot of computation time by having to work with dense matrices for qpSWIFT. It would be even faster if the python interface could accept scipy sparse matrices. In your readme you are saying that qpSWIFT is a sparse solver so I assume it should be possible?
Is such a feature planned?

Absolute tolerance check error in Python

It seems we cannot set "ABSTOL" from Python. Here is a small example:

import numpy as np
import qpSWIFT

M = np.array([[1.0, 2.0, 0.0], [-8.0, 3.0, 2.0], [0.0, 1.0, 1.0]])
P = np.dot(M.T, M)  # this is a positive definite matrix
q = np.dot(np.array([3.0, 2.0, 3.0]), M)
G = np.array([[1.0, 2.0, 1.0], [2.0, 0.0, 1.0], [-1.0, 2.0, -1.0]])
h = np.array([3.0, 2.0, -2.0])
x = qpSWIFT.run(q, h, P, G, opts={"ABSTOL": 1e-5})["sol"]

This example triggers a check error:

Traceback (most recent call last):
  File "quadratic_programming.py", line 33, in <module>
    x = qpSWIFT.run(q, h, P, G, opts={"ABSTOL": 1e-5})["sol"]
TypeError: absolute tolerance must be between 0 and 1, using the default value

The issue is of course that 1e-5 should be between 0 and 1. It does not appear with "RELTOL".

This issue was reported in qpsolvers/qpsolvers#64

simulink support

Thanks for your code. I used the S-function method to include the c codes however failed and I thought the main problem might be the lib file. I noticed you have added a /simulink interface so I am looking forward to your solution. Thanks again!