Minimalizacja systemu zliczającego L1, zbiegającego się w nie-minimalnym miejscu?

Question

To jest mój pierwszy wpis do stackoverflow, więc jeśli to nie jest właściwy obszar, przepraszam. Pracuję nad zminimalizowaniem Systemu Zregionu L1.

Ten weekend to moje pierwsze nurkowanie w optymalizacji, mam podstawowy system liniowy Y = X * B, X jest macierzą n-by-p, B to wektor p-by-1 współczynników modelu i Y jest wektor wyjściowy n-by-1.

Próbuję znaleźć współczynniki modelu, zaimplementowałem algorytm spadku zarówno gradientowego jak i współrzędnych, aby zminimalizować system L1. Aby znaleźć mój rozmiar kroku, używam algorytmu cofania, kończę algorytm, patrząc na normę-2 gradientu i kończąc, jeśli jest on "wystarczająco blisko" do zera (na razie używam 0.001).

Funkcja, którą próbuję zminimalizować, jest następująca (0,5) * (norma ((Y - X * B), 2)^2) + norma lambda * (B, 1). (Uwaga: Według normy (Y, 2) mam na myśli wartość norm-2 wektora Y) Moja matryca X wynosi 150 na 5 i nie jest rozrzedzona.

Jeśli ustawię parametr lambda na zero, powinienem zbliżyć się do rozwiązania najmniejszych kwadratów, mogę sprawdzić, czy oba algorytmy robią to całkiem dobrze i dość szybko.

Jeśli zacznę zwiększać lambdę moje współczynniki modelu wszystkie zmierzają w kierunku zera, to jest to, czego się spodziewam, moje algorytmy nigdy się nie kończą, ponieważ norma-2 gradientu jest zawsze liczbą dodatnią. Na przykład lambda 1000 da mi współczynniki w zakresie 10^(- 19), ale normą2 mojego gradientu jest ~ 1,5, to jest po kilku tysiącach iteracji, podczas gdy moje wartości gradientu zbiegają się do czegoś w 0 do 1 zakres, mój rozmiar kroku staje się bardzo mały (zakres 10^(- 37)). Jeśli pozwolę, aby algorytm działał dłużej, sytuacja się nie poprawi, wydaje się, że utknął w jakiś sposób.

Zarówno moje algorytmy pochylenia i współrzędnych zbiegają się w tym samym punkcie i nadają tę samą wartość norm2 (gradient) warunku zakończenia. Działają też całkiem dobrze z lambdą równą 0. Jeśli używam bardzo małej wartości lambda (na przykład 0,001), uzyskuję zbieżność, lambda równa się 0,1, wygląda na to, że zbiegnie się, gdybym ją uruchomił przez godzinę lub dwie, a lambda była większa i Stopień konwergencji jest tak mały, że jest bezużyteczny.

Miałem kilka pytań, które według mnie mogą mieć związek z problemem?

Przy obliczaniu gradientu używam metody różnic skończonych (f (x + h) - f (x-h))/(2h)) z h wynoszącym 10^(- 5). Jakieś przemyślenia na temat tej wartości h?

Inna myśl polegała na tym, że przy tych bardzo małych krokach porusza się tam iz powrotem w kierunku zbliżonym do ortogonalnego do minimum, co sprawia, że ​​stopień zbieżności jest tak wolny, że jest bezużyteczny.

Moja ostatnia myśl była taka, że ​​być może powinienem użyć innej metody zakończenia, być może patrząc na stopę konwergencji, jeśli stopień konwergencji jest bardzo wolny, a następnie zakończyć. Czy jest to powszechna metoda zakończenia?

Answer 1

1-norma nie jest różna. Spowoduje to zasadnicze problemy z wieloma rzeczami, w szczególności z testem zakończenia, który wybrałeś; gradient zmieni się drastycznie wokół twojego minimum i nie będzie istnieć na zbiorze zerowym.

Test końcowy, który naprawdę chcesz, będzie zgodny z "jest bardzo krótki wektor w subgradient."

Jest dość łatwo znaleźć najkrótszy wektor w podgradientu || Ax-b || _2^2 + lambda || x || _1.Wybierz mądrze, tolerancję eps i wykonać następujące czynności:

1. Compute v = grad(||Ax-b||_2^2).

2. Jeśli x[i] < -eps, a następnie odjąć od v[i] lambda. Jeśli x[i] > eps, dodaj lambda do v[i]. Jeśli jest to -eps <= x[i] <= eps, dodaj numer w [-lambda, lambda] do v[i], który minimalizuje v[i].

Możesz wykonać test końcowy tutaj, traktując v jako gradient. Zalecam również użycie gradientu v przy wyborze miejsca, w którym powinien się znajdować następny iterat.