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

77

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.

David Ketcheson
źródło
2
David, niestety jest to teraz zupełnie inne pytanie :) Różnica między lokalnym minimum a globalnym jest przedmiotem potencjalnej nieskończonej liczby doktoratów, a według twierdzenia o braku darmowego lunchu każdy solver, który jest dobry dla jednego ogólnego problemu optymalizacji globalnej, jest prawdopodobnie zły dla drugiego. Mogę zasugerować, aby zacząć od rozważenia opcji formułowania (Czy istnieje mieszana liczba całkowita? Czy istnieje wypukła aproksymacja?)
Aron Ahmadia
David, Aron ma rację. Formułowanie ma zdecydowanie kluczowe znaczenie dla uzyskania numerycznych rozwiązań niewypukłych NLP, nie mówiąc już o szybkim uzyskiwaniu dobrych rozwiązań. Być może warto rozważyć alternatywne formulacje, a następnie wykorzystać ich strukturę do wyboru solvera. Korzystanie z solvera, który wykorzystuje dowolną strukturę (taką jak rzadkość, wieloetapowe programowanie stochastyczne, stosowanie ograniczeń do generowania cięć), które można wywołać w swoim problemie, jest kluczem do uzyskania dobrych rozwiązań.
Geoff Oxberry
@DavidKetcheson: Skoro masz preparat, którego chcesz użyć, czy mógłbyś przynajmniej skomentować jego właściwości? Czy jakobian z Lagrangian jest gęsty czy rzadki? Z grubsza, ile ma zmiennych? Nie warto nam polecać oprogramowania, które implementuje metody rozwiązania, które są nieodpowiednie dla twojego problemu, i to jest jedyny powód, dla którego ludzie mówią o formułach.
Geoff Oxberry,
coopr zapewnia wiązanie do ipopt przy użyciu asl: ipopt
denfromufa

Odpowiedzi:

32

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.

Aron Ahmadia
źródło
Andreas wykonuje dobrą robotę, ale jego solver wymaga również informacji o matrycy jakobińskiej (lub przynajmniej informacji o rzadkości dla matrycy jakobskiej). Kiedy mówisz, że chcesz solvera, który nie wymaga macierzy jakobskiej, masz na myśli, że chcesz solvera, który nie wymaga analitycznego dostarczania macierzy jakobskiej (aby wystarczyło obliczenie różnicy skończonej), czy też chcesz solver, który w ogóle nie wymaga informacji o macierzy jakobińskiej (co ograniczyłoby cię do metod optymalizacji bez pochodnych)?
Geoff Oxberry
Dobry chwyt Mam na myśli tę pierwszą; Zaktualizowałem pytanie.
David Ketcheson,
W końcu mogłem zastosować IPOPT do mojego problemu za pomocą sage.openopt.org . Wspaniale!
David Ketcheson
4
Dzisiaj (2017) możesz również używać IPOPT w Pythonie przez Pyomo . Otrzymasz język modelowania algebrycznego i auto diff dla jakobianów i hessianów.
Antonello,
@Antonello poprawiony link to pyomo.org
Moonwalker
37

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.).

Geoff Oxberry
źródło
Uwaga: PaGMO posiada licencję GPL
denfromufa
14

Python APM

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+.

John Hedengren
źródło
2
John, widzę, że APM Python jest ogólnie dostępny, ale nie mogę zrozumieć, czy pakiet zawiera solwery, z których korzysta lokalnie, czy też wymaga połączenia ze stroną AP Monitor w celu wykonania obliczeń. Jestem ciekawy co.
Aron Ahmadia,
3
Skrypty Aron, MATLAB lub Python wymagają połączenia internetowego z serwerami APM w celu rozwiązania problemów związanych z optymalizacją. Ma to wiele zalet i wad. Z drugiej strony usługa optymalizacji sieci pozwala na zgodność między platformami, bezpłatny dostęp do niektórych komercyjnych rozwiązań i uaktualnień oprogramowania, które są przejrzyste dla użytkownika. Wadą jest to, że APM nie jest tak elastyczny, jak niektóre alternatywy typu open source, ale jest przeznaczony dla użytkowników przemysłowych, którzy preferują gotowe rozwiązanie do optymalizacji.
John Hedengren
@JohnHedengren Mam pewne wstępne obliczenia w MATLAB, używając innej biblioteki do zbudowania samego problemu optymalizacji, zwłaszcza ograniczenia związane z tymi wywołaniami zewnętrznymi. Czy uważasz, że APM nadal nadaje się do tego celu?
gpavanb
Myślę, że powszechnym terminem na to jest optymalizacja blackboksa.
gpavanb
@gpavanb Pakiet APMonitor wymaga napisania równań w języku modelowania. Jedną z opcji ładowania kodu zewnętrznego jest utworzenie obiektu, który zapewnia reszty i przynajmniej pierwsze pochodne analityczne. Zazwyczaj kodujemy te obiekty w F90 pod kątem prędkości, takie jak te wymienione tutaj: apmonitor.com/wiki/index.php/Main/Objects Nie sądzę, aby APMonitor był najlepszą opcją dla aplikacji z optymalizacją blackboksa.
John Hedengren
7

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.

Dominique
źródło
7

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.

Hans
źródło
5

Python GEKKO

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 .

John Hedengren
źródło
Czy możesz edytować swoją odpowiedź, aby wyjaśnić, w jaki sposób twoje oprogramowanie spełnia określone wymagania wymienione w poście? W przeciwnym razie wygląda to bardziej jak zwykły post reklamowy niż odpowiedź na pytanie (i prawdopodobnie zostanie zamknięte).
Christian Clason
Christian, zredagowałem odpowiedź, aby była bardziej szczegółowa w stosunku do pytania. Na koniec przeniosłem dodatkowe informacje o GEKKO i kursach online, ale w razie potrzeby mogę je usunąć.
John Hedengren
4

Co z scipy.fmin_slsqp?

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

Alejandro
źródło
1
Dzięki, ale tego właśnie próbowałem (poprzez OpenOpt, który zapewnia dodatkowy interfejs). Nigdy nie był lepszy niż fmincon / sqp i zawiódł w wielu przypadkach, w których ten ostatni się udało.
David Ketcheson,
1
Aktualizacja: Próbowałem tego bezpośrednio z SciPy. Nie udaje się nawet w przypadku problemów, w których fmincon jest w stanie konsekwentnie znaleźć globalne optimum w ciągu kilku sekund.
David Ketcheson,
4

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!

Dario Izzo
źródło
3

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

John D. Cook
źródło
Ale OP pyta o niewypukły problem optymalizacji.
Alejandro
1
OP pyta o niewypukły problem optymalizacji, ale na wszystkie wspomniane do tej pory solwery można jedynie znaleźć epsilon-optymalne rozwiązania wypukłych problemów optymalizacji bez dodatkowych metaheurystyk (wieloczęściowe lub inne stochastyczne globalne algorytmy optymalizacji, które wymagają deterministycznego, nieliniowe, wypukłe solwery optymalizacyjne) lub algorytmy podobne do gałęzi i granicy (takie jak gałąź i granica, gałąź i cięcie oraz gałąź i redukcja), które wymagają rozluźnienia funkcji celu i ograniczeń. Ta odpowiedź nie jest gorsza od innych wymienionych na 11 grudnia.
Geoff Oxberry,
Geoff, jak mogę zastosować cvxmod do problemu niewypukłego?
David Ketcheson,
Nie korzystałem z oprogramowania, ale teoretycznie, jak każdy inny wypukły solver, użyłbyś go, aby znaleźć lokalnie optymalne rozwiązania, podobnie jak teraz używasz fmincon (który jest również wypukłym solverem). Jednym ze sposobów korzystania z niego byłby wieloczęściowy. Wygeneruj listę punktów, które będą używane jako wstępne domysły dla wypukłego solvera. Dla każdego punktu używanego jako domysły zapisz rozwiązanie zwrócone przez solver. Punkt, który odpowiada minimalnej wartości funkcji celu dla wszystkich zwracanych rozwiązań, jest najlepszym przybliżeniem globalnego optimum.
Geoff Oxberry,
1
@Geoff: Tak, używam multistart. Jeśli chodzi o CVXMOD, akceptuje tylko problemy, które można sformułować w kategoriach zdyscyplinowanego programowania wypukłego. Ogólne problemy z programowaniem nieliniowym nie mogą. Jak mówisz, mogłem szukać kolejnych wypukłych relaksacji zbliżających się do mojego problemu, ale głównym celem tutaj jest, aby wykonać mniej pracy.
David Ketcheson,
3

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

użytkownik871016
źródło
To wydaje się już nie istnieć.
footwet
3





denis
źródło
Od wydania 2014b jest to obsługiwane bezpośrednio przez Matlab; patrz mathworks.de/help/matlab/matlab-engine-for-python.html
Christian Clason
@Christian Clason, to wydaje się wcale nie robić numpy-Matlab? jak robi to Python-Matlab-Bridge. (Nie użyłem go jednak.)
den
Nie bezpośrednio (wydaje się, że ma niestandardową klasę tablic matlab), ale istnieje sposób na konwersję między tym a numpy. Oczywiście będzie to związane z kopiowaniem danych, ale prawdopodobnie jest to mniejszy problem dla rozmiarów problemów, o których wspomina OP. (Sam tego nie użyłem; pomyślałem, że wskazałbym opcję).
Christian Clason,
3

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.

MPath
źródło
2

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
Brian
źródło
Ten optymalizator jest daleki od tego, o co prosi OP. Na przykład nie ma jasnego sposobu radzenia sobie z ograniczeniami równości lub nierówności w CMA-ES.
arów
1

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”).

10300(x0.1)2+10300(y0.2)2(x,y)=(1,1)

Dmitrey
źródło
2
Jeśli czytasz uważnie, proszę tylko o coś podobnego do fmincon. Nie musi być lepszy, a może być nawet wolniejszy.
David Ketcheson,
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

asd
źródło
Tak, wypróbowałem niektóre z nich, ale żadne nie dorównało fminconowi.
David Ketcheson
1

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

Tolga Birdal
źródło
Czy to nie Levenbeg-Marquardt? co, choć miłe, jest dalekie od tego, czego chce OP
denis
Chociaż ceres jest naprawdę dobrym rozwiązaniem, w ogóle nie obsługuje ograniczeń równości i obsługuje tylko ograniczenia nierówności jako górne / dolne granice parametrów (od obecnej wersji 1.12).
orzechów