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