proxsuite

Proxsuite ist eine Sammlung von open-Source-, numerisch robusten, präzisen und effizienten numerischen Solvers (z. B. LPS, QPS usw.), die in überarbeiteten primalen proximalen Algorithmen verwurzelt sind. Durch Proxsuite wollen wir den Community skalierbaren Optimierern anbieten, die sich mit dichten, spärlichen oder matrixfreien Problemen befassen. Während die erste gezielte Anwendung Robotik ist, kann Proxsuite in anderen Kontexten ohne Grenzen verwendet werden.

Proxsuite wird aktiv von den Forschungsgruppen der Willow und der Sierra, gemeinsamen Forschungsteams zwischen INRIA, École Normal Supérieure de Paris und Center National de la Recherche Scientifique in Frankreich entwickelt und unterstützt.

Proxsuite ist bereits integriert in:

• CVXPY -Modellierungssprache für konvexe Optimierungsprobleme,
• Casadis symbolischer Rahmen für die numerische Optimierung in der allgemeinen und optimalen Kontrolle. ProxQP ist in Casadi als Plugin zur Lösung quadratischer Programme erhältlich.
• TSID: Roboter -Software für effiziente Roboter -Inverse -Dynamik mit Kontakten und basierend auf Pinocchio.

Wir sind bereit, Proxsuite in andere Optimierungsökosysteme zu integrieren.

Proxsuite -Hauptmerkmale

Proxsuite ist schnell:

• C ++ - Vorlagenbibliothek,
• Cache-freundlich.

Proxsuite ist vielseitig und bietet eine einheitliche API -erweiterte Algorithmen an, die auf effizient ausnutzende Problemstrukturen spezialisiert ist:

• dicht, spärlich und matrixfreie Matrixfaktorisierungs-Backends,
• Fortgeschrittene Optionen für warmstart (z. B. gleichbereinigte anfängliche Vermutung, Warmstart- oder Kaltstartoptionen aus früheren Ergebnissen),

mit speziellen Funktionen für

• Umgang mit effizienter Boxbeschränkungen, linearen Programmen, QP mit diagonalem Hessisch oder mit weit mehr Einschränkungen als ursprüngliche Variablen,
• Lösen von nicht konvexen QPs,
• Lösen von QPS parallel, parallel,
• Lösen des nächstgelegenen realisierbaren QP, wenn das QP ursprünglich unmöglich zu sein scheint,
• Differenzieren Sie realisierbare und nicht realisierbare QPS.

Proxsuite ist flexibel:

• Nur Header,
• C ++ 14/17/20 konform,
• Python- und Julia -Bindungen für einfache Code -Prototypen ohne die Leistung.

Proxsuite ist erweiterbar. Proxsuite ist zuverlässig und umfassend getestet und zeigt die besten Leistungen zu den schwierigsten Problemen der Literatur. Proxsuite wird unter Windows, Mac OS X, Unix und Linux unterstützt und getestet.

Dokumentation

Die Online -Proxsuite -Dokumentation der letzten Version ist hier verfügbar.

Erste Schritte

Proxsuite wird an viele bekannte Paketmanager verteilt.

Schnelle Installation mit:

   pip install proxsuite

Dieser Ansatz ist unter Linux, Windows und Mac OS X verfügbar.

Schnelle Installation mit:

   conda install proxsuite -c conda-forge

Dieser Ansatz ist unter Linux, Windows und Mac OS X verfügbar.

Schnelle Installation mit:

   brew install proxsuite

Dieser Ansatz ist unter Linux und Mac OS X verfügbar.

Alternative Ansätze

Die Installation aus der Quelle wird hier vorgestellt.

Kompilieren eines ersten Beispielprogramms

Verwenden Sie für die schnellste Leistung den folgenden Befehl, um die Vektorisierung beim Kompilieren des einfachen Beispiels zu aktivieren.

g++ -O3 -march=native -DNDEBUG -std=gnu++17 -DPROXSUITE_VECTORIZE examples/first_example_dense.cpp -o first_example_dense $( pkg-config --cflags proxsuite )

Verwendung von Proxsuite mit CMake

Wenn Sie Proxsuite mit CMake verwenden möchten, sollte Ihnen das folgende winzige Beispiel helfen:

 cmake_minimum_required ( VERSION 3.10)

project (Example CXX)
find_package (proxsuite REQUIRED)
set (CMAKE_CXX_STANDARD 17) # set(CMAKE_CXX_STANDARD 14) will work too

add_executable (example example.cpp)
target_link_libraries (example PUBLIC proxsuite::proxsuite)

# Vectorization support via SIMDE and activated by the compilation options '-march=native' or `-mavx2 -mavx512f`
add_executable (example_with_full_vectorization_support example.cpp)
target_link_libraries (example_with_full_vectorization_support PUBLIC proxsuite::proxsuite-vectorized)
target_compile_options (example_with_full_vectorization_support PUBLIC "-march=native" )

Wenn Sie Proxsuite mit der Vektorisierungsunterstützung kompiliert haben, können Sie auch die CMake-Ziel- proxsuite::proxsuite-vectorized verwenden, um auch mit Simde zu verknüpfen. Vergessen Sie nicht -march=native zu verwenden, um die beste Leistung zu erzielen.

Proxqp

Der ProxqP -Algorithmus ist ein numerischer Optimierungsansatz zur Lösung quadratischer Programmierungsprobleme der Form:

$$ begin {align} min_ {x} & ~ frac {1} {2} x^{t} hx+g^{t} x \ text {st} & ~ a x = b \ & ~ l leq leq u {{Align $ $$

Wo $ x in mathbb {r}^n $ ist die Optimierungsvariable. Die objektive Funktion wird durch eine positive semidefinitische Matrix definiert $ H in mathcal {s}^n _+$ und ein Vektor $ g in mathbb {r}^n $ . Die linearen Einschränkungen werden durch die Matrix zur Gleichstellung der Unstimmigkeiten definiert $ A in mathbb {r}^{n_ text {eq} times n} $ und die Matrix der Ungleichheitskonstruktion $ C in mathbb {r}^{n_ text {in} times n} $ und die Vektoren $ b in mathbb {r}^{n_ text {eq}} $ Anwesend $ l in mathbb {r}^{n_ text {in}} $ Und $ u in mathbb {r}^{n_ text {in}} $ so dass $ b_i in mathbb {r}, ~ forall i = 1, ..., n_ text {eq} $ Und $ l_i in mathbb {r} cup { - infty} $ Und $ u_i in mathbb {r} cup { + infty}, ~ forall i = 1, ..., n_ text {in} $ .

Unter Berufung auf Proxqp

Wenn Sie ProxQP für Ihre Arbeit verwenden, empfehlen wir Ihnen, das zugehörige Papier zu zitieren.

Numerische Benchmarks

Die numerischen Benchmarks von Proxqp gegen andere kommerzielle und open-Source-Löser finden Sie hier.

Bei dichten konvexen quadratischen Programmen mit Ungleichheit und Gleichheitsbeschränkungen, wenn man nach relativ hoher Genauigkeit bittet (z. B. 1E-6), erzielt man die folgenden Ergebnisse.

Auf der y-Achse können Sie Timings in Sekunden und in der x-Achsen-Dimension auf die ursprüngliche Variable der zufälligen quadratischen Probleme sehen (die Anzahl der Einschränkungen des erzeugten Problems ist halb so groß wie seine ursprüngliche Dimension). Für jede Dimension wird das Problem über verschiedene Samen erzeugt, und die Timings werden als Durchschnittswert über aufeinanderfolgende Läufe für die gleichen Probleme erhalten. Dieses Diagramm zeigt für jeden von einem Benchmarked Solver und zufälligen quadratischen Programm erzeugten Barplot -Timings, einschließlich Median (als Punkt) und minimaler und maximaler Werte (Definieren der Amplitude des Balkens). Sie können sehen, dass ProxQP immer über Löser unterhalb von Lösten liegt, was bedeutet, dass es für diesen Test am schnellsten ist.

Bei harten Problemen aus dem maros meszaros testset bittet man bei einer hohen Genauigkeit (z. B. 1E-9) die folgenden Ergebnisse.

Das Diagramm oben meldet die Leistungsprofile verschiedener Solvers. Es ist klassisch für Benchmarking -Solvers. Leistungsprofile entsprechen dem Anteil der gelösten Probleme (auf der y-Achse) als Funktion bestimmter Laufzeit (auf der X-Achse, gemessen an einem Vielfachen der Laufzeit des schnellsten Lösers für dieses Problem). Also desto höher, desto besser. Sie können sehen, dass ProxQP die schnellsten über 60% der Probleme löst (dh für $ tau = 1 $ ) und dass es für die Lösung von etwa 90% der Probleme höchstens zweimal langsamer ist als die schnellsten Löser, die diese Probleme lösen (dh für $ tau ca.2 $ ).

HINWEIS: Alle diese Ergebnisse wurden mit einem Intel (R) Core (R) Core (TM) I7-11850H bei 2,50 GHz CPU (TM) erhalten.

Qplayer

QPlayer ermöglicht es, ein QP als Ebene innerhalb der Standard -Lernarchitekturen zu verwenden. Genauer gesagt unterscheidet QPlayer über $ theta $ die ursprünglichen und doppelten Lösungen von QP der Form

$$ begin{align} min_{x} & ~frac{1}{2}x^{T}H(theta)x+g(theta)^{T}x \ text{st} & ~A(theta) x = b(theta) \ & ~l(theta) leq C ( theta) x leq u ( theta) end {align} $$

Wo $ x in mathbb {r}^n $ ist die Optimierungsvariable. Die objektive Funktion wird durch eine positive semidefinitische Matrix definiert $ H ( theta) in mathcal {s}^n _+$ und ein Vektor $ g ( theta) in mathbb {r}^n $ . Die linearen Einschränkungen werden durch die Matrix zur Gleichstellung der Unstimmigkeiten definiert $ A ( theta) in mathbb {r}^{n_ text {eq} times n} $ und die Matrix der Ungleichheitskonstruktion $ C ( theta) in mathbb {r}^{n_ text {in} times n} $ und die Vektoren $ b in mathbb {r}^{n_ text {eq}} $ Anwesend $ l ( theta) in mathbb {r}^{n_ text {in}} $ Und $ u ( theta) in mathbb {r}^{n_ text {in}} $ so dass $ b_i in mathbb {r}, ~ forall i = 1, ..., n_ text {eq} $ Und $ l_i in mathbb {r} cup { - infty} $ Und $ u_i in mathbb {r} cup { + infty}, ~ forall i = 1, ..., n_ text {in} $ .

QPlayer kann strukturiertere Architekturen lernen. Zum Beispiel, $ theta $ kann nur darin bestehen, einige Elemente von zu lernen $ A $ Während des Vermeidens $ B $ Behoben (siehe z. QPlayer kann auch LPS unterscheiden. QPlayer ermöglicht einen parallelisierten Kalkül über CPUs und ist mit Pytorch verbunden.

Zitieren QPlayer

Wenn Sie QPlayer für Ihre Arbeit verwenden, empfehlen wir Ihnen, das zugehörige Papier zu zitieren.

Installationsverfahren

Bitte befolgen Sie die Installationsverfahren hier.