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!

  • $\begingroup$ If the primal is infeasible, the dual may also be infeasible. Why not solve 2 problems? $\endgroup$
    – LinAlg
    Nov 28 '18 at 19:03
  • $\begingroup$ You could add a binary variable to deal with infeasibility, but I doubt it is faster. $\endgroup$
    – LinAlg
    Nov 28 '18 at 19:17
  • $\begingroup$ 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. $\endgroup$ Nov 28 '18 at 19:20
  • $\begingroup$ 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... $\endgroup$ 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}

  • $\begingroup$ Unfortunately I do not know a priori if the problem is infeasible. Your approach would then boil down to just solve two problems, right? $\endgroup$ Nov 28 '18 at 19:25
  • $\begingroup$ You will have to first check the feasibility of the original problem anyway. Besides, this new problem is always feasible. $\endgroup$
    – Hans
    Nov 28 '18 at 19:36
  • $\begingroup$ I do not agree that I have to first check the feasibility of the original problem anyway: the example I described with the big M in the objective function is a single problem, where I do not need that check first. No? $\endgroup$ Nov 28 '18 at 19:44
  • $\begingroup$ Your requirement is to solve for the original problem if the domain is feasible. Your objective function with the big M violates that requirement. The bigger the M is, the further away your solution deviates from the true solution, when the original problem is feasible. My formulation, on the other hand, fulfills exactly your two requirements. $\endgroup$
    – Hans
    Nov 28 '18 at 19:56
  • 1
    $\begingroup$ It's clear that solving two problems as you are suggesting would work: my question is in fact how to avoid that... $\endgroup$ Nov 28 '18 at 20:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.