Nieujemne najmniejsze kwadraty

W optymalizacji matematycznej problem nieujemnych najmniejszych kwadratów ( NNLS ) jest rodzajem ograniczonego problemu najmniejszych kwadratów , w którym współczynniki nie mogą stać się ujemne. Oznacza to, że mając macierz A i (kolumnowy) wektor zmiennych odpowiedzi y , celem jest znalezienie

$\ Displaystyle \ nazwa operatora {arg \, min} \ ograniczenia _ {\ mathbf {x}} \|\ mathbf {Ax} -\ mathbf {y} \|_ {2} ^ {2}} z zastrzeżeniem$ x ≥ ≥ 0.

Tutaj x ≥ 0 oznacza, że ​​każda składowa wektora x powinna być nieujemna, a ‖·‖ ₂ oznacza normę euklidesową .

Nieujemne problemy najmniejszych kwadratów pojawiają się jako podproblemy w dekompozycji macierzy , np. w algorytmach dla PARAFAC i nieujemnej faktoryzacji macierzy/tensorów . To ostatnie można uznać za uogólnienie NNLS.

Innym uogólnieniem NNLS jest metoda najmniejszych kwadratów ze zmienną ograniczoną (BVLS) z jednoczesnymi górnymi i dolnymi granicami α _i ≤ x _i ≤ β _i .

Wersja programowania kwadratowego

Problem NNLS jest równoważny problemowi programowania kwadratowego

${\ Displaystyle \ nazwa operatora {arg \, min} \ ograniczenia _ {\ mathbf {x \ geq 0}} \ lewo ({{ \frac {1}{2}}\mathbf {x} ^{\mathsf {T}}\mathbf {Q} \mathbf {x} +\mathbf {c} ^{\mathsf {T}}\mathbf {x } \Prawidłowy),}$

gdzie Q = ZA ^T ZA i do = - ZA ^T y . Ten problem jest wypukły , ponieważ Q jest dodatnio półokreślony , a ograniczenia nieujemne tworzą wypukły możliwy zbiór.

Algorytmy

Pierwszym szeroko stosowanym algorytmem do rozwiązania tego problemu jest metoda zbioru aktywnego opublikowana przez Lawsona i Hansona w ich książce Solving Least Squares Problems z 1974 roku . W pseudokodzie ten algorytm wygląda następująco:

• Wejścia:
  • A o wartościach rzeczywistych o wymiarze m × n ,
  • wektor o wartościach rzeczywistych y o wymiarze m ,
  • wartość rzeczywista ε , tolerancja dla kryterium zatrzymania.
• Zainicjuj:
  • Ustaw P = ∅ .
  • Ustaw R = {1, ..., n }.
  • Ustaw x na całkowicie zerowy wektor o wymiarze n .
  • Zestaw w = ZA ^T ( y - ZA x ) .
  • Niech w ^R oznacza podwektor z indeksami z R
• Główna pętla: while R ≠ ∅ i max( w ^R ) > ε :
  • Niech j w R będzie indeksem max( w ^R ) w w .
  • Dodaj j do P. _
  • Usuń j z R .
  • Niech A ^P będzie A ograniczone do zmiennych zawartych w P .
  • Niech s będzie wektorem tej samej długości co x . Niech s ^P oznacza podwektor o indeksach z P , a s ^R oznacza podwektor o indeksach z R .
  • Zestaw s ^P = (( ZA ^P ) ^T ZA ^P ) ^-1 ( ZA ^P ) ^T y
  • Ustaw sR ^na zero
  • Podczas gdy min( s ^P ) ≤ 0 :
    • Niech α = min x _ja / x _ja - s _ja dla ja w P gdzie s _ja ≤ 0 .
    • Ustaw x na x + α ( s - x ) .
    • Przenieś do R wszystkie indeksy j w P takie, że x _j ≤ 0 .
    • Zestaw s ^P = (( ZA ^P ) ^T ZA ^P ) ^-1 ( ZA ^P ) ^T y
    • Ustaw sR ^na zero.
  • Ustaw x na s .
  • Ustaw w na ZA ^T ( y - ZA x ) .
• Wyjście: x

Algorytm ten wykonuje skończoną liczbę kroków, aby dojść do rozwiązania i płynnie ulepsza rozwiązanie kandydujące w miarę postępów (dzięki czemu może znaleźć dobre przybliżone rozwiązania po odcięciu w rozsądnej liczbie iteracji), ale w praktyce jest bardzo powolny, głównie dzięki obliczenie pseudoodwrotności ( ( AP ) ^T A ^P ) ^{−1 .} Warianty tego algorytmu są dostępne w MATLAB- ie jako rutyna lsqnonneg , aw SciPy jako optymalizacja.nnls .

Od 1974 roku zaproponowano wiele ulepszonych algorytmów. Fast NNLS (FNNLS) to zoptymalizowana wersja algorytmu Lawsona-Hansona. Inne algorytmy obejmują warianty opadania gradientu Landwebera i optymalizację pod kątem współrzędnych w oparciu o powyższy problem programowania kwadratowego.

Zobacz też

• macierz M
• Twierdzenie Perrona-Frobeniusa