Pakiet oprogramowania do ograniczonej optymalizacji?

21

Szukam rozwiązania ograniczonego problemu optymalizacji, w którym znam granice niektórych zmiennych (w szczególności ograniczenie pudełkowe).

\arg min_{u} f (u, x)

$\arg \min_u f(u,x)$

z zastrzeżeniem

c (u, x) = 0

$c(u,x) = 0$

a \leq d (u, x) \leq b

$a \le d(u,x) \le b$

gdzie $u$ jest wektorem zmiennych projektowych, $x$ jest wektorem zmiennych stanu, a $c(u,x)$ jest ograniczeniem równości (zwykle PDE). Dolne i górne ograniczenia i mogą być przestrzennie zróżnicowany. $a$ $b$

Które pakiety mogą obsługiwać systemy tego formularza?

pde optimization nonlinear-programming Sean Farley
źródło

1

Edytowana wersja nie wygląda na problem optymalizacji związany z ograniczeniami. Problem optymalizacji ograniczonej przez pudełko miałby ograniczenie . Czy ma być funkcja ? Czy liniowe ? Jeśli nie, to czy można go dwukrotnie rozróżnić? Czy wypukła w ? Jest to dwukrotnie różniczkowalne w ? Wreszcie, oznacza zbiór punktów w , w którym minimalna wartość jest osiągnięta. Czy zamiast tego masz na myśli ?

a \leq u \leq b

$a \leq u \leq b$

u

$u$

x

$x$

c

$c$

u

$u$

f

$f$

u

$u$

u

$u$

\arg min_{u}

$\arg \min_{u}$

u

$u$

f

$f$

min_{u}

$\min_{u}$

Geoff Oxberry

d (u, x) = u

$d(u,x) = u$ jest jednym szczególnym przypadkiem, ale ta bardziej ogólna forma jest w rzeczywistości powszechna w praktyce. Zawsze można wprowadzić dodatkowe zmienne, jeśli metoda ta może dotyczyć jedynie ograniczeń bezpośrednio na . Zwykle bardziej interesuje nas wartość przy której osiągane jest minimum, niż wartość minimalna . Sean dodał tag [pde], więc możesz uzyskać z tego pewną regularność. Nie stwierdził, czy system jest hiperboliczny, czy nie, więc nie zakładajmy. Nie zakładajmy, że jest wypukły, ponieważ często nie jest.

u

$u$

u

$u$

f

$f$

f

$f$

Jed Brown

dość często obejmuje regularyzację lub , więc nie powinniśmy zakładać dwóch pochodnych.

f

$f$

L^{1}

$L^1$

W^{1, 1}

$W^{1,1}$

Jed Brown

@JedBrown: To ma sens; mylnie było widzieć „ograniczenie pola” wspomniane bez wyraźnego ograniczenia pola. Dla typów problemów mówisz (problemów projektowych, problemy kontroli) jest zdecydowanie bardziej interesujące, ale problemy optymalizacyjne są zazwyczaj zaznaczono za pomocą notacji i ich zestawy rozwiązanie opisane są za pomocą notacja.

u

$u$

m i n

$min$

\arg min

$\arg \min$

Geoff Oxberry

Przydatne może być określenie, w jakim języku / środowisku modelujesz PDE. Może to ograniczyć wybór optymalizatorów.

Dominique,

18

Postanowiłem radykalnie edytować swoją odpowiedź na podstawie niektórych komentarzy.

Nie korzystałem z TAO. Z wglądu w dokumentację wydaje się, że jedynym sposobem, w jaki TAO może poradzić sobie z ograniczonymi problemami optymalizacji (wyłączając szczególny przypadek tylko ograniczeń pudełkowych), jest przekształcenie problemu w nierówność wariacyjną przy użyciu warunków Karush-Kuhn-Tucker (KKT) , które są konieczne w ramach kwalifikacji ograniczeń (typ, który zwykle widzę to warunek punktu Slatera ) i wystarczające w wypukłości celu i ograniczeń (bardziej ogólnie, wypukłość typu 1). Jeśli $f$ jest niep wypukły, sformułowanie nierówności wariacyjnej przy użyciu warunków KKT NIE jest równoważne pierwotnemu problemowi optymalizacji, więc ściśle mówiąc, jeśli chcesz globalnego optimum dla problemu optymalizacji, nie powinieneś wyrażać go jako nierówności wariacyjnej. W każdym razie trudno byłoby znaleźć globalne optimum dla optymalizacji ograniczonej przez PDE (patrz poniżej), więc może ignorowanie tego szczegółu jest w porządku. Biorąc pod uwagę to, co powiedział Wolfgang, byłbym sceptycznie nastawiony do korzystania z TAO; Jestem już sceptyczny, ponieważ nie implementuje metod rozwiązywania programów nieliniowych (NLP) jako NLP, a nie nierówności wariacyjne.

Nie jestem ekspertem od optymalizacji ograniczonej przez PDE; współpracownicy i współpracownicy kopalni pracują nad problemami optymalizacji ograniczonymi przez ODE. Wiem, że w przypadku natrętnych sformułowań, Larry Biegler (i inni) zastosuje metody kolokacji, aby zdyskretować PDE i uczynić go bardzo dużym, rzadkim NLP, a następnie rozwiąże go przy użyciu wewnętrznych metod punktowych. Aby naprawdę rozwiązać problem z optymalizacją globalną, należy również wygenerować wypukłe rozluźnienia, ale o ile mi wiadomo, takie podejście nie jest stosowane, ponieważ problemy optymalizacji ograniczone przez PDE prowadzą do tak dużych NLP, że trudno byłoby je rozwiązać globalna optymalizacja. Wspominam o tych szczegółach tylko dlatego, że sformułowanie problemu ma duży wpływ na wybór pakietu solvera. W przypadku nieinwazyjnych preparatów powtarzane PDE rozwiązuje informacje o gradiencie wydajności dla algorytmów optymalizacyjnych.

Niektóre osoby, które badają problemy optymalizacji ograniczone przez ODE, stosują podobne podejście do dyskretyzacji problemu za pomocą kolokacji i metody numerycznej, a następnie rozluźnienia wynikowego NLP, aby uzyskać wypukłą formułę stosowaną w globalnym algorytmie optymalizacji. Alternatywnym podejściem do optymalizacji ograniczonej przez ODE jest złagodzenie problemu, a następnie dyskretyzacja ODE, co jest podejściem przyjętym w moim laboratorium. Może być możliwe złagodzenie pewnych klas problemów związanych z optymalizacją ograniczonych przez PDE, ale nie znam żadnej pracy wykonanej nad tym problemem. (W pewnym momencie był to potencjalny projekt w moim laboratorium).

Ostatecznie liczy się nie różnicowalność pierwotnego PDE, ale różnicowalność dyskretyzacji w odniesieniu do zmiennych decyzyjnych.

Jeśli dyskretny problem można dwukrotnie rozróżnić w odniesieniu do zmiennych decyzyjnych, następujące pakiety obliczą lokalne rozwiązanie:

IPOPT to open source wewnętrzny punkt rozwiązywania problemów opracowany przez Andreasa Wächtera w IBM. Jest to kod bardzo wysokiej jakości. Jako solver z punktami wewnętrznymi lepiej nadaje się do funkcji obiektywnych z dużymi, rzadkimi macierzami jakobskimi i byłby użyteczny do optymalizacji ograniczonej przez PDE
SNOPT to komercyjny sekwencyjny kwadratowy solver programistyczny, który jest kolejnym wysokiej jakości kodem. Jest lepszy dla funkcji obiektywnych z małymi, gęstymi jakobianowymi macierzami, więc nie spodziewałbym się, że będzie przydatny do optymalizacji ograniczonej przez PDE, ale możesz spróbować.
NLopt to mały, otwarty kod źródłowy napisany przez Stevena Johnsona z MIT, który zawiera podstawowe implementacje szeregu nieliniowych algorytmów optymalizacji. Wszystkie algorytmy powinny być odpowiednie do rozwiązywania problemów związanych z ograniczeniami.
fmincon w Matlab implementuje szereg algorytmów (w tym programowanie punktów wewnętrznych i sekwencyjne programowanie kwadratowe) dla optymalizacji nieliniowej
GAMS i AMPL są komercyjnymi językami modelowania używanymi do formułowania problemów optymalizacyjnych i zawierają interfejsy do dużej liczby nieliniowych solverów programistycznych. Wiem, że GAMS ma wersję próbną, której można używać w przypadku mniejszych problemów, a przypadki problemów można również przesyłać na serwer NEOS w celu rozwiązania.

Możliwe jest jednak, że dyskretyzacja jest tylko raz rozróżnialna w odniesieniu do zmiennych decyzyjnych, w którym to przypadku należy zastosować prognozowane najbardziej strome zejście lub inną metodę optymalizacji pierwszego rzędu przy obliczaniu rozwiązania lokalnego. Ponieważ wiele badań koncentruje się na problemach, w których można zastosować metody drugiego rzędu (a kiedy można ich użyć, ich lepsze właściwości zbieżności sprawiają, że są lepszym wyborem), nie mogłem znaleźć wielu implementacji najbardziej stromego zejścia, które nie byłyby rozwiązaniami do zadań domowych. GNU Scientific Library zawiera implementację, ale to tylko w celach demonstracyjnych. Prawdopodobnie będziesz musiał zakodować własną implementację.

Jeśli problem jest ciągły tylko w odniesieniu do zmiennych decyzyjnych, możesz użyć metod bezpośrednich, aby rozwiązać go lokalnie. Istnieje doskonała ankieta na temat metod bezpośrednich przeprowadzona przez Koldę, Lewisa i Torczona . Najbardziej znaną z tych metod jest algorytm simpleksowy Neldera-Meada . Nie można zagwarantować, że zbiega się do lokalnego minimum w wielu wymiarach, ale i tak znalazło znaczne praktyczne zastosowanie.

Wybór pakietu naprawdę zależy od języka, którego chcesz użyć do rozwiązania problemu, jeśli rozwiązanie problemu związanego z ograniczeniami jest tylko częścią algorytmu, który chcesz zaimplementować (lub jeśli jest to jedyny krok w algorytmie, w którym to przypadku języki modelowania stają się bardziej opłacalne dla kodu produkcyjnego), rodzaju i wielkości problemu, a jeśli potrzebujesz jakiejkolwiek równoległości.

Geoff Oxberry
źródło

4

Próbowaliśmy TAO, ale okazało się, że nie jest to bardzo przydatne w przypadku problemów ograniczonych nierównością. Jest także zasadniczo w trybie konserwacji od co najmniej 2003 roku, bez żadnych nowych nowych funkcji oprócz aktualizacji do śledzenia zmian w PETSc, na których jest zbudowany.

Wolfgang Bangerth
źródło

3

Inną alternatywą jest OPT ++ . Obsługuje ograniczenia liniowe i nieliniowe dzięki wydajnemu nieliniowemu rozwiązaniu punktu wewnętrznego, zapewnia kontrolę dokładności funkcji (jeśli wymagane jest różnicowanie numeryczne), kontrolę wielkości kroków itp. Zazwyczaj optymalizuję duże funkcje ukryte (np. MES) tam, gdzie te typy kontrole mogą być przydatne.

Barron
źródło

Czy mógłbyś wyjaśnić, dlaczego OPT ++ jest dobrym pakietem do użycia? Czy ty (lub twoi koledzy) masz z tym jakieś doświadczenie?

Geoff Oxberry

Żeby było jasne, nie mam powodu, aby twierdzić, że OPT ++ jest lepszy od któregokolwiek z wymienionych wcześniej, ponieważ nie mam z nimi żadnego doświadczenia (chociaż dodałem do zakładek kilka z nich do sprawdzenia). Ale mam doświadczenie z OPT ++ i uważam, że jest odpowiednie dla moich potrzeb. Obsługuje ograniczenia liniowe i nieliniowe dzięki wydajnemu nieliniowemu rozwiązaniu punktu wewnętrznego, zapewnia kontrolę dokładności funkcji (jeśli wymagane jest różnicowanie numeryczne), kontrolę wielkości kroków itp. Zazwyczaj optymalizuję duże funkcje ukryte (np. MES) tam, gdzie te typy kontrole mogą być przydatne.

Barron

2

@Barron: na początek powinieneś umieścić to w swojej odpowiedzi. :)

JM

2

Jeśli problem został sformułowany jako problem komplementarności, możesz użyć TAO (Toolkit for Advanced Optimization). Niektóre metody w TAO, takie jak metoda zredukowanej przestrzeni (wariant metody zestawu aktywnego), są obecnie dostępne jako część SNES w PETSc ( SNESVI ).

Jungho Lee
źródło

1

$[-\infty,+\infty]$

Nie sądzę, aby MINUTE dobrze działał dla twoich potrzeb, ale transformacja może być, jeśli będziesz zmuszony napisać część lub całość kodu samodzielnie.

dmckee
źródło

Ta transformacja wygląda paskudnie; nic dziwnego, że towarzyszy temu kilka akapitów.

Geoff Oxberry

1

Jak zauważył @Geoff Oxberry, kilka pakietów pozwala znaleźć lokalne rozwiązanie. Jeśli chcesz być w stanie porównać te różne solwery NLP dla tego samego problemu, możesz użyć RobOptim .

Mimo że RobOptim został pierwotnie opracowany z myślą o problemach związanych z optymalizacją robotyki, jest odpowiedni do wszelkich nieliniowych problemów związanych z optymalizacją. Zapewnia prosty interfejs C ++ z wtyczkami do wielu solverów NLP (np. Ipopt, NAG). 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/

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

BenC
źródło

1

Należy zauważyć, że inne odpowiedzi opisują solwery , a nie ramy. Łatwiej jest znaleźć akceptowalną platformę ( sterownik ) niż dobry solver,

Deer Hunter

@DeerHunter Kiedy szukasz solvera do rozwiązania danego problemu, często trudno jest z góry ustalić, który solver obliczy najlepsze rozwiązanie i / lub będzie najszybszy. Mówisz o „dobrym rozwiązaniu”, ale tak naprawdę zależy to od tego, co rozwiązujesz: nie ma jednego „najlepszego ogólnego rozwiązania”. Co więcej, interfejsy API solvera są zwykle całkiem różne, więc użycie dobrego frameworka, który pozwala łatwo przełączać się z jednego solvera na inny, może być naprawdę pomocne. Pytanie dotyczyło „pakietów oprogramowania do ograniczonej optymalizacji”, a do tej kategorii należą również frameworki.

BenC

1

Oto częściowa lista pakietów optymalizacyjnych ograniczonych przez PDE.

Dolfin Adjoint jest częścią FEniCS FEM:

http://dolfin-adjoint.org/

ROL, MOOCHO, Sundance są częścią Trilinos:

https://github.com/trilinos/trilinos/tree/master/packages/rol/

https://github.com/trilinos/trilinos/tree/master/packages/Sundance/

http://trilinos.org/packages/moocho/

Przykład PYOMO dla optymalizacji ograniczonej przez PDE:

https://software.sandia.gov/trac/pyomo/browser/pyomo/trunk/examples/dae

Podręcznik TAO podaje przykłady rozwiązywania problemów optymalizacji ograniczonych przez PDE:

http://www.mcs.anl.gov/petsc/petsc-3.5/docs/tao_manual.pdf

denfromufa
źródło

1

Witamy w SciComp.SE! Samo podanie linku (może być przydatne) nie jest tak naprawdę dobrą odpowiedzią; patrz meta.stackexchange.com/questions/8231 . Czy mógłbyś nieco rozwinąć tę kwestię (język obliczeniowy, jakie ograniczenia można leczyć, jakie metody są wdrożone itp.)?

Christian Clason

Zgadzam się z @ChristianClason. Znacząco rozwinięto solwery dla oprogramowania optymalizacyjnego ograniczonego przez PDE; jednak ta odpowiedź zasadniczo nie dostarcza informacji na temat algorytmów, które te pakiety faktycznie wdrażają.

Geoff Oxberry

0

The APM MATLAB i APM Python pakiety mogą rozwiązać dużą skalę (100,000 zmienne) układów równań mieszane Integer różnicowego algebraicznych. Oprogramowanie jest dostępne jako usługa internetowa do użytku komercyjnego lub akademickiego. Jeśli rozwiązujesz system PDE, możesz raz dyskretnie wprowadzić go do formularza DAE lub ODE, aby umieścić go w języku modelowania APMonitor. Język modelowania używa solverów APOPT , BPOPT, IPOPT, SNOPT i MINOS.

John Hedengren
źródło

1

Proszę ujawnić swoją przynależność jako programisty APMonitor w tej i przyszłych odpowiedziach dotyczących twojego oprogramowania. Zobacz często zadawane pytania, aby uzyskać szczegółowe informacje na temat naszych zasad ujawniania.

Geoff Oxberry

Geoff, dzięki za podpowiedź. Pracę na platformie APMonitor rozpocząłem w 2004 roku jako doktorant na University of Texas w Austin. Używamy go teraz w naszej grupie badawczej na Uniwersytecie Brighama Younga do kontroli i optymalizacji procesów ( apm.byu.edu/prism ) w aplikacjach biologicznych, chemicznych, lotniczych i innych. Udostępniam go bezpłatnie użytkownikom komercyjnym lub akademickim.

John Hedengren,

Pakiet oprogramowania do ograniczonej optymalizacji?

Odpowiedzi: