0

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?

Oliver G
  • 4,792
  • can you show the first few steps for $\Leftarrow$? – LinAlg Feb 17 '19 at 16:06
  • 1
    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? – Michael Grant Feb 18 '19 at 02:41
  • 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$.) – Michael Grant Feb 18 '19 at 02:43
  • You really should combine your two questions together (the other being https://math.stackexchange.com/questions/3116263/how-are-these-two-systems-strong-alternatives). – Michael Grant Feb 18 '19 at 02:45
  • @MichaelGrant not pedantic: you are right! – LinAlg Feb 18 '19 at 02:46
  • So I'm just not sure the claim is correct as stated, unless we are willing to assume the convention that $p^*=-\infty$ is a legitimate optimal value. – Michael Grant Feb 18 '19 at 02:54
  • @MichaelGrant I would assume that $- \infty$ is a legitimate optimal value. The book explicitly says "The optimal value $p^$ of this problem (B) is negative if and only if there exists a solution to the strict inequality system (A*)". – Oliver G Feb 18 '19 at 12:48
  • @LinAlg I have added what I tried to the question. – Oliver G Feb 18 '19 at 13:16
  • @OliverG for me the $\Leftarrow$ would start with "assume that there is an $s < 0$ and an $x$ that satisfy $f_i(x) - s \leq 0$, $i=1,\ldots,m$ and $Ax=b$". You can then argue from there. – LinAlg Feb 18 '19 at 15:17

0 Answers0