Quadratic programming in python

Saved searches

Use saved searches to filter your results more quickly

You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window. Reload to refresh your session.

quadratic-programming

Here are 23 public repositories matching this topic.

locuslab / qpth

A fast and differentiable QP solver for PyTorch.

qpsolvers / qpsolvers

Quadratic programming solvers in Python with a unified API

osqp / osqp-python

Python interface for OSQP

osqp / osqp_benchmarks

QP Benchmarks for the OSQP Solver against GUROBI, MOSEK, ECOS and qpOASES

qpsolvers / qpsolvers_benchmark

Benchmark for quadratic programming solvers available in Python

tachukao / idoc

Implicit Differentiable Optimal Control (IDOC) with JAX

KarrLab / conv_opt

Python package for linear and quadratic programming

wyqsnddd / pyQpController

pyQpController is the proof of concept simulator attached to the paper: Impact-Friendly Robust Control Design with Task-Space Quadratic Optimization. Examples are provided to brew your own multi-objective robot controllers in python.

dmeoli / optiml

Optimizers for/and sklearn compatible Machine Learning models

xEnVrE / QP-toy-problems

A set of toy problems solved using QP programming

lanl-ansi / bqpjson

Utilities for working with bqpjson data

Источник

qpsolvers 3.4.0

Quadratic programming solvers in Python with a unified API.

Навигация

Ссылки проекта

Статистика

Метаданные

Лицензия: GNU Lesser General Public License v3 (LGPLv3)

Сопровождающий: Stéphane Caron

Метки quadratic programming, solver, numerical optimization

Требует: Python >=3.7

Сопровождающие

Классификаторы

• Development Status
  • 5 — Production/Stable
  • Developers
  • Science/Research
  • OSI Approved :: GNU Lesser General Public License v3 (LGPLv3)
  • OS Independent
  • Python :: 3
  • Python :: 3.7
  • Python :: 3.8
  • Python :: 3.9
  • Python :: 3.10
  • Scientific/Engineering :: Mathematics

  Описание проекта

  Quadratic Programming Solvers in Python

  Unified interface to convex Quadratic Programming (QP) solvers available in Python.

  Installation

  Using PyPI

  Using

  Check out the documentation for Windows instructions.

  Usage

  The library provides a one-stop shop solve_qp function with a solver keyword argument to select the backend solver. It solves convex quadratic programs in standard form:

  $$ \begin \begin \underset<\mbox> & \frac x^T P x + q^T x \ \mbox & G x \leq h \ & A x = b \ & lb \leq x \leq ub \end \end $$

  Vector inequalities apply coordinate by coordinate. The function returns the solution $x^*$ found by the solver, or None in case of failure/unfeasible problem. All solvers require the problem to be convex, meaning the matrix $P$ should be positive semi-definite. Some solvers further require the problem to be strictly convex, meaning $P$ should be positive definite.

  Dual multipliers: alternatively, the solve_problem function returns a more complete solution object containing both the primal solution and its corresponding dual multipliers.

  Example

  To solve a quadratic program, build the matrices that define it and call the solve_qp function:

    This example outputs the solution [0.30769231, -0.69230769, 1.38461538] . It is also possible to get dual multipliers at the solution, as shown in this example.

  Solvers

  Solver	Keyword	Algorithm	API	License	Warm-start
  Clarabel	clarabel	Interior point	Sparse	Apache-2.0	✖️
  CVXOPT	cvxopt	Interior point	Dense	GPL-3.0	✔️
  DAQP	daqp	Active set	Dense	MIT	✖️
  ECOS	ecos	Interior point	Sparse	GPL-3.0	✖️
  Gurobi	gurobi	Interior point	Sparse	Commercial	✖️
  HiGHS	highs	Active set	Sparse	MIT	✖️
  MOSEK	mosek	Interior point	Sparse	Commercial	✔️
  NPPro	nppro	Active set	Dense	Commercial	✔️
  OSQP	osqp	Augmented Lagrangian	Sparse	Apache-2.0	✔️
  ProxQP	proxqp	Augmented Lagrangian	Dense & Sparse	BSD-2-Clause	✔️
  qpOASES	qpoases	Active set	Dense	LGPL-2.1	➖
  qpSWIFT	qpswift	Interior point	Sparse	GPL-3.0	✖️
  quadprog	quadprog	Active set	Dense	GPL-2.0	✖️
  SCS	scs	Augmented Lagrangian	Sparse	MIT	✔️

  Matrix arguments are NumPy arrays for dense solvers and SciPy Compressed Sparse Column (CSC) matrices for sparse ones.

  Frequently Asked Questions

  • Can I print the list of solvers available on my machine?
    • Absolutely: print(qpsolvers.available_solvers)
    • Yes, there is also a solve_ls function.
    • You can cast squared norms to QP matrices and feed the result to solve_qp .
    • Unfortunately most available QP solvers are designed for convex problems (i.e. problems for which P is positive semidefinite). That’s in a way expected, as solving non-convex QP problems is NP hard.
    • CPLEX has methods for solving non-convex quadratic problems to either local or global optimality. Notice that finding global solutions can be significantly slower than finding local solutions.
    • Gurobi can find global solutions to non-convex quadratic problems.
    • For a free non-convex solver, you can try the popular nonlinear solver IPOPTe.g. using CasADi.
    • A list of (convex/non-convex) quadratic programming software (not necessarily in Python) was compiled by Nick Gould and Phillip Toint.
    • You will need to install the Visual C++ Build Tools to build all package dependencies.
    • Absolutely! The first step is to install the library and use it. Report any bug in the issue tracker.
    • If you’re a developer looking to hack on open source, check out the contribution guidelines for suggestions.

    Benchmark

    On a dense problem, the performance of all solvers (as measured by IPython’s %timeit on an Intel(R) Core(TM) i7-6700K CPU @ 4.00GHz) is:

    Solver	Type	Time (ms)
    qpswift	Dense	0.008
    quadprog	Dense	0.01
    qpoases	Dense	0.02
    osqp	Sparse	0.03
    scs	Sparse	0.03
    ecos	Sparse	0.27
    cvxopt	Dense	0.44
    gurobi	Sparse	1.74
    mosek	Sparse	7.17

    On a sparse problem with n = 500 optimization variables, these performances become:

    Solver	Type	Time (ms)
    osqp	Sparse	1
    qpswift	Dense	2
    scs	Sparse	4
    mosek	Sparse	17
    ecos	Sparse	33
    cvxopt	Dense	51
    gurobi	Sparse	221
    quadprog	Dense	427
    qpoases	Dense	1560

    On a model predictive control problem for robot locomotion, we get:

    Solver	Type	Time (ms)
    quadprog	Dense	0.03
    qpswift	Dense	0.08
    qpoases	Dense	0.36
    osqp	Sparse	0.48
    ecos	Sparse	0.69
    scs	Sparse	0.76
    cvxopt	Dense	2.75

    Finally, here is a small benchmark of random dense problems (each data point corresponds to an average over 10 runs):

    Note that performances of QP solvers largely depend on the problem solved. For instance, MOSEK performs an automatic conversion to Second-Order Cone Programming (SOCP) which the documentation advises bypassing for better performance. Similarly, ECOS reformulates from QP to SOCP and works best on small problems.

    Contributing

    We welcome contributions, see Contributing for details.

    We are also looking forward to hearing about your use cases! Please share them in Show and tell.

    Citing qpsolvers

    If you find this project useful, please consider giving it a :star: and a citation :books: (check out the Cite this repository button on GitHub).

    Источник

    Quadratic Programming in Python using Numpy?

    I am in the process of translating some MATLAB code into Python. There is one line that is giving me a bit of trouble:

    [q,f_dummy,exitflag, output] = quadprog(H,f,-A,zeros(p*N,1),E,qm,[],[],q0,options); 

    I looked up the documentation in MATLAB to find that the quadprog function is used for optimization (particularly minimization).

    I attempted to find a similar function in Python (using numpy) and there does not seem to be any.

    Is there a better way to translate this line of code into Python? Or are there other packages that can be used? Do I need to make a new function that accomplishes the same task?

    Thanks for your time and help!

    Solution – 1

    There is a library called CVXOPT that has quadratic programming in it.

    def quadprog_solve_qp(P, q, G=None, h=None, A=None, b=None): qp_G = .5 * (P + P.T) # make sure P is symmetric qp_a = -q if A is not None: qp_C = -numpy.vstack([A, G]).T qp_b = -numpy.hstack([b, h]) meq = A.shape[0] else: # no equality constraint qp_C = -G.T qp_b = -h meq = 0 return quadprog.solve_qp(qp_G, qp_a, qp_C, qp_b, meq)[0] 

    Solution – 2

    OSQP is a specialized free QP solver based on ADMM. I have adapted the OSQP documentation demo and the OSQP call in the qpsolvers repository for your problem.

    Note that matrices H and G are supposed to be sparse in CSC format. Here is the script

    import numpy as np import scipy.sparse as spa import osqp def quadprog(P, q, G=None, h=None, A=None, b=None, initvals=None, verbose=True): l = -np.inf * np.ones(len(h)) if A is not None: qp_A = spa.vstack([G, A]).tocsc() qp_l = np.hstack([l, b]) qp_u = np.hstack([h, b]) else: # no equality constraint qp_A = G qp_l = l qp_u = h model = osqp.OSQP() model.setup(P=P, q=q, A=qp_A, l=qp_l, u=qp_u, verbose=verbose) if initvals is not None: model.warm_start(x=initvals) results = model.solve() return results.x, results.info.status # Generate problem data n = 2 # Variables H = spa.csc_matrix([[4, 1], [1, 2]]) f = np.array([1, 1]) G = spa.csc_matrix([[1, 0], [0, 1]]) h = np.array([0.7, 0.7]) A = spa.csc_matrix([[1, 1]]) b = np.array([1.]) # Initial point q0 = np.ones(n) x, status = quadprog(H, f, G, h, A, b, initvals=q0, verbose=True) 

    Solution – 3

    I will start by mentioning that quadratic programming problems are a subset of convex optimization problems which are a subset of optimization problems.

    There are multiple python packages which solve quadratic programming problems, notably

    1. cvxopt — which solves all kinds of convex optimization problems (including quadratic programming problems). This is a python version of the previous cvx MATLAB package.
    2. quadprog — this is exclusively for quadratic programming problems but doesn’t seem to have much documentation.
    3. scipy.optimize.minimize — this is a very general minimizer which can solve quadratic programming problems, as well as other optimization problems (convex and non-convex).

    You might also benefit from looking at the answers to this stackoverflow post which has more details and references.

    Note: The code snippet in user1911226′ answer appears to come from this blog post:
    https://scaron.info/blog/quadratic-programming-in-python.html
    which compares some of these quadratic programming packages. I can’t comment on their answer, but they claim to be mentioning the cvxopt solution, but the code is actually for the quadprog solution.

    Solution – 4

    You could use the solve_qp function from qpsolvers. It can be installed, along with a starter kit of open source solvers, by pip install qpsolvers[open_source_solvers] . Then you can replace your line with:

    from qpsolvers import solve_qp solver = "proxqp" # or "osqp", "quadprog", "cvxopt", . x = solve_qp(H, f, G, h, A, b, initvals=q_0, solver=solver, **options) 

    There are many solvers available in Python, each coming with their pros and cons. Make sure you try different values for the solver keyword argument to find the one that fits your problem best.

    Here is a standalone example based on your question and the other comments:

    import numpy as np from qpsolvers import solve_qp H = np.array([[4.0, 1.0], [1.0, 2.0]]) f = np.array([1.0, 1]) G = np.array([[1.0, 0.0], [0.0, 1.0]]) h = np.array([0.7, 0.7]) A = np.array([[1.0, 1.0]]) b = np.array([1.0]) q_0 = np.array([1.0, 1.0]) solver = "cvxopt" # or "osqp", "proxqp", "quadprog", . options = x = solve_qp(H, f, G, h, A, b, initvals=q_0, solver=solver, **options) 

    Источник

    Читайте также:  margin-bottom