In this article, we will compare the SDP execution time of PICOS
and CVXPY
, which are python libraries for solving SDP.
** 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.
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 |
○ | ○ | - | ○ | - |
-*** 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
numpy.random
.% timeit
.· 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} }$
https://github.com/teatea6666/sdpcmp/blob/master/SDPSpeedCompare.ipynb
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 |
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.
-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 ***.
-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.
・ 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
Recommended Posts