interior point computational complexity for SDP

Question

I am trying to get the complexity of the SDP problem for my specific problem, but I’m facing some problems.

I found in the literature that the complexity of the SDP problem for an interior point per iteration is O(m * n^3 + m^2 * n^2 + m^3), where m is the number of constraints with (n x n) semidefinite matrix. It also implies that this (n x n) semidefinite matrix is the problem variable by saying there are n^2 variables.

This is where my problem starts because I can not determine n and m in my problem. When many constraints include equalities, inequalities, and semidefinite ones, how can I calculate n and m?

My problem in CVX format is as follows:

cvx_begin SDP
    variable b(n+2,1) nonnegative
    variable B(n+2,n+2) nonnegative
    variable u(2,1) nonnegative
    variable r(n,1) nonnegative
    variable v
    
    minimize ( trace(W*(A*B*A.' - 2*A*b*c.' + c*c.')) + rho_c*sum(r.^2) + rho_n*(b(n+1)^2+b(n+2)^2) )
    subject to
        [B,b;b.',1] == semidefinite(n+3);
        [eye(2),u;u.',v] == semidefinite(3);
        for i = 1:n
            B(i,i) == [ai(:,i).', -1] * [eye(2),u;u.',v] * [ai(:,i); -1];
            b(i) >= 0;
            r(i) >= 0;
            vi(i) + r(i) >= norm(u-ai(:,i));
        end
cvx_end

Answer 1

Throughout, I will use $\texttt{n}$ to refer to the "n" in your code, $n$ to refer to the size of the semidefinite matrix variable (what the literature calls $n$), and $m$ to be the number of constraints.

Calculating $n$ is fairly easy. We can see that your first two constraints are saying, "this first matrix of variables must be a $(\texttt{n}+3) \times (\texttt{n}+3)$ positive semidefinite matrix, and this second matrix of variables must be a $3 \times 3$ positive semidefinite matrix. You could combine these into a single $(\texttt{n}+6) \times (\texttt{n}+6)$ positive semidefinite matrix of variables, where some ($3\texttt{n}+10$) variables are constrained to be 0. Thus $n = \texttt{n}+6$. The constraints are also fairly easy, but requires knowing that usually nonnegativity and positive semidefiniteness constraints are not counted. With that in mind you have 2 constraints for each $i$ from $1$ to $\texttt{n}$ so $m = 2\texttt{n}$.