Skip to content
/ QPDAS.jl Public

Quadratic Programming Dual Active Set solver using iterative refinement

License

Notifications You must be signed in to change notification settings

mfalt/QPDAS.jl

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

30 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

QPDAS

Quadratic Programming Dual Active Set solver using iterative refinement.

Build Status codecov

The solver is written completely in Julia, and should be able to handle types of any precision.

The algorithm is based on a paper that is submitted to the Control and Decision Conference 2019.

Solves the mixed constraint positive-definite quadratic programming problem

min 1/2 xᵀPx + zᵀx
s.t Ax=b,
    Cx≤d

using a dual-active set method. Since the algorithm is solving the dual, it is very efficient when the number of inequalities is small.

At the moment, it is not possible to manually warm-start the problem.

Usage:

qp = QuadraticProgram(A, b, C, d, z=zeros(..), P=I; semidefinite=true, ϵ = sqrt(eps(T)), smartstart=true)
sol, val = solve!(qp)

Keyword arguments:

  • semidefinite: Refers to the dual problem. If true then iterative refinement is used to solve the linear systems in the dual. Must be true if the constraints of the primal are not linearly independent.
  • ϵ: The relaxation used for iterative refinement
  • smartstart: if true then the initial active set is guessed from the linear term in the dual. If false, then the initial active set is empty in the dual.

Updating

The vectors b,d,z can be updated without re-factorizing the problem using

update!(QP::QuadraticProgram; b=QP.b, d=QP.d, z=QP.z)

The next solve will use the previous solution as an initial guess.

Dual problem

It is also possible to directly formulate and solve the dual box-constrained problem

min 1/2 xᵀGx + cᵀx,
s.t dᵢ ≤ xᵢ ∀ i>n-m
where m=size(d,1), n=size(c,1).

At the moment, only d .== 0 is supported.

boxQP = BoxConstrainedQP(G, c, d; semidefinite=true, ϵ = sqrt(eps(T)))
run_smartstart(boxQP) # Run to set initial active ste guess
sol = solve!(boxQP)

The vector c can be efficiently updated using

boxQP.c = c

Examples

A MPC example in reduced form is located in examples/mpc.jl, and an example of projection onto a polytope at examples/polytope_projection.jl.

About

Quadratic Programming Dual Active Set solver using iterative refinement

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages