README.md

QPDAS

Quadratic Programming Dual Active Set solver using iterative refinement.

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.