Consider two systems A and B:

A$: f_i(x) \lt 0, i=1, \dots, m, Ax = b$

B$: \min_{\{x,s\}} s$ subject to $f_i(x) - s \le 0, i = 1, \dots, m; Ax = b$

Then B has optimal value $p^* \lt 0$ iff there exists a solution to A

I can prove $\Rightarrow$ but I'm having trouble showing $\Leftarrow$.

My original attempt was to assume $x$ is the solution of A, and therefore: IF $x$ is used in B then the smallest $s$ that satisfies the equation must be in $[f_i(x), 0)$ since $f_i(x) \lt 0$. But this is assuming that for $B$ the same value of $x$ is used. Which doesn't seem right because $x$ might not work for B.

Any ideas?

  • $\begingroup$ can you show the first few steps for $\Leftarrow$? $\endgroup$ – LinAlg Feb 17 at 16:06
  • 1
    $\begingroup$ A bit of pedantry here: if $B$ is unbounded below—and it certainly can be for certain instances of this—is it correct to say that $B$ has an optimal value $p^*<0$? After all, it has no finite optimal value. @LinAlg what do you think? $\endgroup$ – Michael Grant Feb 18 at 2:41
  • $\begingroup$ And even if $p^*$ is finite, that doesn't mean there's an $x$ that attains it. (Though there must be such an $x$ for at least one $p$ satisfying $p^*\leq p<0$.) $\endgroup$ – Michael Grant Feb 18 at 2:43
  • $\begingroup$ You really should combine your two questions together (the other being math.stackexchange.com/questions/3116263/…). $\endgroup$ – Michael Grant Feb 18 at 2:45
  • $\begingroup$ @MichaelGrant not pedantic: you are right! $\endgroup$ – LinAlg Feb 18 at 2:46

Your Answer


Browse other questions tagged or ask your own question.