Czy istnieje wysokiej jakości nieliniowy solver programowania dla Pythona?

Mam kilka trudnych, niewypukłych problemów globalnej optymalizacji do rozwiązania. Obecnie używam MATLAB's Optimization Toolbox (konkretnie fmincon()z algorytmem = 'sqp'), co jest dość skuteczne . Jednak większość mojego kodu znajduje się w języku Python i chciałbym również przeprowadzić optymalizację w języku Python. Czy istnieje solver NLP z powiązaniami Pythona, z którym można konkurować fmincon()? To musi

• być w stanie poradzić sobie z nieliniowymi ograniczeniami równości i nierówności
• nie wymaga od użytkownika podania jakobianu.

Jest w porządku, jeśli nie gwarantuje globalnego optimum ( fmincon()nie). Szukam czegoś, co solidnie zharmonizuje się z lokalnym optimum, nawet w przypadku trudnych problemów, a nawet jeśli będzie nieco wolniejsze niż fmincon().

Wypróbowałem kilka solverów dostępnych przez OpenOpt i okazało się, że są gorsze od MATLAB-a fmincon/sqp.

Dla podkreślenia mam już dobrą recepturę i dobry solver. Moim celem jest jedynie zmiana języka w celu usprawnienia przepływu pracy.

Geoff podkreśla, że ​​niektóre cechy problemu mogą być istotne. Oni są:

• 10–400 zmiennych decyzyjnych
• 4-100 wielomianowe ograniczenia równości (stopnie wielomianu wynoszą od 1 do około 8)
• Liczba racjonalnych ograniczeń nierówności równa około dwukrotności liczby zmiennych decyzyjnych
• Funkcja celu jest jedną ze zmiennych decyzyjnych

Jakobian ograniczeń równości jest gęsty, podobnie jak jakobian ograniczeń nierówności.

fmincon(), jak wspomniałeś, stosuje kilka strategii, które są dobrze znane w optymalizacji nieliniowej, które próbują znaleźć lokalne minimum bez większego znaczenia, czy znaleziono globalne optimum. Jeśli nie masz nic przeciwko, myślę, że poprawnie sformułowałeś pytanie (optymalizacja nieliniowa).

Najlepszy pakiet, jaki znam dla ogólnej optymalizacji nieliniowej, to IPOPT [1]. Najwyraźniej Matthew Xu utrzymuje zestaw powiązań Python z IPOPT , więc może to być gdzieś na początek.

[1]: Andreas Wachter jest osobistym przyjacielem, więc mogę być nieco stronniczy.

Pracuję w laboratorium, które zajmuje się globalną optymalizacją problemów z liczbami całkowitymi i niewypukłymi. Moje doświadczenie z rozwiązaniami optymalizacyjnymi typu open source polegało na tym, że lepsze są zazwyczaj pisane w skompilowanym języku i mają się gorzej w porównaniu z komercyjnymi pakietami optymalizacyjnymi.

Jeśli potrafisz sformułować swój problem jako jawny układ równań i potrzebujesz darmowego rozwiązania, najlepszym wyborem jest prawdopodobnie IPOPT, jak powiedział Aron. Inne bezpłatne solwery można znaleźć na stronie internetowej COIN-OR . Według mojej wiedzy, nieliniowe solwery nie mają powiązań Pythona dostarczonych przez programistów; wszelkie znalezione wiązania byłyby stronami trzecimi. Aby uzyskać dobre rozwiązania, musiałbyś również owinąć dowolny nieliniowy, wypukły solver znaleziony w odpowiedniej stochastycznej heurystyce optymalizacji globalnej lub w deterministycznym algorytmie optymalizacji globalnej, takim jak rozgałęzienie i ograniczenie. Alternatywnie, możesz użyć Bonmin lub Couenne, z których oba są deterministycznymi niewypukłymi solverami optymalizacyjnymi, które działają sprawnie dobrze w porównaniu do najnowocześniejszego solvera BARON .

Jeśli możesz kupić komercyjny solver optymalizacyjny, możesz rozważyć spojrzenie na język modelowania GAMS , który zawiera kilka nieliniowych solverów optymalizacyjnych. Na szczególną uwagę zasługują interfejsy do solverów CONOPT, SNOPT i BARON. (CONOPT i SNOPT są wypukłymi rozwiązaniami.) Kludgey rozwiązaniem, którego użyłem w przeszłości, jest użycie powiązań językowych Fortran (lub Matlab) z GAMS w celu napisania pliku GAMS i wywołania GAMS z Fortran (lub Matlab) w celu obliczenia rozwiązanie problemu optymalizacji. GAMS ma powiązania z językiem Python i bardzo szybko reagujący personel pomocniczy chętny do pomocy w razie problemów. (Oświadczenie: Nie mam powiązań z GAMS, ale moje laboratorium posiada licencję GAMS). Rozwiązania komercyjne nie powinny być gorsze niżfmincon; w rzeczywistości byłbym zaskoczony, gdyby nie były o wiele lepsze. Jeśli Twoje problemy są wystarczająco małe, może nie być nawet konieczne wykupienie licencji GAMS i licencji na solwery, ponieważ kopię testową GAMS można pobrać z ich witryny internetowej. W przeciwnym razie prawdopodobnie zdecydujesz, które solwery kupić w połączeniu z licencją GAMS. Warto zauważyć, że BARON wymaga rozwiązania do programowania liniowego z mieszanymi liczbami całkowitymi oraz że licencje na dwa najlepsze rozwiązania do programowania liniowego z mieszanymi liczbami całkowitymi CPLEX i GUROBI są bezpłatne dla naukowców, więc możesz być w stanie uciec po prostu kupując interfejsy GAMS niż interfejsy i licencje na solver, co może zaoszczędzić sporo pieniędzy.

Należy powtórzyć ten punkt: w przypadku każdego deterministycznego niewypukłego rozwiązania optymalizacyjnego, o którym wspomniałem powyżej, musisz mieć możliwość sformułowania modelu jako jawnego zestawu równań. W przeciwnym razie nie wypukłe algorytmy optymalizacji nie będą działać, ponieważ wszystkie z nich opierają się na analizie symbolicznej do tworzenia wypukłych relaksacji dla algorytmów rozgałęzionych i powiązanych.

AKTUALIZACJA: Jedną z myśli, które na początku mi nie przyszło do głowy, było to, że można również zadzwonić do Toolkit for Advanced Optimization ( TAO ) i PETSc przy użyciu tao4py i petsc4py , co miałoby potencjalnie dodatkową zaletę łatwiejszej równoległości i wykorzystania znajomości PETSc oraz narzędzia ACTS .

AKTUALIZACJA # 2: W oparciu o dodatkowe informacje, o których wspomniałeś, najlepsze będą metody sekwencyjnego programowania kwadratowego (SQP). Metody SQP są ogólnie uważane za bardziej niezawodne niż metody punktów wewnętrznych, ale mają tę wadę, że wymagają gęstych rozwiązań liniowych. Ponieważ bardziej zależy Ci na solidności niż szybkości, SQP będzie najlepszym wyborem. Nie mogę znaleźć dobrego rozwiązania SQP napisanego w Pythonie (i najwyraźniej Sven Leyffer nie był w Argonne w tym raporcie technicznym ). Zgaduję, że algorytmy zaimplementowane w pakietach takich jak SciPy i OpenOpt mają zaimplementowany podstawowy szkielet niektórych algorytmów SQP, ale bez specjalistycznej heurystyki, której używają bardziej zaawansowane kody w celu przezwyciężenia problemów konwergencji. Możesz spróbować NLopt, napisany przez Stevena Johnsona z MIT. Nie mam na to wielkiej nadziei, ponieważ nie ma żadnej znanej mi reputacji, ale Steven Johnson jest genialnym facetem, który pisze dobre oprogramowanie (w końcu był współautorem FFTW). Implementuje wersję SQP; jeśli to dobre oprogramowanie, daj mi znać.

Miałem nadzieję, że TAO będzie miało coś w rodzaju ograniczonego solvera optymalizacyjnego, ale tak nie jest. Z pewnością możesz użyć tego, co mają zbudować; mają tam wiele komponentów. Jak już zauważyłeś, byłoby to o wiele więcej pracy, a jeśli masz takie kłopoty, równie dobrze możesz być programistą TAO.

Dzięki tym dodatkowym informacjom istnieje większe prawdopodobieństwo, że uzyskasz lepsze wyniki, wywołując GAMS z Pythona (jeśli w ogóle jest to opcja) lub próbując załatać interfejs Python IPOPT. Ponieważ IPOPT używa metody punktu wewnętrznego, nie będzie tak solidna, ale być może implementacja metody punktu wewnętrznego Andreasa jest znacznie lepsza niż implementacja SQP przez Matlaba, w którym to przypadku możesz wcale nie poświęcać solidności. Aby mieć pewność, musiałbyś przeprowadzić kilka studiów przypadku.

Znasz już sztuczkę przeformułowania ograniczeń racjonalnej nierówności jako wielomianowych ograniczeń nierówności (jest to w twojej książce); powodem, dla którego pomogłoby to BARON i niektórym innym niep wypukłym rozwiązaniom jest to, że może on używać analizy terminów do generowania dodatkowych prawidłowych nierówności, które może wykorzystać jako cięcia w celu poprawy i przyspieszenia konwergencji rozwiązania.

Wyłączając powiązania GAMS Python i interfejs Pythona do IPOPT, odpowiedź brzmi nie, nie ma jeszcze wysokiej jakości nieliniowych solverów programistycznych dla Pythona. Może @Dominique zmieni to dzięki NLPy.

AKTUALIZACJA # 3: Więcej dzikich prób znalezienia rozwiązania opartego na Pythonie przyniosło PyGMO , który jest zestawem powiązań Pythona z PaGMO, globalnym wielozadaniowym rozwiązaniem optymalizacyjnym opartym na C ++. Chociaż został stworzony do optymalizacji wieloobiektywowej, może być również używany do jednoprzedmiotowego programowania nieliniowego i ma interfejsy Python do IPOPT i SNOPT, między innymi. Został opracowany w ramach Europejskiej Agencji Kosmicznej , więc mam nadzieję, że stoi za tym społeczność. Został również wydany stosunkowo niedawno (24 listopada 2011 r.).

Aktualizacja: zobacz nowy pakiet GEKKO, który właśnie wydaliśmy.

APM Python to darmowy zestaw narzędzi do optymalizacji, który posiada interfejsy do APOPT, BPOPT, IPOPT i innych solverów. Dostarcza solverom pierwszej (jakobskiej) i drugiej (Heskiej) informacji oraz zapewnia opcjonalny interfejs WWW do przeglądania wyników. Klient APM Python jest instalowany z pipem:

 pip install APMonitor

Można go również zainstalować w skrypcie Python za pomocą:

try:
    from APMonitor.apm import *
except:
    # Automatically install APMonitor
    import pip
    pip.main(['install','APMonitor'])
    from APMonitor.apm import *

Zrobiliśmy kilka testów porównawczych i stwierdziliśmy, że połączenie APOPT (metoda zestawu aktywnego) i IPOPT (metoda punktu wewnętrznego) może rozwiązać duży procent problemów z testem porównawczym. Istnieje kilka przykładowych problemów, które są zawarte w pobranym pliku zip. Tym, od którego prawdopodobnie będziesz chciał zacząć, jest Hock Schittkowski # 71. Jest to najprostszy przykład i pokazuje, jak rozwiązać ograniczone problemy optymalizacji.

Istnieje interfejs przeglądarki i interfejs API do Python / MATLAB. Interfejs API Python to pojedynczy skrypt (apm.py), który można pobrać ze strony głównej apmonitor.com. Po załadowaniu skryptu do kodu w języku Python daje on możliwość rozwiązania problemów:

• Równania nieliniowe
• Mieszane nieliniowe programowanie liczb całkowitych
• Równania różniczkowe i algebraiczne
• Model z najmniejszymi kwadratami
• Oszacowanie ruchomego horyzontu
• Nieliniowa kontrola predykcyjna modelu
• itp.

Dla nowego użytkownika oprogramowanie APM Python ma forum Grup dyskusyjnych Google, na którym użytkownik może zamieszczać pytania. Istnieją seminaria internetowe, które pokazują problemy z optymalizacją w badaniach operacyjnych i inżynierii.

Poniżej znajduje się przykład problemu z optymalizacją (hs71.apm).

Model
  Variables
    x[1] = 1, >=1, <=5
    x[2] = 5, >=1, <=5
    x[3] = 5, >=1, <=5
    x[4] = 1, >=1, <=5
  End Variables

  Equations
    x[1] * x[2] * x[3] * x[4] > 25
    x[1]^2 + x[2]^2 + x[3]^2 + x[4]^2 = 40

    minimize  x[1] * x[4] * (x[1]+x[2]+x[3]) + x[3]
  End Equations
End Model

Problem optymalizacji rozwiązano za pomocą następującego skryptu Python:

from APMonitor.apm import *
server = 'http://byu.apmonitor.com'

# Application name
app = 'eqn'

# Clear previous application
apm(server,app,'clear all')

# Load model file
apm_load(server,app,'hs71.apm')

# Option to select solver (1=APOPT, 2=BPOPT, 3=IPOPT)
apm_option(server,app,'nlc.solver',3)

# Solve on APM server
solver_output = apm(server,app,'solve')

# Display solver output
print(solver_output)

# Retrieve results
results = apm_sol(server,app)

# Display results
print('--- Results of the Optimization Problem ---')
print(results)

# Display Results in Web Viewer 
url = apm_var(server,app)
print("Opened Web Viewer: " + url)

APM Python to darmowa usługa sieciowa do optymalizacji. Problemy optymalizacji są rozwiązywane na zdalnych serwerach, a wyniki są zwracane do lokalnego skryptu Python. Lokalny serwer APMonitor jest również dostępny do pobrania, więc połączenie z Internetem nie jest wymagane ( serwer pobierania ). Ostatnio dodaliśmy obsługę przetwarzania równoległego zarówno dla MATLAB, jak i Pythona. Moduł Python jest kompatybilny z Python 2.7 lub Python 3+.

Chociaż to nie do końca odpowiada na twoje pytanie, tworzę pakiet Pythona do programowania nieliniowego o nazwie NLPy. Najnowszą wersję można pobrać ze strony https://github.com/dpo/nlpy

Muszę podkreślić, że NLPy ma jakość badawczą, a zawarte w nim solwery nie są tak niezawodne, jak bardziej dopracowane kody, takie jak IPOPT. Co więcej, obecnie wymagają zapewnienia Jakobianów. Biorąc to pod uwagę, celem NLPy jest zapewnienie narzędzi potrzebnych naukowcom do tworzenia niestandardowych rozwiązań, jeśli zajdzie taka potrzeba. W każdym razie będę zainteresowany usłyszeniem twoich komentarzy offline, jeśli spróbujesz. Przydatne mogą być również powiązane pakiety https://github.com/dpo/pykrylov i https://github.com/dpo/pyorder . Obecnie zdecydowanie brakuje dokumentacji NLPy. Pozostałe dwa powinny być rozsądne.

pyomo to pełne środowisko modelowania podobne do GAMS / AMPL do optymalizacji w Pythonie. Jest niezwykle potężny, ma interfejsy do wszystkich solverów obsługiwanych przez AMPL i automatycznie generuje jakobianów itp. Jednak ze względu na to, że działa w „wirtualnym środowisku python”, połączenie go z istniejącym kodem może nie być trywialne.

Niedawno wydaliśmy (2018) pakiet GEKKO Pythondo programowania nieliniowego za pomocą solverów takich jak IPOPT, APOPT, BPOPT, MINOS i SNOPT z aktywnymi metodami set i point point. Jednym z problemów związanych z używaniem tych solverów jest to, że zwykle musisz podać co najmniej pierwsze pochodne i opcjonalnie drugie pochodne. Istnieje kilka fajnych języków modelowania, które mogą to dla ciebie zrobić, jak wspomniano w innych odpowiedziach. GEKKO kompiluje równania do kodu bajtowego, dzięki czemu jest tak, jakbyś napisał model w Fortran lub C ++ pod względem szybkości. Automatyczne różnicowanie zapewnia pierwszą i drugą pochodną w postaci rzadkiej solverom opartym na gradiencie. Zaprojektowaliśmy GEKKO dla optymalnych problemów sterowania, ale może również rozwiązać problemy podobne do fmincon. Poniżej znajduje się szybki przykład problemu programowania nieliniowego z ograniczeniami równości i nierówności. Najpierw ty'

pip install gekko

Hock Schittkowski problemem 71 przedstawiono poniżej jako przykład funkcji celu, nierówność ograniczenia, ograniczenia równości i cztery zmienne z górnych i dolnych granic.

from gekko import GEKKO
m = GEKKO() # Initialize gekko
# Initialize variables
x1 = m.Var(value=1,lb=1,ub=5)
x2 = m.Var(value=5,lb=1,ub=5)
x3 = m.Var(value=5,lb=1,ub=5)
x4 = m.Var(value=1,lb=1,ub=5)
# Equations
m.Equation(x1*x2*x3*x4>=25)
m.Equation(x1**2+x2**2+x3**2+x4**2==40)
m.Obj(x1*x4*(x1+x2+x3)+x3) # Objective
m.options.IMODE = 3 # Steady state optimization
m.solve() # Solve
print('Results')
print('x1: ' + str(x1.value))
print('x2: ' + str(x2.value))
print('x3: ' + str(x3.value))
print('x4: ' + str(x4.value))    

GEKKO działa na wszystkich platformach (procesory Windows, MacOS, Linux, ARM) oraz z Python 2.7 i 3+. Opcja w pełni lokalna jest dostępna bez połączenia z Internetem poprzez ustawienie opcji „remote = False”. Opcja lokalna jest obecnie dostępna tylko dla systemu Windows i pracujemy nad innymi wersjami, takimi jak Linux, MacOS, procesory ARM, które działają lokalnie bez połączenia z Internetem. Wersja lokalna zawiera tylko bezpłatne solwery, które nie wymagają licencji. Domyślnie problem jest wysyłany do publicznego serwera, na którym obliczane jest rozwiązanie i zwracane do Pythona.

Chociaż pytanie dotyczy konkretnie rozwiązywania programowania nieliniowego w Pythonie, zwrócę też uwagę na kilka innych rodzajów problemów, które GEKKO może rozwiązać, oraz zasoby do optymalizacji uczenia się. GEKKO rozwiązuje również równania algebraiczne o mieszanej liczbie całkowitej i różniczkowej oraz ma kilka wstępnie zaprogramowanych obiektów dla zaawansowanych kontroli (podobnych do DMC, RMPCT itp.). Tryby działania obejmują uzgadnianie danych, optymalizację w czasie rzeczywistym, symulację dynamiczną i nieliniową kontrolę predykcyjną.

Uczę dwóch kursów na temat optymalizacji (optymalizacja projektu i optymalizacja dynamiczna ) i opublikowałem materiał kursu online. Kurs dynamicznej optymalizacji jest oferowany każdego roku, począwszy od stycznia, i korzystamy z pakietu GEKKO Python (i MATLAB). GEKKO jest rozszerzeniem APMonitor Optimization Suite, ale zintegrowało modelowanie i wizualizację rozwiązań bezpośrednio w Pythonie. Referencje APMonitor i GEKKO zawierają przykładowe typy aplikacji, które można rozwiązać za pomocą tego pakietu. GEKKO jest rozwijany w ramach grantu National Science Foundation Research Grant # 1547110 .

Co z scipy.fmin_slsqp?

http://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.fmin_slsqp.html

PyGMO zawiera kilka solverów, zapewniając im ten sam interfejs. IPOPT i scipy slsqp są uwzględnione w przypadku, gdy skompilujesz kod i pobierzesz / zainstalujesz kod innej firmy niezależnie.

Jako bonus, równoległe korzystanie z solvera jest naprawdę łatwe (wieloczęściowe) poprzez klasę archipelagu!

Istnieje cvxmod , opakowanie Pythona wokół wypukłego oprogramowania optymalizacyjnego Stephena Boyda. To część pakietu Sage .

fmincon może być teraz używany z Pythona za pomocą frameworku OpenOpt, opcjonalnie z automatycznym różnicowaniem gęstym / rzadkim przez FuncDesigner http://openopt.org/fmincon

$\to$ $\to$

Czy skakanie do basenu za pomocą scipy jest wystarczające dla twoich potrzeb? Jeśli zwraca lokalną min, a nie globalną min, możesz zmienić liczbę iteracji i / lub zastosować granice.

Co powiesz na CMA-ES? Ma powiązania z Pythonem i jest dobrze dostosowany do nie wypukłych, nieliniowych problemów z optymalizacją i dość często go używałem: https://www.lri.fr/~hansen/cmaesintro.html

Instalacja przez pip:

pip install cma

Oto przykładowy kod z ich strony internetowej:

import cma
help(cma)  # "this" help message, use cma? in ipython
help(cma.fmin)
help(cma.CMAEvolutionStrategy)
help(cma.CMAOptions)
cma.CMAOptions('tol')  # display 'tolerance' termination options
cma.CMAOptions('verb') # display verbosity options
res = cma.fmin(cma.Fcts.tablet, 15 * [1], 1)
res[0]  # best evaluated solution
res[5]  # mean solution, presumably better with noise

Ponieważ MATLAB ma kompilator JIT, podczas gdy CPython jeszcze go nie ma (przynajmniej dopóki pypy nie uzyska pełnej obsługi numpy). Wygląda na to, że chcesz darmowego solvera, który przewyższa produkowany komercyjnie fmincon. Czy to nie za dużo?

IIRC wśród komercyjnych solverów NLP, do tej pory tylko snopt dostarczył API Pythona (choć jest raczej brzydki).

Które solwery OpenOpt próbowałeś? Ile zmiennych i ograniczeń masz w swoim niewypukłym zadaniu?

Możesz wypróbować IPOPT przez API OpenOpt / Funcdesigner bez instalacji na serwerze OpenOpt Sage (zwróć uwagę na obrazek „przełączania z mędrca na python”).

$10^{300}(x-0.1)^2 + 10^{-300}(y-0.2)^2$$(x,y) = (1,1)$

w przypadku problemów globalnych możesz być zainteresowany http://openopt.org/interalg i innymi globalnymi rozwiązaniami openopt (http://openopt.org/GLP) w celu optymalizacji lokalnej openopt udostępnia również różnorodne rozwiązania: http://openopt.org / NLP

Warto tutaj wspomnieć, że solver Google Ceres jest w rzeczywistości bardzo potężnym nieliniowym optymalizatorem stosowanym w wielu projektach.

Dostępny jest również otoki Pythona: https://github.com/rll/cyres

KNITRO ma między innymi interfejsy Python i MATLAB. Pomyśl o tym jak o zamienniku FMINCON, ale o wiele lepszym i droższym. https://www.artelys.com/en/optimization-tools/knitro#doc-tab .

Jestem użytkownikiem KNITRO, ale nie jestem powiązany z produktem.