Dear experts,
Hello, I`m new here!
I`m trying to compare the computational complexities about the SDP solvers with my solver.
So, I trying to analyze the computational complexity of CVX solvers (e.g., MOSEK, SeDuMi) for solving SDP which stems from atomic norm minimization.
But, I really don`t know how can I analyze the computational complexities about the CVX solvers.
Sorry about the ignorant question.
Really thanks.
Try search for
computational complexity
in the posts of this forum.
Thanks for answer.
I`ve found your previous answer.
#-----
All the problems that CVX can solve can in theory be solved in polynomial time using an interior-point algorithm. Therefore, you can look up the complexity solving your problem with an interior-point algorithm. I doubt you will get a more accurate answer.
PS. Try look in the ph.d. thesis of Michal Grant about CVX.
#-----
From this, if analyzing the computational complexity with the interior-point algorithm, there`s no difference respect to the Big O between the different CVX solvers (e.g., MOSEK and SeDuMi)?
Again, thanks for replying
Theoretical complexity can be used to prove the theoretical superiority of an algorithm.
Practical experiments can be used to prove the practical superiority of a piece of software implementing (multiple) algorithms.
IMO none of the authors (and I am one of them) of the software you mention would use theoretical complexity to claim superiority of their software. Theoretical complexity is just one element and perhaps not an important element in the evaluation of the software.
See also