Optimalidad y mínimos cuadrados · Definición

Mínimos cuadrados lineales

optimización continuaoptimalidad y mínimos cuadrados

Antes de empezar necesitas conocer

Cuando un sistema lineal \(Ax=b\) no tiene solución exacta, buscamos el \(x\) que deja el error lo más pequeño posible. Este problema aparece en ajuste de datos, regresión y estimación.

Definición

Problema de optimización que minimiza la suma de los cuadrados de los residuos \(\|Ax-b\|_2^2\) para aproximar un vector \(b\) mediante combinaciones lineales de las columnas de \(A\).

\[\min_{x}\ \|Ax-b\|_2^2 \quad \Rightarrow \quad A^\top A\,x = A^\top b\]

La función \(f(x)=\|Ax-b\|_2^2\) es convexa, y si \(A\) tiene columnas linealmente independientes su solución es única. El gradiente \(\nabla f(x)=2A^\top(Ax-b)\) se anula exactamente en las ecuaciones normales \(A^\top A x=A^\top b\). Geométricamente, \(Ax^*\) es la proyección ortogonal de \(b\) sobre el espacio columna de \(A\).

Para ajustar la recta \(y=c_0+c_1 t\) a los puntos \((0,1),(1,2),(2,2)\), la matriz \(A\) tiene filas \((1,0),(1,1),(1,2)\) y \(b=(1,2,2)\). Las ecuaciones normales dan \(A^\top A=\begin{pmatrix}3&3\\3&5\end{pmatrix}\) y \(A^\top b=(5,6)^\top\), de donde \(c_1=\tfrac{1}{2}\) y \(c_0=\tfrac{7}{6}\).

Un error típico es resolver \(Ax=b\) con la inversa de \(A\) cuando \(A\) no es cuadrada o no es invertible. Otro error frecuente es olvidar la transpuesta en las ecuaciones normales y escribir \(AA^\top x=b\), que da una solución distinta.

Para pensar

¿Qué pasaría con los minimizadores si las columnas de \(A\) fueran linealmente dependientes?

Habría infinitas soluciones porque \(A^\top A\) sería singular, pero \(Ax^*\) seguiría siendo único.

Ejercicios 10

  1. ¿Cuál es el gradiente de \(f(x)=\|Ax-b\|_2^2\) respecto de \(x\)?
  2. ¿Cuáles son las ecuaciones normales del problema de mínimos cuadrados?
  3. Si \(A\) tiene columnas linealmente independientes, ¿cuántas soluciones tiene el problema de mínimos cuadrados?
  4. ¿Qué representa \(Ax^*\) geométricamente, siendo \(x^*\) la solución de mínimos cuadrados?
  5. Si \(A\) es una matriz \(3\times 2\), ¿cuál es la dimensión de \(A^\top A\)?
  6. Dada \(A=\begin{pmatrix}1&0\\0&1\\1&1\end{pmatrix}\) y \(b=(1,2,4)^\top\), ¿cuánto vale \(A^\top b\)?
  7. Con \(A^\top A=\begin{pmatrix}2&1\\1&2\end{pmatrix}\) y \(A^\top b=(3,3)^\top\), ¿cuál es la solución de mínimos cuadrados?
  8. Para ajustar \(y=c\,t\) (sin término independiente) a los puntos \((1,2)\) y \((2,3)\), ¿cuál es el valor de \(c\)?
  9. ¿Por qué no conviene calcular la solución de mínimos cuadrados como \(x=(A^\top A)^{-1}A^\top b\) cuando \(A^\top A\) está mal condicionada?
  10. Sea \(A=\begin{pmatrix}1&1\\1&2\\1&3\end{pmatrix}\) y \(b=(1,2,2)^\top\). Calcula la solución de mínimos cuadrados \(x^*\) y el residuo \(\|Ax^*-b\|_2^2\).

Referencias

  • Stephen Boyd, Lieven Vandenberghe, Convex Optimization, 1st edition, Cambridge University Press, 2004.
  • Jorge Nocedal, Stephen J. Wright, Numerical Optimization, 2nd edition, Springer, 2006.