Problema cuadrático convexo grande y mal condicionado

Question

Necesito resolver numéricamente un problema cuadrático convexo:

$\min f(x) = \frac{1}{2} x^\top A x - b^\top x$ ,

donde $A$ es una matriz semipositiva definida muy grande y mal condicionada. El típico método del gradiente conjugado no funciona bien. El SGD es demasiado lento.

Estoy buscando un buen método numérico con un esfuerzo computacional relativamente menor.

¿Alguna experiencia o sugerencia? Gracias.

Answer 1

Asumo que está buscando minimizar $f(x)$ y que $A$ es simétrica y semidefinida positiva.

• Si $b \notin Null(A)^{\perp}$ entonces hay un vector $v \in Null(A)$ tal que $b^Tv \neq 0$ . Sin pérdida de generalidad, supongamos que $b^Tv >0$ (si no, multiplicar $v$ por $-1$ ). Entonces para todos los números reales $\theta$ nos encontramos con que: $$ f(\theta v) = 0 + (\theta)(-b^Tv)$$ así que $\lim_{\theta\rightarrow\infty} f(\theta v) = -\infty$ y no existe ningún minimizador.

• Otra cosa, $b \in Null(A)^{\perp} = Col(A^T) = Col(A)$ . Sólo hay que encontrar cualquier vector $r$ tal que $Ar=b$ . Entonces: \begin {align} \frac {1}{2}(x-r)^TA(x-r) &= \frac {1}{2}x^TAx - x^TAr + \frac {1}{2}r^TAr \\ &= f(x) + \frac {1}{2}r^TAr \end {align} y esto se minimiza claramente en $x^*=r$ Así que $$ f(x^*) = f(r) = -\frac{1}{2}r^TAr$$

  ---

En otras palabras, el problema se reduce a la eliminación gaussiana: Encontrar un vector $r$ tal que $Ar=b$ . Si no hay tal $r$ existe, entonces no existe ningún minimizador.