Calculating Duality Gap

Hi there!

I’m reaching out as I’m trying to do some comparisons of an algorithm I’m working that uses OSQP compared to one used by ECOS. In order to make my comparison as fair as possible, I’m trying to replicate the settings used in ECOS in OSQP (as the original method was modeled using ECOS).

These are the settings in ECOS:

#define FEASTOL /* primal/dual infeasibility tolerance /
#define ABSTOL /
absolute tolerance on duality gap /
#define RELTOL /
relative tolerance on duality gap */

From looking over the settings and the OSQP paper, FEASTOL would be equivalent to both eps_prim_inf and eps_dual_inf (I guess ECOS does not have a way of splitting these two). However, it doesn’t look like OSQP has settings for termination based off duality gaps (and indeed looking through this link, it looks like it’s a TODO:

Just wanted to see if anything has changed by chance on that end, and also, if it even makes sense to compare the termination criteria of something like the FEASTOL from one solver to the other given that they’re different methods (first order vs. IPM). Also, as you mentioned in the paper, internal problem scaling will play a role in comparing the solvers as well.

We do not compute the duality gap as it would involve computing the dual objective value. While this is easy for problems with linear objective, for problems considered by OSQP it would involve computing the pseudoinverse of P (see this comment).

You can check Section 8 of the OSQP paper to see the metric we used to compare OSQP against IPM-based solvers.

Hi Goran,

Thanks for the response; regarding the duality gap, this is exactly what I suspected (as I had also read your comment), but just wanted to make sure there were no updates on this.

Secondly; regarding the primal/dual infeasibility tolerances, it looks like in section 8, you modify eps_rel and eps_dual, however, wouldn’t the infeasibility tolerances (at least, when compared to ECOS) be eps_inf_prim and eps_inf_dual? I might have misunderstood either this if that’s the case.

eps_inf_prim and eps_inf_dual are primal and dual infeasibility tolerances that tell us how small the infeasibility conditions need to be to report that the problem is primal or dual infeasible; see here.

This is different from eps_prim and eps_dual (which are computed based on eps_abs and eps_rel; see here) that tell us how small the optimality residuals need to be to report that the problem is optimal. The labels prim and dual mean that these are tolerances on the primal and dual optimality residuals.

Hi, thanks for clearing that up. I think I figured that out last night and then forgot about it today :sweat_smile:.