1

I was working through the exercises of chapter 3 from Boyd & Vandenberghe's Convex Optimization but I'm a bit confused by the solution for Ex 3.19(a). It says that:-

for $\alpha_1 \geq \alpha_2 \geq \alpha_3 \geq ... \geq \alpha_r \geq 0$ and $x_{[i]}$ denotes the $i^{th}$ largest component of $x$,

\begin{alignat*}{1} f(x) &= \sum_{i=1}^{r} \alpha_ix_{[i]}\\ &= \alpha_r(x_{[1]}+x_{[2]}+\ldots+x_{[r]}) + (\alpha_{r-1}-\alpha_r)(x_{[1]}+x_{[2]}+\ldots+x_{[r-1]}) \\ &\hspace{5mm}+ (\alpha_{r-2}-\alpha_{r-1})(x_{[1]}+x_{[2]}+\ldots+x_{[r-2]}) + \ldots + (\alpha_1-\alpha_2)x_{[1]} \end{alignat*}

I cant seem to understand how these two are equivalent. Any additional steps in between would be appreciated. Thank you.

jjcluu
  • 153
Hazard
  • 191
  • 1
    if you combine the first two terms in the last expression, they simplify to $$\alpha_r x_{[[r]}+\alpha_{r-1}(x_{[1]}+x_{[2]}+\cdots +x_{[r-1]}).$$ If you combine the second term with the $(\alpha_{r-2}-\alpha_{r-1})$ term, then it seems that the cancellation leaves $\alpha_{r-1} x_{[r-1]}$ behind along with an $\alpha_{r-2}$ term. So at each step you're picking up another $\alpha_i x_{[i]}$ term in descending order. – Semiclassical Mar 03 '21 at 20:52

1 Answers1

1

The right hand side of your equation is what's known as a telescoping sum, in which pairs of consecutive terms cancel. For instance, notice that adding the first two terms gives:

$$ a_r (x_{[1]} + \cdots + x_{[r]}) + (a_{r-1} + a_r)(x_{[1]} + \cdots + x_{[r-1]}) = a_r x_{[r]} + a_{r-1}(x_{[1]} + \cdots + x_{[r-1]}) $$

Then, adding the third term gives,

$$ a_r x_{[r]} + a_{r-1} x_{[r-1]} + a_{r-2}(x_{[1]} + \cdots + x_{[r-2]}) $$

And so on. Hence after adding all $r$ terms the sum collapses, and you are left with

$$ a_r x_{[r]} + a_{r-1} x_{[r-1]} + \cdots + a_1 x_{[1]} = \sum_{i=1}^r a_i x_{[i]}$$

Bean
  • 144