1
$\begingroup$

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
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Nov 15, 2023 at 16:16

1 Answer 1

0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.