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!
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}