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 **

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

• Other solvers will be posted in the future

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

result

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.

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 ***.

• • Since each solver uses a different algorithm, the result may change depending on the nature of the problem. *

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 Document ・ CVXPY Document ・ PICOS memo (semidefinite programming problem) ・ Solving cone programming problems using PICOS ・ Semidefinite 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