Theory behind heuristic used for guessing binding constraints

Hi guys and thank you for opensourcing this lovely admm solver.

Can you perhaps shed some light on the heuristic used to guess active constraints?

Also, if this guess is incorrect (i.e. misses a binding constraint), is it then correct to assume that the iterative refinement step will not converge towards the same solution as a problem where all active constraints are included?

If so, can one somehow detect and incorporate the missing constraint?

Thanks,
Marcus

To guess the active constraint set we just look at the multipliers and take the subset of constraints that correspond to the active ones. There is a bit of a wrinkle because the constraints are all two-sided, so you have to consider the sign of the ADMM variable y in the solver to figure out which side is active. It happens here in the code. See also p.10 of this paper.

Once we have our guess about the active constraint, we treat the problem as if it is an equality constrained QP. If that guess is incorrect, then solution we get in the polishing step will be defective somehow (e.g. infeasible) and we just don’t use it.

If the polishing fails, then there is no easy way to inject the ‘missing’ constraint, or to adjust the active set to get the correct combination, without implementing something that amounts to another QP solver, e.g. the simplex method or some variation thereof.

Thanks for your informative response.

Regarding the last bit about another QP solver, would that simplex call need to run on the full problem or the reduced one? Or would one run the full problem but somehow use the current state as a warm start?

Thanks again,
Marcus.

If the polish step fails then the reduced problem would have the wrong set of constraints marked as the active set. You would therefore need to add / exchange constraints in the active set somehow. There’s no obvious way of working out which missing constraints are the right ones though, so you would need to consider all of the remaining constraints from the full problem.

Regarding warm-starting : it’s not clear to me that that would work either, since it’s not obvious that the incorrect active set would produce a point that was either primal or dual feasible. Maybe you could do some variation of a two-phase simplex method, but don’t think it would necessarily be better than just using the simplex method on its own.

All of the above would also complicate the code enormously, so definitely not a road we plan to go down at present.