Biblioteka C ++ do nieliniowej ograniczonej minimalizacji

9

Obecnie próbuję rozwiązać problem minimalizacji ograniczonej nieliniowo, jak zaimplementowano w funkcji matlab „fmincon”. Moje oczekiwania to minimalizacja (fun1, x0, uB, lB, fun2), gdzie x0 to stan początkowy, fun1 to funkcja, którą należy zminimalizować, uB to górne granice, lB to dolne granice, a fun2 to funkcja zapewniająca wektory równości nieliniowych / nierówności opisane w http://www.mathworks.com/help/optim/ug/fmincon.htmljako funkcja nonlcon. Wektory te również zmieniają się przez iteracje (są nieliniowo zależne od x_n, n-ta iteracja wektora rozwiązania). W implementacji Matlab mają one postać c (x) <= 0. Jest to ostatni fragment kodu, który należy przenieść z Matlaba do C ++. Miałem dużo problemów, próbując znaleźć odpowiednią bibliotekę c ++ zawierającą ten algorytm. Dlatego szukam tutaj pomocy i byłbym bardzo wdzięczny, gdybyś mógł udzielić swojej wiedzy.

Dobry przykład tego, co chcę zrobić, to pierwszy na tej stronie http://www.mathworks.com/help/optim/ug/constrained-nonlinear-optimization-examples.html#f10960?s_tid=doc_12b Jedyną różnicą jest to, że ja potrzebuję również granic ...

Z góry dziękuję.

Piotr

Peter Kottas
źródło
Istnieje możliwość użycia NLOPT ab-initio.mit.edu/wiki/index.php/NLopt_C-plus-plus_Reference, ale musiałbym obliczyć skończone różnice przy użyciu wielu wywołań do „zminimalizowanej” oceny funkcji z funkcji celu i byłem miły mając nadzieję, że algorytm sam się tym zajmie, aby poprawić wydajność. Obliczanie mojej zminimalizowanej funkcji jest naprawdę drogie. Aby wyjaśnić, funkcja zminimalizowana to prawdopodobieństwo logarytmiczne modelu szacunkowego z oryginalnymi danymi w estymacji modelu przełączania markowa w szeregach czasowych.
Peter Kottas,
1
Czy spojrzałeś na odpowiedzi na to pytanie ? Jeśli twoje wymagania nie są wystarczająco spełnione, powinieneś edytować swoje pytanie, aby je wskazać, aby uzyskać pomocne rekomendacje.
Christian Clason
Dzięki, jest tam kilka przydatnych informacji. Obecnie jestem na łokciach w bibliotece NLOPT, ponieważ odkryłem, że może to również pasować do mojego problemu. Będę na bieżąco zamieszczał ten temat i dostarczę rozwiązania, gdy tylko go wymyślę. Jakakolwiek pomoc, która może przyspieszyć proces, jest nadal doceniana. Rzeczywiste wdrożenie na przykład itp.
Peter Kottas,
1
Kilka pytań: 1. Czy Twój problem jest wypukły? 2. Czy cel i ograniczenia są zróżnicowane? Jeśli tak, ile razy? Pewnego razu? Dwa razy? 3. Czy możesz łatwo obliczyć te pochodne, jeśli istnieją? Czy przybliżenia różnic skończonych byłyby łatwe do obliczenia, jeśli nie masz łatwo dostępnych pochodnych? 4. Ile masz zmiennych decyzyjnych? (tzn. ile zmiennych próbujesz zminimalizować?) Wystarczyłaby przybliżona ocena. 5. Czy oceny funkcji są drogie? Pomocne byłoby posiadanie wszystkich tych informacji w celu uzyskania lepszej odpowiedzi.
Geoff Oxberry 30.12.12
Cześć! Przede wszystkim dziękuję za odpowiedź. 1. Trudno powiedzieć, ale najprawdopodobniej nie, ponieważ funkcją zminimalizowaną jest prawdopodobieństwo logarytmiczne między oszacowaniem modelu przełączania markowa szeregów czasowych w zastosowaniu finansowym i z natury tego zakładam rodzaj hałaśliwego wyniku. 2. nie 3. wyłącznie przy użyciu różnic skończonych 4. wektor rozwiązania składa się z n zmiennych, gdzie n jest zależny od pożądanych parametrów modeli, ogólnie od 12 do powiedzmy 30 5. log-prawdopodobieństwo między modelem a oryginalnymi danymi jest drogie, dodatkowe nierówności nieliniowe są tanie do obliczenia
Peter Kottas

Odpowiedzi:

2

Jeśli twojej funkcji nie da się rozróżnić, powinieneś uważać na to, jak używasz różnic skończonych. Jeśli chcesz korzystać z informacji pochodnych, najlepszym rozwiązaniem jest prawdopodobnie jakaś półstosowna metoda typu Newtona. Zestaw notatek opisujących takie metody można znaleźć tutaj .

Od dwunastu do trzydziestu zmiennych jest prawdopodobnie na górnym końcu tego, co jest możliwe dzięki metodom wyszukiwania wzorców (zwanym także wyszukiwaniem bezpośrednim). Najnowszy artykuł przeglądowy Riosa i Sahinidisa w Journal of Global Optimization na temat metod optymalizacji wolnych od pochodnych (takich jak metody wyszukiwania wzorców) można znaleźć tutaj , wraz ze stroną towarzyszącą . Mniej aktualny artykuł przeglądowy na temat tych metod autorstwa Kolda, Lewisa i Torczona w SIAM Review można znaleźć tutaj . Metody te działają dość dobrze z kosztownymi ocenami funkcji i niekoniecznie wymagają różnicowania lub informacji pochodnych.

Wiele z tych metod wymaga pewnego rodzaju wypukłości, aby zagwarantować zbieżność z globalnym optimum, więc jeśli miałbyś rygorystycznie rozwiązać swój problem, może być konieczne połączenie tych metod powyżej ze strategią odgałęzienia. Jeśli jednak nie zależy ci na rygorze, takie podejście jak MATLAB fminconmoże działać wystarczająco dobrze (nie ma już żadnych gwarancji). Skończone różnice najprawdopodobniej dadzą ci członka subfunkcji twojej niezróżnicowanej funkcji, co może wystarczyć dla twojego wystąpienia problemu i określonych danych wejściowych, aby zwrócić wystarczająco dokładny wynik dla twoich celów. W takim przypadku powinieneś prawdopodobnie spojrzeć na biblioteki wymienione w odpowiedziach na pytanie, które Christian powiązał w swoim komentarzu.

Geoff Oxberry
źródło
2

Jeśli potrzebujesz tylko biblioteki C ++ do rozwiązywania problemów optymalizacji nieliniowej, możesz użyć RobOptim . Mimo że RobOptim został pierwotnie opracowany z myślą o problemach związanych z optymalizacją robotyki, nadaje się do wszelkich nieliniowych problemów optymalizacji. Zapewnia prosty interfejs C ++ z wtyczkami do wielu solverów nieliniowych ( Ipopt , NAG itp.). Korzystanie z tego rodzaju opakowań ułatwia korzystanie z innego solvera NLP. Jeśli nie możesz podać gradientów, obliczenia różnic skończonych można wykonać automatycznie.

Jest to oprogramowanie typu open source, dzięki czemu możesz sprawdzić kod źródłowy w GitHub: https://github.com/roboptim/

Analiza przeprowadzona przez @Geoff Oxberry jest niezbędna do wyboru solwera nieliniowego, który zostanie wywołany przez RobOptim. Zwróć uwagę, że w przypadku tego rodzaju rozwiązań, modyfikowanie parametrów może mieć ogromny wpływ na wydajność i nadal możesz utknąć w lokalnych minimach (tak naprawdę zależy to od rodzaju problemu, z którym masz do czynienia).

Uwaga: Jestem jednym z twórców tego projektu.

BenC
źródło