Algorithm Complexity for solving SDP

1

Hi,

I have the following SDP optimization problem, and I needed to know the complexity of the algorithm that CVX uses to solve it:

cvx_begin sdp
    variable W(N, N) complex
    maximize real(trace(Q * W))
    subject to
        diag(W) == ones(N, 1);
        W == semidefinite(N); 
cvx_end

Does anyone know how to figure out the complexity of the solver for this problem?
I saw somewhere that CVX uses SeDuMi for solving SDP with complexity of O(N^4.5 log(1/epsilon)). Does this apply to every form of SDP, or the complexity changes with the form of SDP?

Thanks.

2

I’m afraid I can’t help you here. You should consult the academic literature on the complexity of symmetric primal/dual methods.