¿Por qué esta función describe una bola euclidiana?

Question

En el libro de optimización convexa de Stephen Boyd, en la página 97, se puede leer :

$$ a,b \in R^n $$ $$ (1-\alpha^2)x^Tx-2(a-\alpha^2b)^Tx+a^Ta-\alpha^2b^Tb \leq 0 $$ es convexa (de hecho una bola euclidiana) si $ \alpha \leq 1 $ .

Traté de escribirlo en la forma $ (x-c)^T(x-c) \leq r^2 $ pero no lo he conseguido. ¿Cómo podemos demostrar que se trata de una bola euclidiana bajo tal condición?

Answer 1

Como dije en los comentarios, es necesario tener $|\alpha|<1$ para obtener una bola euclidiana. Para $|\alpha| = 1$ el LHS describe un plano, y la desigualdad describe todos los puntos en un lado de este plano.

Si eliges $$\boxed{c := \frac{a-\alpha^2 b}{1-\alpha^2}}$$ (que es la única opción obvia para $c$ aquí) funciona:

$(x-c)^t(x-c) = x^t -2c^tx+c^tc = x^tx-\frac{(a-\alpha^2b)^t x}{1-\alpha^2}+\frac{1}{(1-\alpha^2)^2} [a^ta-2\alpha^2a^tb+\alpha^4b^tb] \leq r^2 \tag{1}$

Ahora tienes que elegir $r$ tal que

$\frac{1}{(1-\alpha^2)^2} [a^ta-2\alpha^2a^tb+\alpha^4b^tb] - r^2 = \frac{a^ta-\alpha^2 b^t b}{1-\alpha^2} \tag{2}$

Lo que equivale a

$\begin{align*} [a^ta-2\alpha^2a^tb+\alpha^4b^tb] - (1-\alpha^2)^2r^2 &= (1-\alpha^2)(a^ta-\alpha^2 b^t b) \\ &=a^ta-\alpha^2a^ta-\alpha^2b^tb+\alpha^4b^tb \end{align*}\tag{3}$

Si se resta el lado derecho y se añade $(1-\alpha^2)r^2$ entonces lo anterior es equivalente a

$(1-\alpha^2)r^2= -2\alpha^2 a^t b + \alpha^2 a^t a + \alpha^2 b^tb = \alpha^2(a-b)^t(a-b)$ que ahora puedes resolver fácilmente para $r$ .

$$\boxed{r:= \frac{\alpha\Vert a-b\Vert}{\sqrt{1-\alpha^2}}}$$

Con estas opciones para $r$ y $c$ su ecuación es equivalente a

$$\boxed{(x-c)^t(x-c) \leq r^2}$$

Aquí un gif rápido para $n=2$ y $a = \color{red}{\bullet}$ y $b=\color{blue}{\bullet}$ como $\alpha$ va de $0$ a $1$ .