DAQP returns infeasible solution but exitflag is feasible

[bemilio]

Sometimes DAQP returns an infeasible solution and exitflag==1 (that is, the solution is marked as optimal)

Here is a script to recreate the example on which I experienced this behavior. Sorry, I couldn't work out something more minimal. This behavior appears quite unpredictably on some problem instances.

julia version: 1.11.5

Dependencies hashes:

DAQP = "c47d62df-3981-49c8-9651-128b1cd08617"
OSQP = "ab2f91bb-94b4-55e3-9ba0-7f65df51de79"
SparseArrays = "2f01184e-e22b-5df5-ae63-d93ebab69eaf"

• CODE:

using OSQP
using SparseArrays
using DAQP

H = [6.837677669279314 1.3993262799977795 1.9781574256330445 0.7988389688453156;
    1.3993262799977795 4.91607513347457 0.8347008717503388 0.964319980996552;
    1.9781574256330445 0.8347008717503388 5.6186371819867755 0.23421356059787485;
    0.7988389688453156 0.964319980996552 0.23421356059787485 5.512564828518534]
q = [-0.9018168388545096, 1.3888380439021342, -3.2050167583822065, 6.2604158413126205]

A = [0.0 0.0 0.0 0.0;
    1.0 0.0 1.0 0.0;
    0.0 0.0 0.0 0.0;
    -1.0 0.0 -1.0 0.0;
    1.0 0.0 1.0 0.0;
    0.5 1.0 0.5 1.0;
    -1.0 0.0 -1.0 0.0;
    -0.5 -1.0 -0.5 -1.0;
    1.0 0.0 0.0 0.0;
    -1.0 0.0 0.0 0.0;
    0.0 1.0 0.0 0.0;
    0.0 -1.0 0.0 0.0;
    0.0 0.0 1.0 0.0;
    0.0 0.0 -1.0 0.0;
    0.0 0.0 0.0 1.0;
    0.0 0.0 0.0 -1.0]
b = [2.2693082025353517, 1.3445735938597536, -0.2693082025353519, 0.6554264061402464, 2.2330893356345, 1.172286796929877, -0.23308933563449985, 0.8277132030701232, 1.0, 0.5, 1.0, 0.5, 0.5, 2.0, 0.5, 2.0]

prob_DAQP = DAQP.Model()

m = size(A, 1)
DAQP.setup(prob_DAQP, H, q, A, b, Float64[], zeros(Cint, m))

y, _, exitflag, _ = DAQP.solve(prob_DAQP)

if exitflag < 0
    printl("DAQP: infeasible")
else
    println("DAQP: feasible")
end

if maximum(A * y - b) > 1e-5
    println("DAQP output is infeasible")
end


prob_OSQP = OSQP.Model()
OSQP.setup!(prob_OSQP; P=sparse(H), q=q, A=sparse(A), u=b, l=-Inf * ones(m))
results = OSQP.solve!(prob_OSQP)

if results.info.status_val < 0
    println("OSQP infeasible")
else
    println("OSQP feasible")
end

• Output

DAQP: feasible
DAQP output is infeasible
-----------------------------------------------------------------
           OSQP v0.6.2  -  Operator Splitting QP Solver
              (c) Bartolomeo Stellato,  Goran Banjac
        University of Oxford  -  Stanford University 2021
-----------------------------------------------------------------
problem:  variables n = 4, constraints m = 16
          nnz(P) + nnz(A) = 34
settings: linear system solver = qdldl,
          eps_abs = 1.0e-03, eps_rel = 1.0e-03,
          eps_prim_inf = 1.0e-04, eps_dual_inf = 1.0e-04,
          rho = 1.00e-01 (adaptive),
          sigma = 1.00e-06, alpha = 1.60, max_iter = 4000
          check_termination: on (interval 25),
          scaling: on, scaled_termination: off
          warm start: on, polish: off, time_limit: off

iter   objective    pri res    dua res    rho        time
   1  -4.6081e+00   2.69e-01   7.77e-01   1.00e-01   8.52e-05s
  50   1.0000e+30   2.69e-01   6.98e-04   1.09e+01   1.37e-04s

status:               primal infeasible
number of iterations: 50
run time:             1.43e-04s
optimal rho estimate: 4.18e+02

OSQP infeasible

[darnstrom]

Thanks for reporting this @bemilio. The problem is most likely that your third constraint is trivially infeasible (since the row in A is zero and b < 0) Currently zero rows are just ignored by DAQP, but it would be better to also mark infeasibility (i.e., addressing this todo.)

I will fix this shortly.

[darnstrom]

This is fixed in #83, which has been merged on the dev branch. This fix will also be merged into main in the next release of DAQP.

[bemilio]

that was quick! Thank you