1
$\begingroup$

Consider the function:

$$ f: x \mapsto \begin{cases} a_1 x + b_1 & x \le \frac{b_1 - b_2}{a_2 - a_1} \\ a_i x + b_i & \frac{b_{i-1} - b_i}{a_i - a_{i-1}} \le x \le \frac{b_i - b_{i+1}}{a_{i+1} - a_i} \quad \forall 1 \le i \le n-1 \\ a_nx + b_n & x \ge \frac{b_{n-1} - b_n}{a_n - a_{n-1}} \end{cases} \, $$

where we can assume that $a_1 < \dots < a_n$. This is question 3.36 in Boyd and Vandenberghe. The solutions manual (p. 55 of the PDF) claims that:

For $a_i ≤ z ≤ a_{i+1}$, the supremum in the definition of $f^∗$ is reached at the breakpoint between the segments $i$ and $i + 1$, i.e., at the point $(b_{i+1} − b_i)/(a_{i+1} − a_i)$, so we obtain $$f^∗(z) = −b_i − (b_{i+1} − b_i)\frac{y − a_i}{ a_{i+1} − a_i}$$ where $i$ is defined by $a_i ≤ z ≤ a_{i+1}$.

Question: Why is this claim true? How can we prove that claim without knowing anything about the $b$'s or the relative sizes of the $(a_i - a_{i-1})$'s?

What I have figured out so far about $f^*(z)$ is included below, but it doesn't seem strong enough to allow me to reach the same conclusion.

Note: This is a follow-up to a previous question.

Work so far: One can write (note: $c_{i,i+1}$ is meant to denote the breakpoint between the $i$th and $(i+1)$st segments, specifically $(b_i - b_{i+1})/(a_{i+1} - a_i)$):

$$\begin{array}{rcl} f^*(z) & = & \sup_{x \in \mathbb{R}}[ xz - f(x) ] \\ & = & \max_{i \in [n]} \left\{ \begin{array}{l} \displaystyle \sup_{x \le c_{12}} [ xz - a_1 x - b_1] \,, \\ \displaystyle \sup_{c_{12} \le x \le c_{23}} [xz - a_2 x - b_2] \,, \\ \vdots \\ \displaystyle \sup_{x \ge c_{n-1, n}} [xz - a_n x - b_n] \end{array} \right\} \\ & = & \max_{i \in [n]} \left\{ \begin{array}{l} \displaystyle \sup_{x \le c_{12}} [ (z - a_1)x - b_1] \,, \\ \displaystyle \sup_{c_{12} \le x \le c_{23}} [(z - a_2) x - b_2] \,, \\ \vdots \\ \displaystyle \sup_{x \ge c_{n-1, n}} [(z - a_n) x - b_n] \end{array} \right\} \,. \\ \end{array}$$

We note that the supremum terms over $[c_{i-1, i} , c_{i, i+1}]$ will always be finite (i.e. for $1 < i < n$), since we are always taking the supremum of a continuous function over a compact set (closed interval), making the extreme value theorem applicable. Thus, when checking to see when (if ever) $f^*(z)$ is unbounded, it suffices to only consider the terms corresponding to suprema over $(-\infty, c_{12}]$ and $[c_{n-1, n}, \infty)$.

Because a linear function is unbounded \textit{from above} (we don't need to consider whether it's unbounded from below since we're taking a supremum) as $x \to -\infty$ if and only if its slope is negative, we have that:

$$ \left[ \sup_{x \le c_{12}} [ (z-a_1) x - b_1 ] = +\infty \quad \iff \quad z - a_1 < 0 \right] \quad \quad \implies \quad \quad f^*(z) = +\infty \text{ whenever }z < a_1 \,, $$

since the maximum over a finite set will always be $+\infty$ if one of the elements of that set is $+\infty$.

Similarly, since a linear function is unbounded from above as $x \to \infty$ if and only if its slope is positive:

$$ \left[ \sup_{x \ge c_{n-1,n} } [ (z-a_n) x - b_n ] = +\infty \quad \iff \quad z - a_n > 0 \right] \quad \quad \implies \quad \quad f^*(z) = +\infty \text{ whenever }z > a_n \,. $$

Therefore we only need to do any work calculating $f^*(z)$ for $z$ in the closed interval $[a_1, a_n]$.

When $z \in [a_1, a_n]$, $z - a_1 \ge 0$, so the slope of $(z-a_1)x - b_1$ is non-negative, and thus the supremum of the first term occurs at the right endpoint ($c_{12}$). Similarly, $z-a_n \le 0$, so the slope of $(z - a_n)$ is non-positive, and the supremum of the last term occurs at the left endpoint ($c_{n-1, n}$).

For the terms $1 < i < n$, consider that the slope is non-positive, and thus the supremum occurs at the left endpoint ($c_{i-1, i}$) of the interval in question, only when $z \le a_i$, whereas the slope is non-negative, and the supremum occurs at the right endpoint ($c_{i,i+1}$) of the interval only when $z \ge a_i$. Therefore, when restricted to $[a_1, a_n]$, we have for $f^*(z)$ that:

$$\begin{array}{rcl} f^*(z) & = & \max_{i \in [n]} \left\{ \begin{array}{l} (z - a_1)c_{12} - b_1 \,, \\ \vdots\\ \begin{cases} (z-a_i)c_{i-1,i} - b_i & z \in [a_1, a_i] \\ (z-a_i)c_{i,i+1} - b_i & z \in [a_i, a_n] \end{cases} \\ \vdots \\ (z - a_n)c_{n-1, n} - b_n \end{array} \right\} \,. \\ \end{array}$$

Specifically, for a $z$ within a given $[a_i, a_{i+1}]$, we have:

$$\begin{array}{rcl} f^*(z) & = & \max_{i \in [n]} \left\{ \begin{array}{l} (z - a_1)c_{12} - b_1 \,, \\ \vdots\\ (z - a_{i-1})c_{i-1, i} - b_{i-1}\\ (z-a_i)c_{i,i+1} - b_i \\ (z - a_{i+1}) c_{i, i+1} - b_{i+1} \\ \vdots \\ (z - a_n)c_{n-1, n} - b_n \end{array} \right\} \\ & = & \max_{i \in [n]} \left\{ \begin{array}{l} (z - a_1) \frac{b_1 - b_2}{a_2 - a_1} - b_1 \,, \\ \vdots\\ (z - a_{i-1})\frac{b_{i-1} - b_i}{a_i - a_{i-1}} - b_{i-1}\\ (z-a_i)\frac{b_i - b_{i+1}}{a_{i+1} - a_i} - b_i \\ (z - a_{i+1}) \frac{b_i - b_{i+1}}{a_{i+1} - a_i} - b_{i+1} \\ \vdots \\ (z - a_n)\frac{b_{n-1} - b_n}{a_n - a_{n-1}} - b_n \end{array} \right\} \,. \\ \end{array}$$

Note that for $j < i$, $z - a_j > z - a_i > 0$ due to the fact that $a_1 < \dots < a_n$. Similarly, for $j > i$, $z - a_j < 0 < z - a_i$. With the information above, it's very unclear to me how one could evaluate this expression further to get the result of Boyd and Vandenberghe.

$\endgroup$
  • 1
    $\begingroup$ Check Rockafellar's Convex Analysis. It is true even in $\mathbb{R}^n$ but the proof is not trivial. I guess it is easier on the real line. $\endgroup$ – max_zorn Sep 15 '18 at 22:32
  • $\begingroup$ @max_zorn Never mind, it's pp. 107-108 (of the 1972 2nd edition/printing) $\endgroup$ – Chill2Macht Sep 16 '18 at 1:12
  • 1
    $\begingroup$ This should follow from max-min representation of piecewise linear functions. $\endgroup$ – dohmatob Sep 16 '18 at 15:30
  • $\begingroup$ @dohmatob Could you please elaborate on what you mean by this? I don't understand unfortunately. The piecewise linear question was originally written as a maximum of linear functions (see this question: math.stackexchange.com/questions/2914567/… ), but it's not clear to me how to use that information. $\endgroup$ – Chill2Macht Sep 16 '18 at 18:17
1
$\begingroup$

Consider any $a_i, a_{i+1}$ and $z \in [a_i, a_{i+1}]$. No doubt, that

$$ f(x) = \begin{cases} a_ix+b_i, & x \in [\frac{b_{i-1}-b_i}{a_i - a_{i-1}};\ \frac{b_{i}-b_{i+1}}{a_{i+1} - a_{i}}]=c_i \\ a_{i+1}x+b_{i+1}, & x \in [\frac{b_{i}-b_{i+1}}{a_{i+1} - a_{i}};\ \frac{b_{i+1}-b_{i+2}}{a_{i+2} - a_{i+1}}]= c_{i+1} \end{cases} $$

We are interested in calculating

$$ f^*(z)=\sup_{x}\ (xz-\max_j(a_jx+b_j)) $$


Step 1. Let's prove, that

$$ \sup_{c_i \cup c_{i+1}}\ (xz-\max_{j = i, i+1 }(a_jx+b_j)) = x^*z-a_ix^*-b_i = x^*z-a_{i+1}x^*-b_{i+1} $$

where $x^* = \frac{b_{i}-b_{i+1}}{a_{i+1} - a_{i}}$. Since $c_i \cup c_{i+1}$ is a compact, we can write $max$ instead of $sup$. Since $z - a_i >0$:

$$ \text{argmax}_{c_i}\ (xz-a_ix-b_i) = \text{argmax}_{c_i}\ (x(z-a_i)-b_i) =x^* $$

And because $z - a_{i+1} < 0$:

$$ \text{argmax}_{c_{i+1}}\ (xz-a_{i+1}x-b_{i+1}) = \text{argmax}_{c_{i+1}}\ (x(z-a_{i+1})-b_{i+1}) =x^* $$

It's true, that $a_ix^*+b_i = a_{i+1}x^*+b_{i+1}$. Q.E.D.


Step 2.

It remains only to prove, that the following is true:

$$ \sup_{R\setminus \{c_i, c_{i+1}\}}\ (xz-f(x)) < \sup_{c_i \cup c_{j+1}}\ (xz-\max_{j = i, i+1}(a_jx+b_j)) = $$

Define $c_1 = [- \infty; \frac{b_1-b_2}{a_2-a_1}]$, $c_2 = [\frac{b_1-b_2}{a_2-a_1}; \frac{b_2-b_3}{a_3-a_2}]$. Since $z-a_1 > 0, z-a_2 > 0$:

$$ \sup_{c_1}\ (xz-a_1x-b_1) = \sup_{c_1}\ (x(z-a_1)-b_1) = \frac{b_1-b_2}{a_2-a_1}(z-a_1)-b_1 = \frac{b_1-b_2}{a_2-a_1}(z-a_2)-b_2 $$

$$ \sup_{c_2}\ (xz-a_2x-b_2) = \sup_{c_2}\ (x(z-a_2)-b_2) = \frac{b_2-b_3}{a_3-a_2}(z-a_2)-b_2 $$

No doubt, that

$$ \sup_{c_1} < \sup_{c_2} $$

By induction you can verify, that if $z \in [a_i; a_{i+1}]$

$$ \sup_{c_1} < \sup_{c_2} < ... < \sup_{c_i} $$

That's why we have the following:

$$ \sup_{c_1 \cup c_2 \cup ...\cup c_{i-1}} < \sup_{c_i \cup c_{i+1}} $$

Similarly, one can check, that:

$$ \sup_{c_{i+2} \cup c_{i+3} \cup ...\cup c_n} > \sup_{c_i \cup c_{i+1}} $$

Q.E.D.


All in all, we show, that

$$ \sup_{x}\ (xz-\max_j(a_jx+b_j)) = x^*z-a_ix^*-b_i $$

I don't think that is very strict and elegant proof, but I hope, that it is at least correct.

$\endgroup$

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.