Hi,
I am trying to determine the time and space complexities of solving SDP with a simple linear matrix inequality constraint. The problem has a very standard form:
\sum_{i=1}^n x_iM_i\succeq 0,
where x_i's are n variables and M_i's are n given matrices (sparse actually) with dimension m\times m. I am using Mosek so I assume that the algorithm used is the primal-dual interior-point method.
I have searched a few papers on this topic, but I cannot extract the correct big-O complexity from those papers. One thing I am sure about is the (Newton) iteration complexity is O(\sqrt{m}\log{(1/\epsilon)}) with the \epsilon being the tolerance. However, I didn’t find an explicit expression for the per-iteration complexity. I even tried to ask ChatGPT and Claude, which gave inconsistent results: O(m^2n^2+n^3+m^3) from ChatGPT and O(m^2n^2+n^3+nm^3) from Claude. Can anyone help me with the correct time and space complexities with the necessary references?
Sorry if this question has been asked many times on this forum. Since I need to include this complexity analysis in a scientific paper, I want it to be accurate.
Thanks