 # Can the primal in-feasibility certificate be used to help identify problematic constraints?

I have a problem with a quadratic objective function and non linear constraints. I can solve this problem in general by using a non linear optimizer, but it takes too long to be useful. I can solve this problem (most of the time) using OSQP by creating locally linearized constraints. The 1st derivative of the constraints is discontinuous at 0 so I have to split it into a set where the domain is positive and another where the domain is negative. I then iterate by solving it with some initial constraints, use the Lagrange multipliers (I’m assuming that’s what results.y is) to determine which positive domain constraints want to become negative domain constraints (and vice versa) and switch some of them.

As I said, this works most of the time, but in some cases, the initial constraints I have chosen are infeasible in some way, and in these cases, I can manually fiddle with them to get it started. So I want to automate this fiddling. Can the primal in-feasibility certificate be useful for this task?

When the problem is feasible then the output y is the multiplier for the corresponding constraint. Note that since the constraints are all two sided (i.e. they are in the form l \le Ax \le u), then the sign of of a given element of y indicates which side is active.

If your problem is primal infeasible then it means you have some set of constraints that are collectively inconsistent. It is not clear, therefore, that any particular constraint can be blamed as the `bad` one. It is generally the case that a non-zero value in some element of the primal infeasibility certificate is indicative of the corresponding constraint not being satisfiable, but the converse is not true in general I think.

The primal infeasibility certificate does have a clear meaning - see Prop. 3.1(i) in this paper. Generally speaking, it is a proof that the dual problem is unbounded above, since the certificate is a direction of unbounded growth in the dual objective that will never violate the dual constraints. (Caveat: this true only if your problem is not simultaneously primal and dual infeasible, which is usually the case).

If you find an infeasible problem, you might find it easier to solve a problem using the same constraints equipped with element-wise slack terms, and minimize the 1-norm of the slacks. This would tell you the least relaxation of your problem constraints that is required to reach feasibility.

Excellent explanation and a great idea about the element-wise slack terms. Thanks!