# Measuring infeasibility in convex optimization, relations with dual problem

A question regarding convex optimization and (maybe) duality.

I have a problem in the form \begin{align} x^* = \mathrm{arg} \min_x f(x) \quad \text{s.t.} \quad A x \leq b, C x = d, \end{align} where $$f$$ is either quadratic or, if it makes things easier, linear. Let's also assume that $$P = \{ x \mid A x \leq b \}$$ is bounded and not empty.

I would like to design an auxiliary optimization problem that:

• if the original problem is feasible returns the solution $$x^*$$ of the original problem,
• if the original problem is infeasible returns the minimum perturbation (according to some norm) $$e^*$$ that I should add to $$d$$ to make the problem feasible (remember $$P \neq \emptyset$$).

A naive approach could be, for example, something like \begin{align} \min_{x,e} f(x) + M \| e \| \quad \text{s.t.} \quad A x \leq b, C x = d + e, \end{align} where $$M$$ is "big enough". This however is very unpractical since the high value of $$M$$ would lead to numeric problems.

Do you have any better idea?

Do you think duality can help in some way here? If I solve the dual of the original problem, and I detect unboundedness (we know that, under these assumptions, the primal infeasible implies the dual unbounded) can I elaborate the result to get something related to $$e^*$$? For example, could an extreme ray of the dual feasible set help?

Thank you very much!

• If the primal is infeasible, the dual may also be infeasible. Why not solve 2 problems? Nov 28 '18 at 19:03
• You could add a binary variable to deal with infeasibility, but I doubt it is faster. Nov 28 '18 at 19:17
• In the quadratic case, the dual is always feasible, but in general you are right: the dual can also be infeasible. I guess solving two problems is always an option. I wanted to understand if I'm trowing away some useful information from the solution of the dual of the original problem. Nov 28 '18 at 19:20
• This would be actually a lower level QP/LP solver of a branch and bound code for mixed integer programming (reason why I have the solution of the dual almost for free). Yes, the binary would work, but in practice it's equivalent to solve two problems... Nov 28 '18 at 19:23

Well, if the original problem is infeasible, you can just solve for \begin{align} \min_{x,e} \|e\|: & \\ Ax&\le b, \\ e &= d-Cx. \end{align}