Vergleich der Ausführungszeit von Python SDP

In diesem Artikel werden wir die SDP-Ausführungszeit von PICOS und CVXPY vergleichen, die Python-Bibliotheken zum Lösen von SDP sind.

SDP (Semi-Fixed Value Planning Problem)

** SemiDefinite Programming (SDP) ** ist eine Art konvexes Optimierungsproblem. Es zieht Aufmerksamkeit in den Bereichen mathematische Planung und Systemsteuerung auf sich und wird derzeit aktiv erforscht.

[Semi-Fixed Value Planning Problem-Wikipedia](https://ja.wikipedia.org/wiki/%E5%8D%8A%E6%AD%A3%E5%AE%9A%E5%80%A4%E8%A8 % 88% E7% 94% BB% E5% 95% 8F% E9% A1% 8C)

SDP hat beispielsweise die folgenden Probleme.

Angenommen, eine quadratische Matrix $ A $ ist gegeben. P\succ0, PA-A^TP\prec0 Finden Sie die Matrix P, die erfüllt. ($ P \ succ 0 $ bedeutet, dass $ P $ eine kanonische Matrix ist.)

In SDP sind Einschränkungen durch ** Linear Matrix Inequality (LMI) ** gegeben.

Die Existenz der Lösung P in diesem Problem und die Tatsache, dass alle Eigenwerte von A negativ sind, sind äquivalent. Wenn dieses Problem gelöst ist, kann daher bestätigt werden, dass alle Eigenwerte von A negativ sind.

In diesem Beispiel wird gesagt, dass es schneller ist, den Eigenwert von A direkt zu berechnen. Wenn Sie ** mehrere LMI-Einschränkungen ** kombinieren oder ** die Zielfunktion ** optimieren möchten, müssen Sie diese als SDP lösen. Auf dem Gebiet der Systemsteuerung können Steuerungsspezifikationen durch mehrere LMI-Einschränkungen ausgedrückt werden. Das Lösen von SDP ist sehr nützlich.

Sie können MATLAB und Python als Werkzeuge verwenden, um SDP numerisch zu lösen.

Python SDP-Bibliothek

Soweit ich weiß, gibt es drei Bibliotheken zum Lösen von SDP in Python: "PICOS", "CVXPY" und "PYLMI-SDP". Von diesen wird "PYLMI-SDP" nicht behandelt, da kein Verwendungsbeispiel oder Dokument gefunden werden konnte.

PICOS und CVXPY fungieren als Schnittstellen, die das beschriebene SDP an den Solver weitergeben. Der Löser ist der Teil, der tatsächlich die Arbeit zur Lösung des Problems übernimmt.

Die von "PICOS" und "CVXPY" unterstützten SDP-Löser sind nachstehend aufgeführt.

** Tabelle: SDP-Solver, unterstützt von PICOS, CVXPY **

Beschreibung jedes Lösers

• *** CVXOPT *** ・ ・ ・ Zusammen mit PICOS, CVXPY installiert.
• *** MOSEK *** ・ ・ ・ Kommerziell. Die akademische Lizenz ist kostenlos.
• • *** SMCP *** This ・ ・ Dieses Dokument.
• *** SCS *** ・ ・ ・ Erstellt basierend auf diesem Dokument. Es wird mit "CVXPY" installiert.
• *** SDPA-P *** ... basiert wahrscheinlich auf diesem Dokument.

Wie oben erwähnt, gibt es viele Bibliotheken und Löser. Es ist gut, dass viele Leute es entwickelt und bereichert haben, aber ** ich weiß nicht, welches ich verwenden soll **. Daher möchte ich die Ausführungszeit von SDP mit diesen vergleichen.

Dieses Mal werden wir die folgenden 5 Kombinationen mit Ausnahme von "SMCP" und "SDPA-P" in der obigen Tabelle vergleichen. PICOS×CVXOPT, PICOS×MOSEK CVXPY×CVXOPT, CVXPY×MOSEK, CVXPY×SCS

• Weitere Löser werden in Zukunft veröffentlicht

Verfahren

1. Generieren Sie eine konstante Matrix $ A $ mit numpy.random.
2. Lösen Sie das folgende SDP. $ ~~~~~~~~~~~~~~~~~ \rm{min}~~\rm{trace}(\it{P}) ~~~ \rm{s.t.} ~~ \it{P}\succ \rm{0},~\it{PA-A^TP}\prec \rm{0}.$
3. Messen Sie die durchschnittliche Ausführungszeit mit "% timeit".
4. Messen Sie für jeden der folgenden Parameter.

· Bestellen Sie $ n $ der konstanten Matrix $ A $ und der variablen Matrix $ P $ $ ~~~~~~~~~~~~~~~~~ 1\leq n \leq20$ ・ Toleranz $ tol $ $ ~~~~~~~~~~~~~~~~~ tol={ 10^{-4},10^{-6},10^{-8},10^{-10},10^{-12} }$

Ausführungscode

https://github.com/teatea6666/sdpcmp/blob/master/SDPSpeedCompare.ipynb

Ausführungsumgebung

Ergebnis

Die horizontale Achse ist die Größe der Matrix und die vertikale Achse ist die Ausführungszeit. Die Toleranz ist auf $ tol = 1e-08 $ festgelegt.

Das schnellste ist PICOS × ___ MOSEK___. Der Zweitplatzierte ist "PICOS" × *** CVXOPT ***. Davon abgesehen ist es fast dasselbe.

Die horizontale Achse ist die Toleranz und die vertikale Achse ist die Ausführungszeit. Die Größe der Matrix ist auf $ n = 2 $ festgelegt.

Das schnellste ist PICOS × ___ MOSEK___. Der Zweitplatzierte ist "PICOS" × *** CVXOPT ***. Davon abgesehen ist es fast dasselbe. "PICOS" × *** MOSEK *** konnte jedoch nicht mit dem Fehler ausgeführt werden, dass die Toleranz von $ 10 ^ {-10} $ oder mehr zu klein war.

Zusammenfassung

・ Wenn es viele Variablen und Einschränkungen gibt oder wenn eine große Menge von SDP gelöst wird, wird PICOS × *** MOSEK *** empfohlen. ・ Wenn Sie die kommerzielle Lizenz oder die kostenlose akademische Lizenz von *** MOSEK *** nicht verwenden können, verwenden Sie bitte PICOS × *** CVXOPT ***.

• • Da jeder Löser einen anderen Algorithmus verwendet, kann sich das Ergebnis je nach Art des Problems ändern. * *

Memorandum

-PICOS wurde kürzlich auf Version 2.0 aktualisiert und weist einen Fehler auf (Stand: 22. März 2020). → Schreiben Sie die Bibliothek neu und übertreffen Sie. (SearchTime Zero Division Error: Kommentieren Sie die entsprechende Zeile aus und geben Sie einen geeigneten Wert ein (OverheadTime = 1).) ・ In "PICOS" × *** MOSEK *** tritt ein Fehler auf, wenn das Ziel auf "Finden" gesetzt ist. Fügen Sie mit'min' eine entsprechende Funktion ein und lösen Sie sie.

• Ein Fehler, der eine mysteriöse Ausführlichkeit in "CVXPY" verursachte, trat auf und wurde durch Aktualisieren der Anakonda behoben.

Referenzierte Informationen

・ PICOS-Dokument ・ CVXPY-Dokument ・ PICOS-Memo (halbpositives Problem bei der Planung fester Werte) ・ Lösen des Kegelplanungsproblems mit PICOS ・ Semidefinite Programmierung in Python ・ [Systemsteuerung durch LMI - Systematischer Ansatz für ein robustes Steuerungssystemdesign](https://www.amazon.co.jp/LMI%E3%81%AB%E3%82%88%E3%82%8B] % E3% 82% B7% E3% 82% B9% E3% 83% 86% E3% 83% A0% E5% 88% B6% E5% BE% A1-% E3% 83% AD% E3% 83% 90% E3% 82% B9% E3% 83% 88% E5% 88% B6% E5% BE% A1% E7% B3% BB% E8% A8% AD% E8% A8% 88% E3% 81% AE% E3% 81% 9F% E3% 82% 81% E3% 81% AE% E4% BD% 93% E7% B3% BB% E7% 9A% 84% E3% 82% A2% E3% 83% 97% E3% 83% AD% E3% 83% BC% E3% 83% 81-% E8% 9B% AF% E5% 8E% 9F% E7% BE% A9% E9% 9B% 84 / dp / 4627921012 / ref = asc_df_4627921012 /? Tag = jpgo-22 & linkCode = df0 & hvadid = 288872634447 & hvpos = & hvnetw = g & hvrand = 17342343416617666624 & hvpone = & hvptwo = & hvqmt = / hvdev = c & hvdvcmdl = & hvlocl = ・ [Steuerungssystemdesign nach Matrix-Ungleichungsansatz (System Control Engineering Series)](https://www.amazon.co.jp/%E8%A1%8C%E5%88%97%E4%B8%8D%E7% AD% 89% E5% BC% 8F% E3% 82% A2% E3% 83% 97% E3% 83% AD% E3% 83% BC% E3% 83% 81% E3% 81% AB% E3% 82% 88% E3% 82% 8B% E5% 88% B6% E5% BE% A1% E7% B3% BB% E8% A8% AD% E8% A8% 88-% E3% 82% B7% E3% 82% B9 % E3% 83% 86% E3% 83% A0% E5% 88% B6% E5% BE% A1% E5% B7% A5% E5% AD% A6% E3% 82% B7% E3% 83% AA% E3 % 83% BC% E3% 82% BA-% E5% B0% 8F% E5% 8E% 9F-% E6% 95% A6% E7% BE% 8E / dp / 4339033235 / ref = pd_aw_sbs_14_7? _ Encoding = UTF8 & pd_rd_i = 4339033235 & p_ = 3012d9b4-51ca-4be3-bcd5-36cd21bdbdab & pd_rd_w = d3p5i & pd_rd_wg = gyoow & pf_rd_p = 1893a417-ba87-4709-ab4f-0dece788c310 & pf_rd_r = QVTZ