Comparaison du temps d'exécution de Python SDP

Dans cet article, nous comparerons le temps d'exécution SDP de PICOS et CVXPY, qui sont des bibliothèques python pour résoudre SDP.

SDP (problème de planification à valeur semi-fixe)

** La programmation semi-définie (SDP) ** est un type de problème d'optimisation convexe. Il attire l'attention dans les domaines de la planification mathématique et du contrôle de système et fait actuellement l'objet de recherches actives.

[Problème de planification à valeur semi-fixe-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 a les problèmes suivants, par exemple.

Supposons qu'une matrice carrée $ A $ soit donnée. P\succ0, PA-A^TP\prec0 Trouvez la matrice P qui satisfait. ($ P \ succ 0 $ signifie que $ P $ est une matrice canonique.)

Dans SDP, les contraintes sont données par ** Linear Matrix Inequality (LMI) **.

L'existence de la solution P dans ce problème et le fait que toutes les valeurs propres de A sont négatives sont équivalentes. Par conséquent, si ce problème est résolu, il peut être confirmé que toutes les valeurs propres de A sont négatives.

Dans cet exemple, on dit qu'il est plus rapide de calculer directement la valeur propre de A. Si vous souhaitez combiner ** plusieurs contraintes LMI ** ou ** optimiser la fonction objectif **, vous devez la résoudre en SDP. Dans le domaine du contrôle système, les spécifications de contrôle peuvent être exprimées par de multiples contraintes LMI. La résolution de SDP est très utile.

Vous pouvez utiliser MATLAB et Python comme outils pour résoudre le SDP numériquement.

Bibliothèque SDP Python

Autant que je sache, il existe trois bibliothèques pour résoudre SDP en Python: PICOS, CVXPY et PYLMI-SDP. Parmi ceux-ci, «PYLMI-SDP» n'est pas géré car aucun exemple d'utilisation ou document n'a pu être trouvé.

«PICOS» et «CVXPY» agissent comme des interfaces qui transmettent le SDP décrit au solveur. Le solveur est la partie qui entreprend réellement le travail de résolution du problème.

Les solveurs SDP pris en charge par «PICOS» et «CVXPY» sont indiqués ci-dessous.

** Tableau: solveur SDP pris en charge par PICOS, CVXPY **

Description de chaque solveur

• *** CVXOPT *** ・ ・ ・ Installé avec PICOS, CVXPY.
• *** MOSEK *** ・ ・ ・ Commercial. La licence académique est gratuite.
• • *** SMCP *** ・ ・ ・ Ce document.
• *** SCS *** ・ ・ ・ Créé à partir de ce papier. Il est installé avec CVXPY.
• *** SDPA-P *** ... Probablement basé sur cet article.

Comme mentionné ci-dessus, il existe de nombreuses bibliothèques et solveurs. C'est bien que beaucoup de gens l'aient développé et enrichi, mais ** je ne sais pas lequel utiliser **. Par conséquent, je voudrais comparer le temps d'exécution de SDP en utilisant ces derniers.

Cette fois, nous comparerons les 5 combinaisons suivantes à l'exclusion de «SMCP» et «SDPA-P» dans le tableau ci-dessus. PICOS×CVXOPT, PICOS×MOSEK CVXPY×CVXOPT, CVXPY×MOSEK, CVXPY×SCS

• D'autres solveurs seront postés dans le futur

procédure

1. Générez une matrice constante $ A $ avec numpy.random.
2. Résolvez le SDP suivant. $ ~~~~~~~~~~~~~~~~~ \rm{min}~~\rm{trace}(\it{P}) ~~~ \rm{s.t.} ~~ \it{P}\succ \rm{0},~\it{PA-A^TP}\prec \rm{0}.$
3. Mesurez le temps d'exécution moyen avec «% timeit».
4. Mesurez pour chacun des paramètres suivants.

· Commande $ n $ de la matrice constante $ A $ et de la matrice variable $ P $ $ ~~~~~~~~~~~~~~~~~ 1\leq n \leq20$ ・ Tolérance $ tol $ $ ~~~~~~~~~~~~~~~~~ tol={ 10^{-4},10^{-6},10^{-8},10^{-10},10^{-12} }$

Code d'exécution

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

Environnement d'exécution

résultat

L'axe horizontal correspond à la taille de la matrice et l'axe vertical correspond au temps d'exécution. La tolérance est fixée à $ tol = 1e-08 $.

Le plus rapide est «PICOS» × ___ MOSEK___. Le finaliste est «PICOS» × *** CVXOPT ***. A part ça, c'est presque la même chose.

L'axe horizontal est la tolérance et l'axe vertical est le temps d'exécution. La taille de la matrice est fixée à $ n = 2 $.

Le plus rapide est «PICOS» × ___ MOSEK___. Le finaliste est «PICOS» × *** CVXOPT ***. A part ça, c'est presque la même chose. Cependant, PICOS × *** MOSEK *** n'a pas pu être exécuté avec une erreur indiquant que la tolérance de $ 10 ^ {-10} $ ou plus était trop petite.

Résumé

・ Lorsqu'il y a beaucoup de variables et de contraintes, ou lors de la résolution d'une grande quantité de SDP, PICOS × *** MOSEK *** est recommandé. ・ Si vous ne pouvez pas utiliser la licence commerciale ou la licence académique gratuite de *** MOSEK ***, veuillez utiliser PICOS × *** CVXOPT ***.

• • Étant donné que chaque solveur utilise un algorithme différent, le résultat peut changer en fonction de la nature du problème. *

mémorandum

-PICOS a récemment été mis à jour vers la version 2.0 et a un bogue (au 22 mars 2020). → Réécrire la bibliothèque et surpasser. (SearchTime Zero Division Error: commentez la ligne appropriée et entrez une valeur appropriée (overheadTime = 1).) ・ Dans PICOS × *** MOSEK ***, une erreur se produit lorsque l'objectif est réglé sur" rechercher ". Insérez une fonction appropriée avec «min» et résolvez-la. -Un bug qui causait un mystérieux bavardage dans CVXPY s'est produit, et il a été résolu en mettant à jour anaconda.

Informations référencées

・ Document PICOS ・ Document CVXPY ・ Mémo PICOS (problème de planification à valeur fixe semi-positive) ・ Résolution du problème de planification des cônes à l'aide de PICOS ・ Programmation semi-définie en Python ・ [Contrôle du système par LMI - Approche systématique pour une conception de système de contrôle robuste](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 = & hvphytlocint = 52vcvcmdl = & hvphytlocint = 52vlocint = 52 ・ [Conception du système de contrôle par l'approche de l'inégalité matricielle (série d'ingénierie de contrôle système)](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 = 433903rd3235 = 3012d9b4-51ca-4be3-bcd5-36cd21bdbdab & pd_rd_w = d3p5i & pd_rd_wg = gyoow & pf_rd_p = 1893a417-ba87-4709-ab4f-0dece788c310 & pf_rd_psr = QVTZB96 & pf_rd_ psr = QVTZB96