Mínimos quadrados não negativos - Non-negative least squares
| Parte de uma série sobre |
| Análise de regressão |
|---|
| Modelos |
| Estimativa |
| Fundo |
Na otimização matemática , o problema dos mínimos quadrados não negativos ( NNLS ) é um tipo de problema de mínimos quadrados restritos em que os coeficientes não podem se tornar negativos. Ou seja, dada uma matriz A e um vetor (coluna) de variáveis de resposta y , o objetivo é encontrar
- sujeito a x ≥ 0 .
Aqui, x ≥ 0 significa que cada componente do vetor x deve ser não negativo, e ‖ · ‖ 2 denota a norma euclidiana .
Problemas de quadrados mínimos não negativos aparecem como subproblemas na decomposição de matrizes , por exemplo, em algoritmos para PARAFAC e matriz não negativa / fatoração de tensores . O último pode ser considerado uma generalização do NNLS.
Outra generalização do NNLS são os mínimos quadrados de variável limitada (BVLS), com limites superior e inferior simultâneos α i ≤ x i ≤ β i .
Versão de programação quadrática
O problema NNLS é equivalente a um problema de programação quadrática
onde Q = A T A e C = - A T y . Este problema é convexo , pois Q é semidefinido positivo e as restrições de não negatividade formam um conjunto convexo viável.
Algoritmos
O primeiro algoritmo amplamente usado para resolver esse problema é um método de conjunto ativo publicado por Lawson e Hanson em seu livro de 1974, Solving Least Squares Problems . Em pseudocódigo , esse algoritmo se parece com o seguinte:
- Entradas:
- uma matriz de valor real A de dimensão m × n ,
- um vetor de valor real y de dimensão m ,
- um valor real ε , a tolerância para o critério de parada.
- Inicializar:
- Defina P = ∅ .
- Defina R = {1, ..., n }.
- Defina x como um vetor totalmente zero de dimensão n .
- Defina w = A T ( y - A x ) .
- Deixe w R denotar o sub-vetor com índices de R
- Loop principal: enquanto R ≠ ∅ e max ( w R )> ε :
- Seja j em R o índice de max ( w R ) em w .
- Adicionar j a P .
- Remover j a partir de R .
- Deixe Um P ser um restrito para as variáveis incluídas na P .
- Seja s um vetor do mesmo comprimento que x . Let s P denotam o sub-vector com índices de P , e deixe s R denotam o sub-vector com índices de R .
- Defina s P = (( A P ) T A P ) −1 ( A P ) T y
- Defina s R para zero
- Enquanto min ( s P ) ≤ 0 :
- Seja α = min x i/x i - s ipara i em P onde s i ≤ 0 .
- Defina x como x + α ( s - x ) .
- Mova para R todos os índices j em P de modo que x j ≤ 0 .
- Defina s P = (( A P ) T A P ) −1 ( A P ) T y
- Defina s R como zero.
- Defina x como s .
- Defina w para A T ( y - A x ) .
- Resultado: x
Este algoritmo leva um número finito de etapas para chegar a uma solução e melhora suavemente sua solução candidata à medida que avança (para que possa encontrar boas soluções aproximadas quando cortado em um número razoável de iterações), mas é muito lento na prática, devido em grande parte a o cálculo do pseudoinverso (( A P ) T A P ) −1 . Variantes desse algoritmo estão disponíveis no MATLAB como a rotina lsqnonneg e no SciPy como optimize.nnls .
Muitos algoritmos aprimorados foram sugeridos desde 1974. Fast NNLS (FNNLS) é uma versão otimizada do algoritmo Lawson-Hanson. Outros algoritmos incluem variantes de Landweber de gradiente descendente método e optimização coordenar-sábio com base no problema de programação quadrática acima.