I am reading a paper's introduction. It says from the point of view of speed and reliability, SDP solvers lag behind LP and SOCP.
However, as we know, we usually transform LP, SOCP, QCQP to SDP, and use software such as cvx, we can easily solve SDP.
Why SDP is expensive?
I think
- Interior point method is more expensive in large scale.
- Dealing matrices requires more resources.
Can anyone provide more strict and solid answer for this, particularly for reliability compared with LP and SOCP? (SDP can be solved with arbitrary accuracy; I am not sure what reliability here really mean.)
Well, the claim "we usually transform LP, SOCP, QCQP to SDP" is wrong to begin with. That is essentially what you never should do. LPs should be solved as LPs, QPs as QPs or possibly reformulated as an SOCP as Mosek does, SOCPs should be solved as SOCPs, and only if you actually have an SDP do you solve the problem as an SDP.
To see why it is more expensive to solve an SDP, you can read some papers on implementations. As an example of a step which is more expensive in an SDP solver compared to an LP solver, you typically perform line-searches to check feasibility. For an LP, that boils down to a $O(m\times n)$ operation if you have $m$ constraints and $n$ variables (you have to perform matrix-vector multiplication $Ax$) while in an SDP solver, you have to check feasibility by, e.g., eigenvalues or trial Cholesky, which is $O(m^3)$ if you have an LMI of size $m$. In general in the SDP solver, you have a lot of expensive matrix/matrix operations operations while an LP solver comes away with matrix/vector operations.