# interior point computational complexity for SDP

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

• None of the following affects your problem, or is wrong in your current code, bur might serve to your benefit.: b(i) >=0, r(i) >= 0 can be vectorized, or better yet, eliminated due to being redundant to nonegative declaration. Can use >= 0 instead of == semidefinite(n+3), etc if in SDP mode, as your code is. I will leave substantive answer on complexity to others. Nov 15, 2023 at 16:16

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}$$.