Mínimos cuadrados no negativos

En optimización matemática , el problema de 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 ^[1]

${\displaystyle \operatorname {arg\,min} \limits _{\mathbf {x} }\|\mathbf {Ax} -\mathbf {y} \|_{2}^{2}}$sujeto a x ≥ 0 .

Aquí x ≥ 0 significa que cada componente del vector x debe ser no negativo, y ‖·‖ ₂ denota la norma euclidiana .

Los problemas de mínimos cuadrados no negativos aparecen como subproblemas en la descomposición matricial , por ejemplo, en algoritmos para PARAFAC ^[2] y factorización matricial/tensor no negativa . ^{[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

${\displaystyle \operatorname {arg\,min} \limits _{\mathbf {x\geq 0} }\left({\frac {1}{2}}\mathbf {x} ^{\mathsf {T}}\mathbf {Q} \mathbf {x} +\mathbf {c} ^{\mathsf {T}}\mathbf {x} \right),}$

donde Q = A ^T A y c = − A ^T y . Este problema es convexo , ya que Q es semidefinido positivo y las restricciones de no negatividad forman un conjunto convexo factible. ^[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:
  • Establecer 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: while R ≠ ∅ y max( w ^R ) > ε :
  • Sea j en R el índice de max( w ^R ) en w .
  • Agregue j a P .
  • Retire j de R .
  • Sea A ^P A restringido a las variables incluidas en P .
  • Sea s un vector de la misma longitud que x . Sea s ^P el subvector con índices de P y sea s ^R el subvector con índices de R .
  • Conjunto s ^P = (( A ^P ) ^T A ^P ) ⁻¹ ( A ^P ) ^T y
  • Establecer s ^R a cero
  • Mientras min( s ^P ) ≤ 0 :
    • Sea α = mín. xyo_​/x _yo - s _yopara i en P donde s _i ≤ 0 .
    • Establezca x en x + α ( s − x ) .
    • Mover a R todos los índices j en P tales que x _j ≤ 0 .
    • Conjunto s ^P = (( A ^P ) ^T A ^P ) ⁻¹ ( 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 ^{[8] [1]} y en SciPy como optimiza.nnls . ^[9]

Desde 1974 se han sugerido muchos algoritmos mejorados. ^[1] Fast NNLS (FNNLS) es una versión optimizada del algoritmo de Lawson-Hanson. ^[2] Otros algoritmos incluyen variantes del método de descenso de gradiente de Landweber ^[10] y optimización de coordenadas basada en el problema de programación cuadrática anterior. ^[7]

Ver también

• matriz M
• Teorema de Perron-Frobenius

Referencias

1. 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 .
2. Hermano, Rasmus; De Jong, Sijmen (1997). "Un algoritmo rápido de mínimos cuadrados sin restricciones de 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.
3. Lin, Chih-Jen (2007). "Métodos de gradiente proyectado para la 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. 
4. 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.
5. Lawson, Charles L.; Hanson, Richard J. (1995). "23. Mínimos cuadrados lineales con restricciones de desigualdad lineal". Resolución de problemas de mínimos cuadrados. SIAM. pag. 161. doi :10.1137/1.9781611971217.ch23. ISBN 978-0-89871-356-5.
6. Rígido, Philip B.; Parker, Robert L. (1995). "Mínimos cuadrados de variables acotadas: un algoritmo y aplicaciones" (PDF) . Estadística Computacional . 10 : 129.
7. 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 sobre informática. vol. 3691, págs. 407–414. doi :10.1007/11556121_50. ISBN 978-3-540-28969-2.
8. "lsqnonneg". DocumentaciónMATLAB . Consultado el 28 de octubre de 2022 .
9. "scipy.optimize.nnls". Guía de referencia de SciPy v0.13.0 . Consultado el 25 de enero de 2014 .
10. Johansson, BR; Elfving, T.; Kozlov, V.; Censor, Y.; Forssen, 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 .