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 donde 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 [1]
- 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 matricial , por ejemplo, en los algoritmos para PARAFAC [2] y la factorización no negativa de la matriz / tensor . [3] [4] Este último puede considerarse una generalización de NNLS. [1]
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 . [5] : 291 [6]
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. [7]
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 . [5] : 291 En pseudocódigo , este algoritmo tiene el siguiente aspecto: [1] [2]
- 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 . [1] Las variantes de este algoritmo están disponibles en MATLAB como la rutina lsqnonneg [1] y en SciPy como optimizar.nnls . [8]
Se han sugerido muchos algoritmos mejorados desde 1974. [1] Fast NNLS (FNNLS) es una versión optimizada del algoritmo de Lawson-Hanson. [2] Otros algoritmos incluyen variantes de Landweber 's descenso de gradiente método [9] y la optimización de coordenadas-sabia basa en el problema de programación cuadrática anteriormente. [7]
Ver también
Referencias
- ^ a b c d e f Chen, Donghui; Plemmons, Robert J. (2009). Restricciones de no negatividad en el análisis numérico . Simposio sobre el nacimiento del análisis numérico. CiteSeerX 10.1.1.157.9203 .
- ^ a b c Hermano, Rasmus; De Jong, Sijmen (1997). "Un algoritmo rápido de mínimos cuadrados con restricciones de no negatividad". Revista de quimiometría . 11 (5): 393. doi : 10.1002 / (SICI) 1099-128X (199709/10) 11: 5 <393 :: AID-CEM483> 3.0.CO; 2-L .
- ^ Lin, Chih-Jen (2007). "Métodos de gradiente proyectado para factorización de matrices no negativas" (PDF) . Computación neuronal . 19 (10): 2756–2779. CiteSeerX 10.1.1.308.9135 . doi : 10.1162 / neco.2007.19.10.2756 . PMID 17716011 .
- ^ Boutsidis, Christos; Drineas, Petros (2009). "Proyecciones aleatorias para el problema de mínimos cuadrados no negativos". Álgebra lineal y sus aplicaciones . 431 (5–7): 760–771. arXiv : 0812.4547 . doi : 10.1016 / j.laa.2009.03.026 .
- ^ a b Lawson, Charles L .; Hanson, Richard J. (1995). Resolver problemas de mínimos cuadrados . SIAM.
- ^ Stark, Philip B .; Parker, Robert L. (1995). "Mínimos cuadrados de variables acotadas: un algoritmo y aplicaciones" (PDF) . Estadística computacional . 10 : 129.
- ^ a b Franc, Vojtěch; Hlaváč, Václav; Navara, Mirko (2005). Algoritmo secuencial de coordenadas para el problema de mínimos cuadrados no negativos . Análisis informático de imágenes y patrones . Apuntes de conferencias en informática. 3691 . págs. 407–414. doi : 10.1007 / 11556121_50 . ISBN 978-3-540-28969-2.
- ^ "scipy.optimize.nnls" . Guía de referencia de SciPy v0.13.0 . Consultado el 25 de enero de 2014 .
- ^ Johansson, BR; Elfving, T .; Kozlov, V .; Censor, Y .; Forssén, PE; Granlund, GS (2006). "La aplicación de un método Landweber de proyección oblicua a un modelo de aprendizaje supervisado" . Modelado matemático e informático . 43 (7–8): 892. doi : 10.1016 / j.mcm.2005.12.010 .