Finding $c_i$s that maximize $\sum_{i=1}^{r}c_i^2\sigma_i^2$ where $\sigma_1^2 \ge \sigma_2^2 \ge ...$ and $\sum_{i=1}^{r}c_i^2 =1$

Question

I can explain the solution of the above equation in plain English, but I don't know how to explain it mathematically. It is obvious that because $\sigma_1^2$ is greater then other $\sigma_i^2$s, if we set $c_1=1$ and $c_i=0$ for all $i \ne 1$, the convex function is maximized. But could you please guide me on how to express this mathematically?

Different approaches are all welcome!

This question is from the book "Foundations of Data Science" by Blum, Hopcroft, Kannan (page 71, Exercise 3.24).

Answer 1

Since you intuitively know the answer, you could show that any other combination is always less than or equal to it. This, in turn, is equivalent to saying that your intuitive solution is a maximum.

So, your solution is obtained by setting $c_1^2=1, c_i =0,\ \forall i\neq 1$, and in that case, your result is simply $\sigma_1^2$.

Now, lets consider another arbitrary combination. Because $\sigma_1^2 \geq \sigma_2^2 \geq ... $, you have

$$c_1^2 \sigma_1^2 + c_2^2 \sigma_2^2 + ... + c_r^2 \sigma_r^2 \leq c_1^2 \sigma_1^2 + c_2^2\sigma_1^2 + ... + c_r^2\sigma_1^2 = \sigma_1^2 \left(\sum_{i=1}^{r}c_i^2 \right) = \sigma_1^2$$

Thus, $$c_1^2 \sigma_1^2 + c_2^2 \sigma_2^2 + ... + c_r^2 \sigma_r^2 \leq \sigma_1^2$$ which is what we wanted to show.

PS. A complete different story would be to analize how many ways to obtain such a maximum exist. But, I think that anlysis is beyond the scope of this question.

Answer 2

Substitute $x_i = c_i^2$, then the objective is to maximize a linear function over the standard simplex $\{ x : x_i \geq 0, \sum_i x_i = 1\}$. Since the feasible region is bounded, there is an optimal solution at an extreme point of the feasible region. The extreme points are the standard basis vectors $e_i$ (with a $1$ at position $i$ and zeroes elsewhere). The objective value for $x=e_1$ is at least as high as for other extreme points, so $x=e_1$ is optimal.