Python SDP runtime comparison

In this article, we will compare the SDP execution time of PICOS and CVXPY, which are python libraries for solving SDP.

SDP (Semidefinite Programming Problem)

** SemiDefinite Programming (SDP) ** is a type of convex optimization problem. It is attracting attention in the fields of mathematical planning and system control, and is currently being actively researched.

[Semidefinite programming 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 has the following problems, for example.

Suppose a square matrix $ A $ is given. P\succ0, PA-A^TP\prec0 Find the matrix P that satisfies. ($ P \ succ 0 $ means that $ P $ is a definite matrix.)

In SDP, constraints are given by ** Linear Matrix Inequality (LMI) **.

The existence of solution P in this problem and the fact that all eigenvalues of A are negative are equivalent. Therefore, if this problem is solved, it can be confirmed that all the eigenvalues of A are negative.

In this example, it is said that it is faster to calculate the eigenvalue of A directly. If you want to combine ** multiple LMI constraints ** or ** optimize the objective function **, you need to solve it as SDP. In the field of system control, control specifications may be expressed by multiple LMI constraints. Solving SDP is very useful.

You can use MATLAB and Python as tools to solve SDP numerically.

Python SDP library

As far as I know, there are three libraries for solving SDP in Python: PICOS, CVXPY, and PYLMI-SDP. Of these, PYLMI-SDP will not be dealt with because no usage example or documentation could be found.

PICOS and CVXPY act as interfaces that pass the described SDP to the solver. The solver is the part that actually undertakes the work of solving the problem.

The SDP solvers supported by PICOS and CVXPY are shown below.

** Table: SDP solver supported by PICOS, CVXPY **

CVXOPT MOSEK SMCP SCS SDPA-P
PICOS -
CVXPY - -

Description of each solver

-*** CVXOPT *** ・ ・ ・ Installed with PICOS, CVXPY. -*** MOSEK *** ・ ・ ・ Commercial. Academic license is free. --* *** SMCP *** ・ ・ ・ This paper. --*** SCS *** ・ ・ ・ Created based on this paper. It is installed with CVXPY. -*** SDPA-P *** ... Probably based on this paper.

As mentioned above, there are many libraries and solvers. It's good that many people have developed and enriched it, but ** I don't know which one to use **. Therefore, I would like to compare the execution time of SDP using these.

This time, we will compare the following 5 combinations excluding SMCP and SDPA-P in the above table. PICOS×CVXOPT, PICOS×MOSEK CVXPY×CVXOPT, CVXPY×MOSEK, CVXPY×SCS

procedure

  1. Generate a constant matrix $ A $ with numpy.random.
  2. Solve the following SDP. $ ~~~~~~~~~~~~~~~~~ \rm{min}~~\rm{trace}(\it{P}) ~~~ \rm{s.t.} ~~ \it{P}\succ \rm{0},~\it{PA-A^TP}\prec \rm{0}.$
  3. Measure the average execution time with % timeit.
  4. Measure for each of the following parameters.

· Degree $ n $ of constant matrix $ A $ and variable matrix $ P $ $ ~~~~~~~~~~~~~~~~~ 1\leq n \leq20$ ・ Tolerance $ tol $ $ ~~~~~~~~~~~~~~~~~ tol={ 10^{-4},10^{-6},10^{-8},10^{-10},10^{-12} }$

Execution code

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

Execution environment

Library version
anaconda 2019.03
python 3.7
Jupyter Lab
picos 2.0.0
cvxpy 1.0.28
cvxopt 1.2.0
mosek 9.1.13
scs 2.1.1.2

result

matsize.jpg The horizontal axis is the size of the matrix and the vertical axis is the execution time. The tolerance is fixed at $ tol = 1e-08 $.

The fastest is PICOS × ___ MOSEK___. The runner-up is PICOS × *** CVXOPT ***. Other than that, it is almost the same.

tolerance.jpg The horizontal axis is the tolerance and the vertical axis is the execution time. The size of the matrix is fixed at $ n = 2 $.

The fastest is PICOS × ___ MOSEK___. The runner-up is PICOS × *** CVXOPT ***. Other than that, it is almost the same. However, PICOS × *** MOSEK *** could not be executed with an error that the tolerance of $ 10 ^ {-10} $ or more was too small.

Summary

-If there are a large number of variables and constraints, or if you want to solve a large amount of SDP, PICOS × *** MOSEK *** is recommended. ・ If you cannot use the commercial license or free academic license of *** MOSEK ***, please use PICOS × *** CVXOPT ***.

memorandum

-PICOS has recently been updated to ver2.0 and has a bug (as of March 22, 2020). → Rewrite the library and surpass it. (SearchTime Zero Division Error: Comment out the relevant line and enter an appropriate value (overheadTime = 1).) ・ In PICOS × *** MOSEK ***, an error occurs when objective is set to'find'. Insert an appropriate function with'min'and solve it. -A bug that caused a mysterious verbose in CVXPY occurred, and it was solved by updating anaconda.

Referenced information

PICOS DocumentCVXPY DocumentPICOS memo (semidefinite programming problem)Solving cone programming problems using PICOSSemidefinite programming in Python ・ [System control by LMI --Systematic approach for robust control system design](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 = & hvlocint = & hvlocphy = 1009330 & hvtargid = pla-528 ・ [Control system design by matrix inequality approach (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 = 3012d9b4-51ca-4be3-bcd5-36cd21bdbdab & pd_rd_w = d3p5i & pd_rd_wg = gyoow & pf_rd_p = 1893a417-ba87-4709-ab4f-0dece788c310 & pf_rd_r = QVTZB96NPTWPADNZBQRH & psc = 1

Recommended Posts

Python SDP runtime comparison
First Python 3 ~ First comparison ~
Python package manager comparison
Python, Java, C ++ speed comparison
Null object comparison in Python
Receive runtime arguments in Python 2.7
Comparison of 4 Python web frameworks
Python runtime customization [sitecustomize, usercustomize]
About Python string comparison operators
Python 3 sorted and comparison functions
Python Note: About comparison using is
Java and Python basic grammar comparison
Python
Execute Python Script during CodeSys # RunTime
Python executable file conversion module comparison 2
Speed comparison of Python XML parsing
Closure 4 language comparison (Python, JavaScript, Java, C ++)
(Java, JavaScript, Python) Comparison of string processing
Comparison of Japanese conversion module in Python3
Python environment tool comparison chart for Rubyist
python string comparison / use'list'and'in' instead of'==' and'or'
Playing card class in Python (with comparison)
Learn Python! Comparison with Java (basic function)
Comparison of Python serverless frameworks-Zappa vs Chalice
Python> datetime> runtime arguments> start processing immediately
Comparison of matrix transpose speeds with Python
Free Python runtime environment Google Colaboratory memo
Time comparison: Correlation coefficient calculation in Python