Mínimos cuadrados no negativos - Non-negative least squares
| Parte de una serie sobre |
| Análisis de regresión |
|---|
| Modelos |
| Estimacion |
| Fondo |
En optimización matemática , el problema de los mínimos cuadrados no negativos ( NNLS ) es un tipo de problema de mínimos cuadrados restringidos en el que no se permite que los coeficientes se vuelvan negativos. Es decir, dada una matriz A y un vector (columna) de variables de respuesta y , el objetivo es encontrar
- sujeto ax ≥ 0 .
Aquí x ≥ 0 significa que cada componente del vector x debe ser no negativo, y ‖ · ‖ 2 denota la norma euclidiana .
Los problemas de mínimos cuadrados no negativos aparecen como subproblemas en la descomposición de matrices , por ejemplo, en algoritmos para PARAFAC y factorización de tensor / matriz no negativa . Este último puede considerarse una generalización de NNLS.
Otra generalización de NNLS son los mínimos cuadrados de variables acotadas (BVLS), con límites superior e inferior simultáneos α i ≤ x i ≤ β i .
Versión de programación cuadrática
El problema NNLS es equivalente a un problema de programación cuadrática
donde Q = A T A y c = - A T y . Este problema es convexo , ya que Q es semidefinito positivo y las restricciones de no negatividad forman un conjunto factible convexo.
Algoritmos
El primer algoritmo ampliamente utilizado para resolver este problema es un método de conjunto activo publicado por Lawson y Hanson en su libro de 1974 Solving Least Squares Problems . En pseudocódigo , este algoritmo tiene el siguiente aspecto:
- Entradas:
- una matriz A de valor real de dimensión m × n ,
- un vector de valor real y de dimensión m ,
- un valor real ε , la tolerancia para el criterio de parada.
- Inicializar:
- Establezca P = ∅ .
- Establezca R = {1, ..., n }.
- Establezca x en un vector todo cero de dimensión n .
- Establezca w = A T ( y - A x ) .
- Sea w R el subvector con índices de R
- Bucle principal: mientras R ≠ ∅ y max ( w R )> ε :
- Sea j en R el índice de max ( w R ) en w .
- Añadir j a P .
- Eliminar j de R .
- Deje A P sea un restringido a las variables incluidas en P .
- Sea s un vector de la misma longitud que x . Let s P denota el sub-vector con índices de P , y dejar que s R denotan la sub-vector con índices de R .
- Establezca s P = (( A P ) T A P ) −1 ( A P ) T y
- Ponga s R a cero
- Mientras min ( s P ) ≤ 0 :
- Sea α = min x yo/x i - s ipara i en P donde s i ≤ 0 .
- Establezca x en x + α ( s - x ) .
- Mueva a R todos los índices j en P tales que x j ≤ 0 .
- Establezca s P = (( A P ) T A P ) −1 ( A P ) T y
- Establezca s R en cero.
- Establezca x en s .
- Establezca w en A T ( y - A x ) .
- Salida: x
Este algoritmo toma un número finito de pasos para llegar a una solución y mejora suavemente su solución candidata a medida que avanza (para que pueda encontrar buenas soluciones aproximadas cuando se corta en un número razonable de iteraciones), pero es muy lento en la práctica, debido en gran parte a el cálculo de la pseudoinversa (( A P ) T A P ) −1 . Las variantes de este algoritmo están disponibles en MATLAB como la rutina lsqnonneg y en SciPy como optimizar.nnls .
Se han sugerido muchos algoritmos mejorados desde 1974. Fast NNLS (FNNLS) es una versión optimizada del algoritmo de Lawson-Hanson. Otros algoritmos incluyen variantes de Landweber 's descenso de gradiente método y optimización de coordenadas en cuanto basa en el problema de programación cuadrática anterior.