I'm a bit ashamed that I have a math degree and can't figure out this seemingly simple problem, but that's what the situation is. From Introduction to Linear Optimization by Bertsimas and Tsitsiklis, they mention on p. 18 that

$|x_i|$ is the smallest number $z_i$ that satisfies $x_i \leq z_i$ and $-x_i \leq z_i$

How does one prove this?

I wish I could provide some more context to this, but this statement seems to have been mentioned as a side comment. We don't know anything other than that $x_i \in \mathbb{R}$.

I do know that by definition (and I have to admit, it is confusing that they use $z_i$ to represent $|x_i|$ as well):

$$|x_i| = \begin{cases} x_i, & x_i \geq 0 \\ -x_i, & x_i < 0\text{.} \end{cases}$$ I believe what we're trying to prove is that $$|x_i| = \min\{z_i \mid x_i \leq z_i, -x_i \leq z_i\}\text{.}$$ However, I'm not sure how to derive this from the definition of $|x_i|$ given above.

  • $\begingroup$ Is anything special about the subscript $i$? $\endgroup$ – Clayton Jun 20 '18 at 23:16
  • $\begingroup$ @Clayton Nah. It's just a component of a vector in $\mathbb{R}^n$. I figured I should keep the notation as is, should someone have the same question I have. $\endgroup$ – Clarinetist Jun 20 '18 at 23:16

Let $z=\min\{z_i \mid x_i \leq z_i, -x_i \leq z_i\}\text{.}$ Let us also get rid of the index $i$ of $x_i$: I will denote it $x$.

First, we have $x\leq |x|$ and $-x\leq |x|$, which can be established simply by a disjonction of cases (depending on whether $x$ is negative or non-negative). Hence, by definition, $z\leq |x|$.

Second, we know that $z\geq \max(x,-x)$ by definition. But we have the identity $\max(x,-x)=|x|$ which again may be shown by disjonction of cases.

We conclude that $|x|=z$.

  • $\begingroup$ Well, $z$ is defined as the minimum of a set, which contains $|x|$ ... $\endgroup$ – Suzet Jun 20 '18 at 23:21
  • $\begingroup$ Ah right, I was reading your argument incorrectly. $\endgroup$ – LinAlg Jun 20 '18 at 23:23
  • 1
    $\begingroup$ Thank you for your answer! The only comment I have is that it wasn't obvious to me how to use proof by disjunction to prove $x \leq |x|$ and $-x \leq |x|$, so I ended up just using $|x| = \max(-x, x)$, from which those inequalities follow trivially. $\endgroup$ – Clarinetist Jun 20 '18 at 23:34

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.