Deterministyczna optymalizacja globalna

Deterministyczna optymalizacja globalna to gałąź optymalizacji numerycznej, która koncentruje się na znajdowaniu globalnych rozwiązań problemu optymalizacyjnego, zapewniając jednocześnie teoretyczne gwarancje, że zgłaszane rozwiązanie jest rzeczywiście rozwiązaniem globalnym, w ramach pewnej z góry określonej tolerancji. Termin „deterministyczna optymalizacja globalna” zazwyczaj odnosi się do pełnych lub rygorystycznych (patrz poniżej) metod optymalizacji. Rygorystyczne metody zbiegają się do globalnego optimum w skończonym czasie. Deterministyczne metody optymalizacji globalnej są zwykle stosowane, gdy zlokalizowanie rozwiązania globalnego jest koniecznością (tj. gdy jedynym naturalnie występującym stanem opisanym przez model matematyczny jest globalne minimum problemu optymalizacyjnego), gdy niezwykle trudno jest znaleźć wykonalne rozwiązanie lub po prostu wtedy, gdy użytkownik chce znaleźć najlepsze możliwe rozwiązanie problemu.

Przegląd

Neumaier sklasyfikował globalne metody optymalizacji w czterech kategoriach, w zależności od stopnia rygoru, z jakim zbliżają się do optimum, w następujący sposób:

Niekompletna metoda wykorzystuje sprytną intuicyjną heurystykę do wyszukiwania, ale nie ma żadnych zabezpieczeń , jeśli wyszukiwanie utknie w lokalnym minimum
Asymptotycznie kompletna metoda osiąga globalne minimum z pewnością lub przynajmniej z prawdopodobieństwem jeden, jeśli może działać w nieskończoność, ale nie ma sposobu, aby wiedzieć, kiedy znaleziono globalny minimalizator.
Kompletna metoda z pewnością osiąga globalne minimum, zakładając dokładne obliczenia i nieskończenie długi czas działania, i wie po skończonym czasie, że znaleziono przybliżony globalny minimalizator (w ramach określonych tolerancji).
Rygorystyczna metoda osiąga globalne minimum z pewnością iw ramach określonych tolerancji , nawet w obecności błędów zaokrągleń, z wyjątkiem przypadków prawie zdegenerowanych, w których tolerancje mogą zostać przekroczone.

Deterministyczne metody optymalizacji globalnej zazwyczaj należą do dwóch ostatnich kategorii. Należy pamiętać, że zbudowanie rygorystycznego oprogramowania jest niezwykle trudne, ponieważ proces ten wymaga rygorystycznego zakodowania wszystkich zależności.

Deterministyczne metody optymalizacji globalnej wymagają sposobów rygorystycznego wiązania wartości funkcji w regionach przestrzeni. Można powiedzieć, że w tym kontekście główna różnica między metodami deterministycznymi i niedeterministycznymi polega na tym, że te pierwsze wykonują obliczenia na obszarach przestrzeni rozwiązań, podczas gdy te drugie wykonują obliczenia na pojedynczych punktach. Odbywa się to albo poprzez wykorzystanie określonych form funkcjonalnych (np. relaksacji McCormicka), albo za pomocą analizy interwałowej w celu pracy z bardziej ogólnymi formami funkcyjnymi. W każdym przypadku wymagane jest ograniczenie, dlatego deterministyczne globalne metody optymalizacji nie mogą dać rygorystycznych wyników podczas pracy z czarnej skrzynki , chyba że ten kod jest wyraźnie napisany tak, aby zwracał również granice funkcji. Z tego powodu często problemy w deterministycznej optymalizacji globalnej są przedstawiane za pomocą wykresu obliczeniowego , ponieważ łatwo jest przeciążyć wszystkie operatory tak, że wynikowe wartości funkcji lub pochodne dają wyniki przedziałowe (zamiast skalarne).

Klasy deterministycznych problemów optymalizacji globalnej

programowania liniowego (LP)

Problemy programowania liniowego są wysoce pożądanym sformułowaniem każdego problemu praktycznego. Powodem jest to, że wraz z pojawieniem się algorytmów punktów wewnętrznych możliwe jest efektywne rozwiązywanie bardzo dużych problemów (obejmujących setki tysięcy, a nawet miliony zmiennych) w celu osiągnięcia globalnej optymalności. Problemy optymalizacji programowania liniowego ściśle mieszczą się w kategorii deterministycznej optymalizacji globalnej.

programowania liniowego na liczbach całkowitych mieszanych (MILP)

Podobnie jak problemy programowania liniowego, MILP są bardzo ważne przy rozwiązywaniu modeli decyzyjnych. Wydajne algorytmy rozwiązywania złożonych problemów tego typu są znane i dostępne w postaci solverów typu CPLEX .

programowania nieliniowego (NLP)

Problemy programowania nieliniowego są niezwykle trudne w deterministycznej optymalizacji globalnej. Rząd wielkości, który nowoczesny solver może obsłużyć w rozsądnym czasie, to około 100 do kilkuset zmiennych nieliniowych. W chwili pisania tego tekstu nie istnieją równoległe rozwiązania dla deterministycznego rozwiązania NLP, co odpowiada za lukę w złożoności między deterministycznym programowaniem LP i NLP.

Zagadnienia programowania nieliniowego na liczbach całkowitych mieszanych (MINLP)

Jeszcze trudniejsze niż ich odpowiedniki NLP, deterministyczne rozwiązanie problemu MINLP może być bardzo trudne. Powszechnie stosowane są techniki, takie jak wycinanie liczb całkowitych lub rozgałęzianie problemu na jego zmiennych całkowitych (stąd tworzenie podproblemów NLP, które z kolei można rozwiązać deterministycznie).

Metody zerowego rzędu

Metody zerowego rzędu składają się z metod wykorzystujących arytmetykę przedziałów zerowego rzędu . Reprezentatywnym przykładem jest bisekcja interwału.

Metody pierwszego rzędu

Metody pierwszego rzędu obejmują metody, które wykorzystują informacje pierwszego rzędu, np. gradienty interwałowe lub nachylenia interwałowe.

Metody drugiego rzędu

Metody drugiego rzędu wykorzystują informacje drugiego rzędu, zwykle granice wartości własnych pochodzące z interwałowych macierzy Hessego . Jedną z najbardziej ogólnych metodologii drugiego rzędu do rozwiązywania problemów typu ogólnego jest αΒΒ .

Deterministyczne solwery optymalizacji globalnej

ANTYGONA : Algorytmy ciągłej/całkowitej globalnej optymalizacji równań nieliniowych). Jest to autorskie oprogramowanie, dostępne za pośrednictwem GAMS ANTIGONE .

BARON : BARON jest dostępny w językach modelowania AIMMS , AMPL i GAMS oraz na serwerze NEOS. Jest to oprogramowanie autorskie
Couenne : Convex Over and Under Envelopes for Nonlinear Estimation (Couenne) to biblioteka typu open source
EAGO: Easy-Advanced Global Optimization (EAGO) to rozwiązanie typu open source w Julii (język programowania) . Jest rozwijany przez University of Connecticut.
LINDO (Linear, Interactive, and Discrete Optimizer) zawiera globalne możliwości optymalizacji.
MAiNGO: Algorytm oparty na McCormick dla mieszanej całkowitej nieliniowej optymalizacji globalnej (MAiNGO) to pakiet C++ z równoległością MPI i openMP oraz udostępniany jako open source na licencji Eclipse Public License - v 2.0.
Octeract Engine to zastrzeżony solver z możliwościami równoległości. Jest rozwijany i licencjonowany przez Octeract
SCIP : SCIP to pakiet rozwiązań optymalizacyjnych typu open source, który między innymi rozwiązuje mieszane programowanie nieliniowe liczb całkowitych (MINLP)