Nieliniowe najmniejszych kwadratów z ograniczeniami ramek

10

Jakie są zalecane sposoby wykonywania nieliniowych najmniejszych kwadratów, min $\sum err_i(p)^2$ , z ograniczeniami ramek $lo_j <= p_j <= hi_j$ ? Wydaje mi się (głupcy się spieszą), że można by uczynić kwadratowe ograniczenia kwadratowymi i zminimalizować

\sum_{i} e r r_{i} (p)^{2} + C * \sum_{j} t u b (p_{j}, l o_{j}, h i_{j})^{2}

$\sum_i err_i(p)^2 + C * \sum_j tub( p_j, lo_j, hi_j )^2$ gdzie

t u b (x, l o, h i)

$tub( x, lo, hi )$ jest „funkcją wanny” w kształcie \ ___ /,

m a x (l o - x, 0, x - h i)

$max( lo - x, 0, x - hi )$ .
Czy to działa w teorii, czy w praktyce?
(Wydaje się, że istnieje wiele wielu prac teoretycznych na temat NLS +, ale moje zainteresowanie jest praktyczne -
rzeczywiste lub realistyczne przypadki testowe pomogłyby mi wybrać jedną z metod).

(Eksperci, proszę dodać tagi: „najmniejszych kwadratów”?)

optimization constraints denis
źródło

5

Zastępowanie ścisłych ograniczeń funkcjami karnymi jest powszechną techniką optymalizacji numerycznej. Wydaje się, że to, co proponujesz, jest szczególną formą tej zamiany. Możesz przeczytać wszystko o podobnych technikach, np. Tutaj: stanford.edu/~boyd/cvxbook

David Ketcheson

p

$p$

p_{i} = min (max (l o_{j}, p_{j}^{'}), h i_{j})

$p_i=\min(\max(lo_j, p'_j),hi_j)$

11

Dodanie kwadratowych warunków kary, aby pozbyć się ograniczeń, jest prostym podejściem zapewniającym dokładność rzędu 1 / współczynnik kary. Dlatego nie jest to zalecane ze względu na wysoką dokładność, chyba że pozwolisz, aby kara spadła do nieskończoności podczas obliczeń. Ale wysoki współczynnik kary powoduje, że Hesjan jest bardzo nieuzasadniony, co ogranicza całkowitą dokładność możliwą do osiągnięcia bez wyraźnego uwzględnienia ograniczeń.

Należy pamiętać, że ograniczenia ograniczone są znacznie łatwiejsze do opanowania niż ograniczenia ogólne, dlatego praktycznie nigdy nie są przekształcane w kary.

Solver L-BFGS-B (używany z historią około 5-wymiarową) zazwyczaj rozwiązuje ograniczone problemy bardzo niezawodnie i szybko w obu niskich wysokich wymiarach. Wyjątkiem są nieporozumienia dotyczące problemów, które mogą stać się bardzo płaskie z dala od rozwiązań, w których łatwo utknąć przy zejściu.

Przeprowadziliśmy wiele eksperymentów na bardzo różnych funkcjach w wielu różnych wymiarach, z wieloma dostępnymi solverami, ponieważ potrzebowaliśmy bardzo solidnego solvera z ograniczonymi ograniczeniami w ramach naszego globalnego oprogramowania optymalizacyjnego. L-BFGS-B wyraźnie wyróżnia się jako metoda ogólnego zastosowania, choć oczywiście w przypadku problemów z małymi innymi rozwiązaniami działają znacznie lepiej. Dlatego poleciłbym L-BFGS-B jako pierwszy wybór i wypróbowałbym alternatywne techniki na wypadek, gdyby L-BFGS-B źle radził sobie z określoną klasą problemów.

Arnold Neumaier
źródło

L-BFGS jest dostępny w IPOPT, poprawiłem swoją odpowiedź.

Ali

5

Chciałbym po prostu użyć uniwersalnego solvera NLP IPOPT . Jest to najbardziej niezawodny solver spośród tych, których próbowałem.

Jeśli nie masz specjalnych wymagań, nie ma powodu, dla którego powinieneś nalegać na rozwiązanie specyficzne dla problemu, które działa tylko dla NLS z ograniczeniami pudełkowymi.

Zmiana wymagań (np. Dodanie ograniczeń nieliniowych) spowodowałaby poważny ból głowy związany z rozwiązaniem konkretnego problemu. Nie będziesz mieć takich problemów, jeśli użyjesz IPOPT ogólnego przeznaczenia.

AKTUALIZACJA: Możesz wypróbować L-BFGS z IPOPT , patrz pod Quasi-Newton w dokumentacji.

Procedura rozwiązania może stać się szybsza kosztem zepsucia niezwykłej niezawodności IPOPT. Moim zdaniem użyj dokładnych instrumentów pochodnych, jeśli są dostępne. Zaczynam bałaganować przybliżeniami (takimi jak L-BFGS) tylko wtedy, gdy mam udowodnione problemy z wydajnością.

Ali
źródło

Nie wiem, jak dobrze działa IPOPT, ale twoja sugestia przypomina mi podobne stwierdzenia zwolenników metody simpleks zjazdowej. Ponieważ nieliniowe najmniejsze kwadraty są powszechną klasą problemów, całkowite odrzucenie przy użyciu jednego z istniejących rozwiązań NLS wydaje mi się nieco podejrzane.

Thomas Klimpel

@ThomasKlimpel Cóż, Denis powinien podać nam więcej szczegółów, a następnie moglibyśmy pomóc mu wybrać odpowiedni solver. :) Lub może sam to sprawdzić i dowiedzieć się, który najlepiej odpowiada jego potrzebom. IPOPT wydaje się być dobrym rozwiązaniem na początek.

Ali

@Ali, czy możesz wskazać jakieś „rzeczywiste lub realistyczne przypadki testowe”?

denis

@denis Mógłbym, ale nie mam zamiaru tego robić, to zrzuciłoby cię z toru. Liczy się tylko to, jak IPOPT poradzi sobie z twoim problemem . Chyba że masz jakieś specjalne wymagania, powinno to dobrze rozwiązać. IPOPT posiada interfejsy do MATLAB, C ++, C, Fortran, R, AMPL, CUTEr. Wybierz jeden interfejs i sprawdź, co dzieje się z twoim problemem :) Testowanie konkretnego rozwiązania problemu również nie byłoby łatwiejsze.

Ali

@Thomas Klimpel, zgaduję, że nie byłem jasny: nie odrzucam, nie pytam o pakiety, ale pytam o spostrzeżenia lub przypadki testowe: dlaczego ta trywialna metoda może nie działać dobrze?

denis

1

Pakiet CRAN R minpack.lm zapewnia implementację Levenberg-Marquardt z ograniczeniami pudełkowymi.

Ogólnie rzecz biorąc, Levenberg-Marquardt jest znacznie bardziej odpowiedni niż L-BFGS-B w przypadku problemów z najmniejszymi kwadratami. Będzie lepiej (znacznie) lepiej pasował do trudnych problemów. Będzie także znacznie szybszy niż IPOPT ogólnego przeznaczenia, ponieważ jest dostosowany do nieliniowych problemów z najmniejszymi kwadratami.

Pakiet R wybiera bardzo proste podejście do projekcji w celu wymuszenia ograniczeń (patrz kod źródłowy ). W zależności od implementacji LM, której używasz, włączenie może być proste.

Sugestia w komentarzach dotyczących zastosowania transformacji (na przykład transformacji sinusoidalnej jak w scipy) jest również dobrą, prostą alternatywą do przekształcenia twojego nieograniczonego algorytmu LM w ograniczony. Będziesz także musiał uwzględnić transformację w Jakubie, jeśli Jakub jest analityczny.

Jherek
źródło

0

(Lata później) dwa solwery, które obsługują ograniczenia pola:

Scipy najmniej_squares ma 3 metody, z obszerną dokumentacją:
1. „trf”: region zaufania odblaskowy
2. „dogbox”
3. „lm”: starsze opakowanie dla MINPACK, bez ograniczeń pudełkowych.
ceres

denis
źródło

1

Scipy jeden wyraźnie mówi, że algorytm Levenberga-Marquardta nie radzi sobie z ograniczeniami pola.

tholy

Nieliniowe najmniejszych kwadratów z ograniczeniami ramek

Odpowiedzi: