Feasibility in case of inaccurate solution or maximum iterations reached

1

Hello,

I have another question regarding the status values of OSQP.
Sometimes I get the status solution inaccurate or maximum iterations reached.
Does OSQP give me in that case a feasible solution? Or should I always check it by evaluating the constraints after getting such status?

Best regards

Manuel

2

I think I found the answer while debugging osqp_solve.
In case anyone has the same question in the future, here is my insight:
When maximum iterations is hit, similar to the case when one gets solution inaccurate, OSQP internally multiplies eps_rel, eps_abs, eps_dual_inf and eps_prim_inf by a factor of 10. Then it checks the conditions for primal and dual infeasibility like stated in the paper. Hence there is a good chance that the obtained solution if feasible however this now depends on the inital setting of eps_dual_inf and eps_prim_inf.
Hope I didn’t get this wrong.
Quickly evaluating the solutions revealed in my case:
l<=Ax<=u with using the standard settings of eps_dual_inf and eps_prim_inf results mostly in infeasible solutions that are not reported by OSQP.

3

Hi Manuel. Thanks for using OSQP!

When maximum iterations is hit, similar to the case when one gets solution inaccurate, OSQP internally multiplies eps_rel, eps_abs, eps_dual_inf and eps_prim_inf by a factor of 10. Then it checks the conditions for primal and dual infeasibility like stated in the paper. Hence there is a good chance that the obtained solution if feasible however this now depends on the inital setting of eps_dual_inf and eps_prim_inf.
Hope I didn’t get this wrong.

Yes this is correct. Feasibility, infeasibility and optimality are always up to the tolerances provided. OSQP reports the inaccurate statuses when the conditions are satisfied after relaxing the related tolerance by one order of magnitude.

l \le Ax \le u with using the standard settings of eps_dual_inf and eps_prim_inf results mostly in infeasible solutions that are not reported by OSQP.

Thanks for reporting it. Would it be possible to send us a minimal working example (MWE) for us to try?

4

Hi Bartolomeo,

thank you for your reply! I will try to package a MWE on Monday for you.
I am currently not sure if the behavior of OSQP is right or wrong. Maybe I expressed myself somewhat unclear.
The maximum number of iterations is reached and the solution is therefore probably quite suboptimal. However I am quite sure that the problem is feasible hence I would also expect that OSQP does not mark it as infeasible. This really comes down to what OSQP really should detect: Infeasibility of the problem itself or infeasibility of the current solution iterate. If it is the former, then everything is fine.

Best regards
Manuel

5

The infeasibility status is related to the problem itself, i.e., the feasible set is empty. If you want to have a look at the theory behind the infeasibility detection in OSQP, it is outlined in this paper (available on here as well).

6

Thanks again for the answer and clarification! That therefore makes the MWE obsolete.

I guess my confusion came from missing proper background of the ADMM method (which I am currently diving into).
Since OSQP gave me OSQP_MAX_ITER_REACHED and polish_status=1 and I was pretty sure, that the feasible set of the problem is not empty, that last iterate solution->x was at least in the feasible set because OSQP did not report infeasibility. This points into the direction that the iterates of the decision variables need not to be in the feasible set for a feasible problem in OSQP.
Maybe it would be a nice addition to the info struct to also inform if the current solution->x is in the feasible set so that the user does not have to check it afterwards. The addition of course only makes sense if that info really pops out somewhere internally in OSQP and no more computation has to be added for it. In my case, I could easily live with a suboptimal solution when the maximum iterations are reached but it is very important that my constraints are not violated.

Best regards

Manuel

7

Unfortunately, I have another question regarding the infeasibility check.
I am probably currently using OSQP quite wrong by setting eps_abs = 1 and eps_rel=1 to these huge values. But I just wanted to check the case when I require almost no optimality of the solution to see if OSQP at least terminates in that case and offers me a solution. And for that case indeed it terminates unsurprisingly and tells me solved. I didn’t touch eps_prim_inf and eps_dual_inf. I assumed to get in this case a feasible but suboptimal solution. But what I got is info->dual_res > 90000 and a clearly infeasible solution.
Again, maybe this is obvious from the algorithmic perspective for you developers of OSQP but I somehow expected a different result. Is there an explanation for this behavior?

Best regards,

Manuel

8

There is no reason to expect that the solver will start to produce strictly feasible solutions after a few iterations because it converges to both feasibility and optimality at the same time. The tolerances you are using are on KKT-like conditions, and if those are only loosely satisfied then there is no reason to expect that your solution is feasible.
If you need a solution which will maintain feasible intermediate iterates, you might be better off with an active-set type solver.

9

Thank you for your answer.
That indeed clarifies things for me. And I probably again confused in my head that eps_dual_inf and eps_prim_inf are not related to the feasibility of the solution but to the problem itself. I am also stuck at the definition that a solution must lie in the feasible set - I guess when numerics come into play, that just does not hold for some methods.
The thing is, I need the speed of OSQP but the best guarantee of obtaining a feasible solution for safety reasons in my application. qpOASES might be too slow, so I probably will stick with OSQP and rather change my problem.

Best regards,

Manuel