Dejemos que $a \in \mathbb R^n$ y $\Sigma$ sea una matriz positiva definida de tamaño $n$ .
¿Cuál es el valor de forma cerrada de
$$\min_{\|x\|_\Sigma \le 1}\|x\|_1 - x^Ta, $$
donde $\|x\|_\Sigma := \sqrt{x^T\Sigma x}$ es la norma inducida por el producto interior $(x, y) \mapsto x^T\Sigma y$ ?
Se ha sugerido en los comentarios que el valor de la solución podría no ser expresable analíticamente en general, pero que hay alguna esperanza, cuando la matriz $\Sigma$ es diagonal. Voy a proporcionar una solución a continuación. Además, se me da mal utilizar las multiplicaciones de Lagrange (por ejemplo, siempre me equivoco con los signos, etc.). Voy a intentar una solución más "sintética".
Ahora, utilizando la representación dual del $\ell_1$ -norma, se tiene
$$ \begin{split}\alpha:=\min_{\|z\|_\Sigma \le 1} \|z\|_1 - z^Ta &= \min_{\|z\|_\Sigma \le 1}\max_{\|w\|_\infty \le 1}z^Tw-z^T a =\max_{\|w\|_\infty \le 1}\min_{\|z\|_\Sigma \le 1}z^T(w-a)\\ &=\max_{\|w\|_\infty \le 1}-\left(\max_{\|z\|_\Sigma \le 1}-z^T(w-a)\right)=\max_{\|w\|_\infty \le 1}-\|w-a\|_{\Sigma^{-1}}\\ &=-\min_{\|w\|_\infty \le 1}\|w-a\|_{\Sigma^{-1}}, \end{split} $$
donde he utilizado Teorema minimax de Sion para intercambiar el mínimo y el máximo. La expresión anterior para el valor objetivo óptimo $\alpha$ es poco probable que se pueda calcular analíticamente en general, debido a la no separabilidad del objetivo (aunque la restricción es perfectamente separable como producto de restricciones 1D).
En cualquier caso, de la visualización anterior se deduce que $\alpha \le 0$ con igualdad si $\|a\|_\infty \le 1$ .
En el caso especial de que $\Sigma=\text{diag}(\sigma_1,\ldots,\sigma_2)$ el cuadrado del valor objetivo óptimo $\alpha^2$ puede separarse como
$$ \alpha \le 0,\;\alpha^2 = \sum_{i=1}^n\min_{|w_i| \le 1}\sigma_i^{-2}(w_i-a_i)^2 = \sum_{i=1}^n\sigma_i^{-2}\begin{cases}(a_i+1)^2,&\mbox{ if }a_i \le -1,\\ 0,&\mbox{ if }-1 < a_i \le 1,\\ (a_i-1)^2,&\mbox{ if }a_i > 1,\end{cases} $$
que es, efectivamente, una fórmula analítica, aunque muy "peliaguda".
Dejemos que $\sigma_n \ge \ldots \ge \sigma_2 \ge \sigma_1 > 0$ sean los valores propios de $\Sigma$ . Entonces, uno tiene $$ \sigma_n^{-1}\|w-a\|_2 \le \|w-a\|_{\Sigma^{-1}} \le \sigma_1^{-1}\|w-a\|_2. $$ Así, se tienen los límites
$-\sqrt{\gamma/\sigma_1} \le \alpha \le -\sqrt{\gamma/\sigma_n}$ , donde $\gamma := \sum_{i=1}^n\begin{cases}(a_i+1)^2,&\mbox{ if }a_i \le -1,\\ 0,&\mbox{ if }-1 < a_i \le 1,\\ (a_i-1)^2,&\mbox{ if }a_i > 1.\end{cases}$
Además, si $\|a\|_\infty > 1$ entonces no es difícil ver que $\gamma \le n(\|a\|_\infty-1)$ (ver detalles más abajo), desde donde $\alpha \ge -\sqrt{\gamma/\sigma_1} \ge -\sqrt{n/\sigma_1}(\|a\|_\infty-1)$ que corresponde a un límite que ha sido observado por alguien en los comentarios. Sin embargo, por construcción, este límite es potencialmente muy flojo.
Tenga en cuenta que $a_i \le -1 \implies (a_i + 1)^2 \le (\|a\|_\infty - 1)^2$ y de manera similar $a_1 > 1 \implies 0 \le (a_i - 1)^2 \le (\|a\|_\infty-1)^2$ . Así, $\gamma \le n(\|a\|_\infty-1)$ .
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
