Gibt es eine eingeschränkte nichtlineare Optimierungsbibliothek wie IPOPT, die auf GPUs ausgeführt wird?

Jemand in meinem Team möchte IPOPT parallelisieren. (zumindest einige Funktionen davon). Ich konnte keine GPU-Implementierung oder ein ähnliches Paket finden. Ich habe auch nichts in ihren Dokumenten gefunden.

Die Frage ist also, gibt es eine Alternative, die bereits auf der GPU implementiert ist? oder zumindest jemand, der daran arbeitet, es auf die GPU zu portieren, damit wir zusammenarbeiten können?

tl; dr: Mein allgemeiner Eindruck aus der Literatur ist, dass Beschleunigungen bescheiden sind (falls vorhanden). Der Hauptkern, den Sie in diesen Methoden sehen, ist eine Methode mit geringer Dichte (z. B. LU mit geringer Dichte, LDLT mit geringer Dichte), und die Speicherzugriffe sind unregelmäßig. Diese Eigenschaften begünstigen nicht die Verwendung von GPUs. Auch parallele IPMs stecken noch in den Kinderschuhen. Ich vermute immer noch, dass Leute an GPU-Implementierungen arbeiten werden, aber ich bin skeptisch, dass viel von ihnen kommen wird. (IPMs mit verteiltem Speicher scheinen jedoch etwas vielversprechender und nützlicher zu sein.)

Einige Leute haben an IPMs (Interior-Point-Methoden) für GPUs gearbeitet:

• Smith, Gondzio und Hall entwickelten ein IPM für lineare Programme (LPs), das eine 4-10-fache Beschleunigung erreichte
• Jung und O'Leary betrachten einige der linearen Algebra-Kernel in IPMs für LPs und sehen bescheidene Beschleunigungen für GPUs bei größeren Problemen in ihrem Testsatz

Im Allgemeinen vergleichen die Zeitungen ihre Arbeit nicht mit hoch abgestimmten LP-Lösern. Jung und O'Leary vergleichen sich mit Linprog, was für die meisten Praktizierenden nicht die Wahl wäre, und der Eindruck, den ich beim Scannen des Papiers von Smith et al. Habe, ist, dass eine serielle Innenpunktmethode von Grund auf neu geschrieben wurde. Angesichts der Tatsache, dass Hall sehr an Open-Source-LP-Lösern beteiligt ist, nehme ich diese Arbeit etwas ernster. Einer der besseren Open-Source-LP-Löser da draußen ist Clp, das Hall unterhält, und wenn sie diesen Code verwendet hätten, würde er namentlich erwähnt. Ich würde also mehr Aufmerksamkeit schenken, wenn diese Codes bereits hochgradig abgestimmte Löser beschleunigen würden, anstatt einmalige serielle Vergleiche, die nicht auf dem neuesten Stand der Technik sind.

Das heißt, die vorhandene Arbeit ist für LPs, und Sie fragen wahrscheinlich nach einem nichtlinearen Programmierlöser (NLP), denn genau das ist IPOPT. Folgendes weiß ich über den NLP-Solver-Fall:

• Das Parallelisieren von IPMs ist im Allgemeinen eine Herausforderung (für den LP- und SOCP-Fall siehe Elemental ; Sie würden für ein allgemeines IPM so etwas wie die SOCP-Version (oder eine QP-Version) verwenden
• Wenn Ihr NLP keine offensichtliche Struktur hat (z. B. kein stochastisches Programm, keine offensichtliche Randblock-Winkelstruktur, kein PDE-eingeschränktes Optimierungsproblem, bei dem Vorkonditionierer für die PDE bekannt sind) Die besten linearen Algebra-Methoden umfassen Methoden mit geringer Dichte (z. B. LU, LDLT) mit unregelmäßigen Speicherzugriffen, die normalerweise nicht für GPU-Architekturen geeignet sind (wie bereits erwähnt).
• Wenn Ihr NLP eine offensichtliche Struktur aufweist, möchten Sie einen trägheitsfreien Liniensuchalgorithmus verwenden, für den keine Trägheitsfaktorisierung erforderlich ist (basierend auf den jüngsten Arbeiten von Chiang und Zavala ), sodass Sie bekannte Vorkonditionierer verwenden können, um zu helfen Löse das Karush-Kuhn-Tucker-System
• Die besten verfügbaren Parallelmatrix-Innenpunktmethoden, die mir bekannt sind, sind die von Gondzio ( Implementierungspapier, Theoriepapier ) und von Waechter et al. ( Groß innerer Punkt Überblick Papier , geht das Papier in mehr Detail über die Umsetzung von großen inneren Punkt Methoden ); Es gibt auch Algorithmen von Petra, Zavala et al., die die Struktur ausnutzen ( strukturiertes nicht konvexes Optimierungspapier , Schur-Komplement für Papier mit Innenpunktmethoden ).

Die meisten Forschungen scheinen an der Parallelität für den Fall des verteilten Speichers zu arbeiten (was schwierig genug ist). Es gibt einige Arbeiten am Shared-Memory-Fall für LP- und QP-Löser, da diese Arbeit es in kommerzielle Codes (z. B. Gurobi, CPLEX, Xpress) schafft. Bestehende Arbeiten sind interessant, aber für GPUs scheint es noch nichts Überzeugendes zu geben, mit Ausnahme spezieller Anwendungen (z. B. maschinelles Lernen, für die Sie verschiedene Algorithmen verwenden können, die besser für GPUs geeignet sind).

Im Allgemeinen ist eine nichtlineare Optimierung schwer zu parallelisieren, da der Schrittalgorithmus sehr sequentiell ist. GPUs sind langsamer als CPUs, sodass Sie nur dann eine Beschleunigung erhalten, wenn Sie ein Problem haben, das sehr parallel ist (dh Tausende von Threads). Daher würde ich keine große Beschleunigung erwarten (oder eine, die normalerweise langsamer ist), wenn ich den nichtlinearen Löser auf die GPU setze. Das ist höchstwahrscheinlich der Grund, warum niemand es gut gemacht hat und die meisten Leute es nicht versuchen würden.

Wenn andererseits Ihre Ziel- und Einschränkungsfunktionen hochparallel (oder vektorisiert) berechnet werden können, können Sie eine massive Beschleunigung erzielen, indem Sie Ihre Ziel- / Einschränkungsfunktionen auf der GPU lösen. Dies ist eine gängige Methode zur Verwendung von GPUs mit nichtlinearer Optimierung, da die GPU-Beschleunigung für den schwierigsten (und parallelsten) Teil des Codes verwendet wird und daher wahrscheinlich die effizienteste ist.

Ich bin etwas spät dran, aber die kurze Antwort lautet: Ja, es ist möglich, eine interne Punktmethode für GPUs zu parallelisieren. Ob dies jedoch erfolgreich ist oder nicht, hängt von der Struktur des Problems ab. In Bezug auf vorhandene Software kann Optizelle dies tun. Besorgen Sie sich den Entwicklungszweig, bis in naher Zukunft eine neue Version erscheint.

Die Situationen unterscheiden sich geringfügig, je nachdem, ob das ursprüngliche Problem Gleichheiten oder Ungleichungen enthält oder nicht. Es gibt verschiedene Möglichkeiten, dies zu tun, aber meiner Meinung nach ist der beste Weg, dies bei Problemen mit nur Ungleichheitsbeschränkungen zu tun, die Verwendung einer Newton-Methode mit ungenauer Vertrauensregion in Kombination mit einer Methode mit zwei ursprünglichen inneren Punkten.

Nur für Ungleichungen finden Sie die grundlegende ungenaue Newton-Methode für Vertrauensbereiche in der numerischen Optimierung von Nocedal und Wright auf Seite 171 oder auf den Vertrauensbereichsmethoden von Conn, Gould und Toint auf Seite 205. Dieser Algorithmus kann erfolgreich mit einer Primärmethode kombiniert werden. Dual-Interior-Point-Methode unter Verwendung der modifizierten Truncated-CG-Methode ab Seite 890 des Papiers Eine Interior-Point-Methode für die nichtlineare Programmierung in großem Maßstab von Byrd, Hribar und Nocedal. Persönlich gefällt mir nicht, wie sie ihr inneres Punktesystem einrichten, daher würde ich ihre innere Punktformulierung nicht verwenden, aber das ist die Präferenz. NITRO ist ein guter Algorithmus. In Bezug auf die Details des Innenpunkts wird im Handbuch von Optizelle in seinem Handbuch erläutert, wie dies zu tun ist. Ich sollte wahrscheinlich ein aktualisiertes Handbuch veröffentlichen,

Für den Fall sowohl mit Ungleichheits- als auch mit Gleichheitsbeschränkungen glaube ich, dass der beste Algorithmus darin besteht, die ungenaue SQP-Methode mit zusammengesetzten Schritten für Vertrauensbereiche von Heinkenschoss und Ridzal in einem Artikel mit dem Titel Eine matrixfreie SQP-Methode für Vertrauensbereiche für die Optimierung mit eingeschränkten Gleichheitsbereichen zu kombinieren. Grundsätzlich funktioniert der Prozess des Anheftens einer inneren Punktmethode ziemlich genau wie der uneingeschränkte Fall, außer dass der quasinormale Schritt ebenfalls sichergestellt werden muss.

Was die Parallelisierungsmöglichkeiten angeht, funktionieren die oben genannten Algorithmen gut, da diese Algorithmen matrixfrei implementiert werden können. Insbesondere die Implementierung von Optizelle für das Problem

$\min\limits_{x\in X}\{ f(x) : g(x)=0, h(x)\geq 0\}$

Erfordert, dass der Benutzer eine Implementierung für bereitstellt

• $f(x), \nabla f(x), \nabla^2 f(x)\partial x$

• $g(x), g^\prime(x)\partial x, g^\prime(x)^*\partial y, (g^{\prime\prime}(x)\partial x)^* \partial y$

• $h(x), h^\prime(x)\partial x, h^\prime(x)^*\partial y, (h^{\prime\prime}(x)\partial x)^* \partial y$

Es ist egal, woher diese Implementierungen kommen oder wie sie parallelisiert sind. Sie können im gemeinsam genutzten Speicher, im verteilten Speicher oder in GPUs ausgeführt werden. Es spielt keine Rolle. Was für ein bestimmtes Problem am besten funktioniert, hängt von der Struktur ab. Darüber hinaus muss der Benutzer eine lineare Algebra für bereitstellen

• init: Memory allocation and size setting
• copy: y <- x (Shallow. No memory allocation.)
• scal: x <- alpha * x
• axpy: y <- alpha * x + y
• innr: innr <- <x,y>
• zero: x <- 0
• rand: x <- random
• prod: Jordan product, z <- x o y
• id: Identity element, x <- e such that x o e = x
• linv: Jordan product inverse, z <- inv(L(x)) y where L(x) y = x o y
• barr: Barrier function, barr <- barr(x) where x o grad barr(x) = e
• srch: Line search, srch <- argmax {alpha \in Real >= 0 : alpha x + y >= 0} where y > 0
• symm: Symmetrization, x <- symm(x) such that L(symm(x)) is a symmetric operator

Diese Vorgänge können im seriellen, parallelen, verteilten Speicher, im gemeinsam genutzten Speicher oder auf GPUs ausgeführt werden. Es spielt keine Rolle. Was am besten ist, hängt von der Problemstruktur ab.

Schließlich gibt es die linearen Systeme und es gibt drei, die bereitgestellt werden können:

• Vorkonditionierer für$\nabla^2 f(x)$
• Linker Vorkonditionierer für$g^\prime(x)g^\prime(x)^*$
• Richtiger Vorkonditionierer für$g^\prime(x)g^\prime(x)^*$

Jeder dieser Vorkonditionierer kann entweder im seriellen oder parallelen, verteilten Speicher oder gemeinsam genutzt oder auf GPUs implementiert werden. Grundsätzlich ist der erste Vorkonditionierer der Vorkonditionierer für das verkürzte CG-System, das den Optimalitätssystemen zugeordnet ist. Die letzten beiden Vorkonditionierer werden für die erweiterten Systemlösungen verwendet, die dem zusammengesetzten Schritt-SQP-Algorithmus zugeordnet sind. Im Allgemeinen erhalten Sie hier Ihren größten Leistungsschub. Stellen Sie sich vor, die Einschränkung repräsentiert eine Art PDE. Dann entspricht der Vorkonditionierer für einer Vorwärts-PDE-Lösung, gefolgt von einer adjungierten PDE-Lösung. Beachten Sie, wenn sie quadratisch wären,g ' ( x ) g ' ( x ) ∗ ( g ' ( x ) g ' ( x ) ∗ ) - 1 = g ' ( x ) - ∗ g ' ( x ) - $g$$g^\prime(x)g^\prime(x)^*$$(g^\prime(x)g^\prime(x)^*)^{-1}=g^\prime(x)^{-*}g^\prime(x)^{-1}$. Für eine große Anzahl von PDE-Formulierungen, wie z. B. Finite-Differenzen-Methoden mit expliziten Zeitintegratoren, können diese Lösungen auf einer GPU sehr gut parallelisiert werden.

Schließlich arbeiten die Algorithmen in Optizelle an symmetrischen Kegelproblemen, zu denen gebundene, Kegel zweiter Ordnung und semidefinite Einschränkungen gehören. Trotzdem neigen die linearen Kegellösungen im Allgemeinen dazu, diese zu übertreffen. Grundsätzlich können lineare Kegellösungen die Machbarkeit und Optimalitätslösungen eines wirklich kompakten Systems reduzieren, das nach Choleski berücksichtigt werden kann. Da Optizelle mit nichtlinearen Systemen arbeitet, kann es das nicht wirklich. Zumindest weiß ich nicht wie. Darüber hinaus gibt es Einschränkungen hinsichtlich der Größe der SDP-Blöcke, die Optizelle verarbeiten kann. Der Betreiberlinvoben erfordert die Umkehrung der SDP-Matrizen und diese Umkehrung ist für große Blöcke wirklich teuer. Darüber hinaus gibt es einen zusätzlichen Schutz, der eine Choleski-Faktorisierung erfordert. Diese Faktorisierungen lassen sich auf einer GPU nicht wirklich gut parallelisieren. Zumindest kenne ich keine Implementierung, die gut parallelisiert werden kann. Unter dem Strich sollten Sie als lineares Kegelprogramm einen linearen Kegellöser wie CSDP oder SDPT3 verwenden.

TLDR; Verwenden Sie Optizelle . Es ist kostenlos, Open Source und BSD-lizenziert. Ich habe es auf ungefähr eine halbe Milliarde Variablen skaliert und es hat gut funktioniert. Ich habe es mit GPUs betrieben und es hat gut funktioniert. Ob es mit einer GPU gut funktioniert oder nicht, hängt davon ab, ob die oben genannten Vorgänge auf einer GPU gut parallel sind oder nicht.