Infeasibility Detection

[govindchari]

This is not really an issue, it is more so a question.

I noticed that PIQP can return PIQP_PRIMAL_INFEASIBLE or PIQP_DUAL_INFEASIBLE. I read through the PIQP paper and did not see any mention of infeasbility detection. How is infeasibility detection implemented in the solver?

[RSchwan]

Indeed, it's not mentioned in the paper (due to space constraints). Basically, what's happening is that for a primal infeasible problem the dual variables of the local problem ($y,z$) diverge from the outer primal variables ($\lambda,\nu$), and for a dual infeasible problem the primal variables of the local problem ($x$) diverge from the outer primal variables ($\xi$). If this infinity norm of the divergence hits a threshold of 1e12 (kind of arbitrarily chosen as part of internals) while the local residuals ($r_x,r_y,r_z$) are converging, then we detect infeasibility and abort the solver.

This method of infeasibilty detection works, but might not be the most robust and can take quite some iterations to trigger. Another option is to change the problem formulation to a homogeneous embedding, which detects infeasibility as part of its convergence to optimality. Actually, SCS switched to this approach in the latest version (see corresponding paper) which is also employed by the new Clarabel solver. I've actually playing around with the idea to also add this to PIQP, but haven't found time and a reason to do so. Normally, I'm solving feasible problems :).

On this note, there are also results which show that the Methods of Multipliers algorithm converges to "the closest" feasible solution of a primal infeasible problem. This might be an interesting adaptation to our algorithm, to allow for "infeasible problem-solving", i.e., still converge but to the closest feasibile solution for primal infeasible problems. This could be useful in the context of MPC and SQP, and I might extend PIQP in the future to support this.

Anyway, thanks for the questions. This reminded me to reflect these question and write them down ;).

I'll keep this issue open as a reminder for future plans.

[govindchari]

Awesome, thanks for the detailed answer!