Encontrar los $c_i$s que maximizan $\sum_{i=1}^{r}c_i^2\sigma_i^2$ donde $\sigma_1^2 \ge \sigma_2^2 \ge ...$ y $\sum_{i=1}^{r}c_i^2 =1$

Question

Puedo explicar la solución de la ecuación anterior en inglés simple, pero no sé cómo explicarlo matemáticamente. Es obvio que porque $\sigma_1^2$ es mayor que otros $\sigma_i^2$s, si establecemos $c_1=1$ y $c_i=0$ para todos los $i \ne 1$, la función convexa se maximiza. ¿Pero podrías guiarme sobre cómo expresar esto matemáticamente?

¡Se aceptan enfoques diferentes!

Esta pregunta es del libro "Foundations of Data Science" por Blum, Hopcroft, Kannan (página 71, Ejercicio 3.24).

Answer 1

Dado que intuitivamente conoces la respuesta, podrías demostrar que cualquier otra combinación siempre es menor o igual a ella. Esto, a su vez, es equivalente a decir que tu solución intuitiva es un máximo.

Por lo tanto, tu solución se obtiene al establecer $c_1^2=1, c_i =0,\ \forall i\neq 1$, y en ese caso, tu resultado es simplemente $\sigma_1^2$.

Ahora, consideremos otra combinación arbitraria. Debido a que $\sigma_1^2 \geq \sigma_2^2 \geq ... $, tienes

$$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$$

Por lo tanto, $$c_1^2 \sigma_1^2 + c_2^2 \sigma_2^2 + ... + c_r^2 \sigma_r^2 \leq \sigma_1^2$$ lo cual es lo que queríamos demostrar.

PD. Una historia completamente diferente sería analizar cuántas formas existen de obtener dicho máximo. Pero, creo que ese análisis está más allá del alcance de esta pregunta.

Answer 2

Sustituye $x_i = c_i^2$, entonces el objetivo es maximizar una función lineal sobre el simplejo estándar $\{ x : x_i \geq 0, \sum_i x_i = 1\}$. Dado que la región factible está acotada, hay una solución óptima en un punto extremo de la región factible. Los puntos extremos son los vectores de la base estándar $e_i$ (con un $1$ en la posición $i$ y ceros en otros lugares). El valor objetivo para $x=e_1$ es al menos tan alto como para otros puntos extremos, por lo que $x=e_1$ es óptimo.