MINOS (oprogramowanie do optymalizacji)

MINOS to pakiet oprogramowania Fortran do rozwiązywania liniowych i nieliniowych problemów optymalizacji matematycznej . MINOS (Modular In-core Nonlinear Optimization System) może być używany do programowania liniowego, programowania kwadratowego i bardziej ogólnych funkcji celu i ograniczeń oraz do znajdowania wykonalnego punktu dla zestawu liniowych lub nieliniowych równości i nierówności.

MINOS został po raz pierwszy opracowany przez Bruce'a Murtagha i Michaela Saundersa , głównie w Laboratorium Optymalizacji Systemów w Departamencie Badań Operacyjnych na Uniwersytecie Stanforda. W 1985 roku Saunders otrzymał inauguracyjną nagrodę Orchard-Hays od Mathematical Programming Society (obecnie Mathematical Optimization Society ) za pracę nad MINOS. Pomimo tego, że jest jednym z pierwszych solwerów optymalizacji z ograniczeniami ogólnego przeznaczenia, pakiet jest nadal intensywnie używany. MINOS jest obsługiwany w programach AIMMS , AMPL , APMonitor , GAMS i Systemy modelowania TOMLAB . Ponadto pozostaje jednym z najczęściej używanych solwerów na serwerze NEOS iw GAMS .

Operacja

W idealnym przypadku użytkownik powinien podać gradienty funkcji nieliniowych. (Jest to automatyczne w większości systemów modelowania wymienionych powyżej.) Jeśli niektóre lub wszystkie gradienty nie zostaną podane, MINOS przybliży brakujące gradienty skończonymi różnicami, ale może to być powolne i mniej niezawodne. Jeśli funkcja celu jest wypukła, a ograniczenia liniowe, otrzymane rozwiązanie będzie globalnym minimalizatorem. W przeciwnym razie otrzymane rozwiązanie może być lokalnym minimalizatorem.

stosowana jest dwufazowa metoda pierwotnego simpleksu . Pierwsza faza minimalizuje sumę niewykonalności. W przypadku problemów z ograniczeniami liniowymi i nieliniowym celem stosowana jest metoda zredukowanego gradientu. Przybliżenie quasi-Newtona do zredukowanego Hessian jest utrzymywane w celu uzyskania wskazówek wyszukiwania. Metoda jest najbardziej wydajna, gdy w rozwiązaniu działa wiele ograniczeń lub ograniczeń.

W przypadku problemów z ograniczeniami nieliniowymi stosowana jest metoda Lagrange'a z ograniczeniami liniowymi. Obejmuje to sekwencję głównych iteracji, z których każda rozwiązuje (być może w przybliżeniu) podproblem z ograniczeniami liniowymi. Celem podproblemu jest rozszerzony Lagrange'a , a ograniczenia podproblemu to linearyzacja ograniczeń nieliniowych w bieżącym punkcie.

MINOS jest przeznaczony do dużych rzadkich problemów. Nie ma ustalonego limitu rozmiaru problemu. Większość działającej pamięci masowej jest zawarta w jednej tablicy o podwójnej precyzji (która powinna być wystarczająco duża). Kod źródłowy jest odpowiedni dla wszystkich maszyn naukowych z kompilatorem Fortran.

Dalsza lektura

• BA Murtagh, MA Saunders (1982). „Przewidywany algorytm Lagrange'a i jego implementacja dla rzadkich ograniczeń nieliniowych” (PDF) . Programowanie matematyczne . 16 : 84–117.

Linki zewnętrzne

• Laboratorium Optymalizacji Systemów, Laboratorium Optymalizacji Systemów Uniwersytetu Stanforda (SOL).
• MINOS 5.5 - Opis - Dystrybutorzy oprogramowania.