1

I am currently working on a problem that requires a solution to a standard QP of the form $$ \min_{z \in \mathbb{R}^n} z^TQz + q^Tz \quad s.t. Az \leq b, \, Q \succ 0, $$ with $b \in \mathbb{R}^m$ that that could potentially be infeasible ($Az \leq b$ is an empty set). I would like to solve a different QP that recovers the true solution if the original QP is feasible and any solution + the possibility to detect the infeasibility of the previous problem in case it is infeasible.

I'm considering something like $$ \min_{z \in \mathbb{R}^n, r \in \mathbb{R}^m} z^TQz + q^Tz + r^T R r\quad s.t. Az \leq b + r, \, R,Q \succ 0. $$ Through some appropriate choice of $R$, I'm hoping to recover $r = 0 $ if the original QP is feasible and $r \neq 0 \, (r > 0 ?)$ otherwise.

Does this in general make sense? Or can you think of a different solution? Can I atleast expect that $r$ will be "small" in case the of feasibility of the original problem?

Torsten Koller
  • 15
  • What do you mean by "$Az \le b$ could be non-convex"? Is $z \mapsto Az$ not a linear transformation? – Robert Israel Aug 23 '18 at 15:37
  • You are right, $A z \leq b $ has to be convex. So I guess I am only considering the case where $ A z \leq b$ is empty! Thanks for pointing this out. – Torsten Koller Aug 23 '18 at 15:47

1 Answers1

2

You are close, it's called exact penalty functions (keyword for searches). Instead of quadratic, you typically use a linear penalty $\lambda r$ with $r\geq 0$. For sufficiently large $\lambda$, the solution satisfies the properties you desire.

Johan Löfberg
  • 9,497
  • 1
  • 15
  • 15