Resolver
Maximizar $f(x)=c^Tx$
con sujeción a $x^TQx \leq 1$
donde $Q$ es una matriz definida positiva.
¿cuál es la solución si se quiere minimizar la función objetivo?
Respuesta
¿Demasiados anuncios?
Escribe $Q=P^TDP$ , donde $D={\rm diag}(\lambda_1,\dots,\lambda_n)$ y $P^T=P^{-1}$ . Dado que todos los $\lambda_i$ son positivos, la matriz $D^{1/2}={\rm diag}(\sqrt{\lambda_1},\dots,\sqrt{\lambda_n})$ está bien definida y satisface $(P^TD^{1/2}P)^2=Q$ . Por lo tanto, podemos utilizar la notación (bien conocida) $$ Q^{1/2}=P^TD^{1/2}P. $$ Entonces $$ \qquad x^TQx = x^TQ^{1/2}Q^{1/2}x = \Vert Q^{1/2}x\Vert_2^2.\qquad(1) $$ Por lo tanto, para $y=Q^{1/2}x$ y $d=Q^{-1/2}c$ el problema se puede replantear como $$ \begin{matrix} \rm maximize &d^Ty\\ \rm subject\ to &\Vert y\Vert_2^2\le 1, \end{matrix} $$ que alcanza su punto óptimo en $d/\Vert d\Vert_2$ en virtud de la desigualdad de Cauchy-Schwartz $|u^Tv|\le\Vert u\Vert_2\Vert v\Vert_2$ (la desigualdad implica que $d^Ty\le\Vert d\Vert_2$ si $\Vert y\Vert_2\le 1$ con igualdad para $y=d/\Vert d\Vert_2$ ). Así, la solución del problema original es $$ \Vert d\Vert_2 = \Vert Q^{-1/2}c\Vert_2, $$ alcanzado en el punto óptimo $$ y^* = \frac{Q^{-1/2}c}{\Vert Q^{-1/2}c\Vert_2}, $$ que puede reescribirse como $$ x^* = \frac{Q^{-1}c}{\sqrt{c^TQ^{-1}c}} $$ porque $\Vert Q^{-1/2}c\Vert_2=\sqrt{c^TQ^{-1/2}Q^{-1/2}c}$ .
Nota: En el caso de la minimización el punto óptimo es $-x^*$ y el valor óptimo es $-\Vert d\Vert_2$ . Para ver esto basta con utilizar el otro extremo de la desigualdad de Cauchy-Schwartz, que implica $d^Ty\ge-\Vert d\Vert_2$ si $\Vert y\Vert_2\le1$ con igualdad para $y=-d/\Vert d\Vert_2$ .
