qpSWIFT is a light-weight sparse quadratic programming solver

Overview

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

Problem Structure

qpSWIFT is designed to solve Quadratic Programs of the following form
min. 0.5*x'Px + c'x
s.t Ax = b
Gx <= h

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

Future Updates

  • Quadratic Program with only equality constraints

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

Comments
  • Absolute tolerance check error in Python

    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 https://github.com/stephane-caron/qpsolvers/issues/64

    opened by stephane-caron 2
  • The solve efficiency of the C++ interface is lower than that of the matlab

    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? matlab solve C++QProblem dense_form_solve_time sparse_form_solve_time

    opened by sucrozzg 2
  • Warm Start Support

    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?

    opened by feiyuxiaoThu 1
  • simulink support

    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!

    opened by feiyuxiaoThu 1
  • RELTOL is actually an absolute feasibility tolerance?

    RELTOL is actually an absolute feasibility tolerance?

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

    https://github.com/qpSWIFT/qpSWIFT/blob/dc707056cb069a4b355ea406eb2ad28589a7fb11/src/qpSWIFT.c#L518-L534

    Isn't RELTOL rather an absolute feasibility tolerance parameter? :thinking:

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

    opened by stephane-caron 0
  • - Initial fixes so compiles under C++ compilers

    - Initial fixes so compiles under C++ compilers

    Some quick mods needed to get the runqpcpp.cpp demo file to compile with a C++ compiler (g++ 10.2.0).

    Still generates litteral suffix warnings, which I didn't bother looking too much into. Just set the -Wno-literal-suffix flag to silence them.

    opened by rmaia3d 0
  • pip install qpswift

    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:

    image

    Keep up the good work with qpSWIFT!

    opened by stephane-caron 0
  • Max iter always reached on humanoid MPC problem

    Max iter always reached on humanoid MPC problem

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

    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? :thinking:

    opened by stephane-caron 5
  • Quadratic programs with only equality constraints

    Quadratic programs with only equality constraints

    Congratulations for qpSWIFT! :clap: 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.

    opened by stephane-caron 1
Releases(v0.0.2)
Owner
qpSWIFT
A repository to host qpSWIFT quadratic programming sovler
qpSWIFT
a lean linear math library, aimed at graphics programming. Supports vec3, vec4, mat4x4 and quaternions

linmath.h -- A small library for linear math as required for computer graphics linmath.h provides the most used types required for programming compute

datenwolf 717 Nov 23, 2022
Seidel's Algorithm: Linear-Complexity Linear Programming for Small-Dimensional Variables

SDLP Seidel's Algorithm: Linear-Complexity Linear Programming (LP) for Small-Dimensions About This solver is super efficient for small-dimensional LP

ZJU FAST Lab 42 Dec 1, 2022
The ROS version of ICP Mapping with QPEP Solver (Quadratic Pose Estimation Problems)

The ROS version of ICP Mapping with QPEP Solver (Quadratic Pose Estimation Problems) The project is based on https://github.com/ethz-asl/ethzasl_icp_m

Jin Wu 11 Nov 2, 2022
Harsh Badwaik 1 Dec 19, 2021
The dgSPARSE Library (Deep Graph Sparse Library) is a high performance library for sparse kernel acceleration on GPUs based on CUDA.

dgSPARSE Library Introdution The dgSPARSE Library (Deep Graph Sparse Library) is a high performance library for sparse kernel acceleration on GPUs bas

dgSPARSE 58 Nov 7, 2022
Lee Thomason 298 Nov 16, 2022
nanomsg-next-generation -- light-weight brokerless messaging

nng - nanomsg-next-gen ℹ️ If you are looking for the legacy version of nanomsg, please see the nanomsg repository. This project is a rewrite of the Sc

nanomsg 3k Nov 29, 2022
pugixml is a Light-weight, simple and fast XML parser for C++ with XPath support

pugixml is a C++ XML processing library, which consists of a DOM-like interface with rich traversal/modification capabilities, an extremely fast XML parser which constructs the DOM tree from an XML file/buffer, and an XPath 1.0 implementation for complex data-driven tree queries. Full Unicode support is also available, with Unicode interface variants and conversions between different Unicode encodings (which happen automatically during parsing/saving).

Arseny Kapoulkine 3.2k Nov 28, 2022
Poseidon OS (POS) is a light-weight storage OS

Poseidon OS Poseidon OS (POS) is a light-weight storage OS that offers the best performance and valuable features over storage network. POS exploits t

null 51 Nov 21, 2022
A light-weight Flutter Engine Embedder based on HADK ,which for Android devices that runs without any java code

flutter-hadk A light-weight Flutter Engine Embedder based on HADK ,which for Android devices that runs without any java code 1.Build by android-ndk-to

null 12 Jun 15, 2022
Light-weight UNIX backdoor

JadedWraith Lightweight UNIX backdoor for ethical hacking. Useful for red team engagements and CTFs. Something I wrote a few years ago as part of a ga

null 128 Aug 24, 2022
Analytics In Real-time (AIR) is a light-weight system profiling tool

Analytics In Real-time Analytics In Real-time (AIR) is a light-weight system profiling tool that provides a set of APIs for profiling performance, lat

null 2 Mar 3, 2022
Ducktape is an Open source Light weight 2d Game Engine that gives utmost priority to user convenience.

Ducktape is an Open source Light weight 2d Game Engine that gives utmost priority to user convenience. It is written in c++ and uses SFML and Box2d for graphics and physics respectively.

Ducktape 98 Nov 17, 2022
A light-weight music Discord bot using Orca.

What's the "Music Discord bot with C"? A light-weight music Discord bot using Orca for it's bot. It's easy to use and install. How to download and use

ThePedro 11 Nov 24, 2022
A very simple and light-weight drawing app made with qt and C++.

Blackboard A very simple and light-weight drawing app made with qt and C++. It supports tablet and pen pressure with the help of QTabletEvents. So you

null 1 Nov 15, 2021
Fast and Light-weight path smoothing methods for vehicles

path_smoother About Fast and Light-weight path smoothing methods for vehicles Denpendencies This project has been tested on Ubuntu 18.04. sudo apt-get

MingwangZhao 4 Dec 1, 2021
Simple, Fast, Light weight

Welcome To PradoshOS Github! Index Main heading Setup Step 1 Step 2 Step 3 Step 4 Compilation of Bootloader Compilation of Kernel Compilation of Userl

S Pradosh 11 Nov 12, 2022
A light-weight json parser.

pson pson is a lightweight parser and it support six type, null , bool, number, string, array, object, and it can parse the encoding of UTF-8. It's fa

pinK 17 Dec 1, 2022