How to put following SDP probllem into an equality standard form

Question

I have the following semi-definite programming problem that I want to put in a standard form in order to estimate its order of complexity.

The problem is:

$$ \max_{x_{i,j}}\sum_{i \in \mathbf{F} }^{ }\sum_{j \in \mathbf{F} }^{ } w_{i,j}^{+}x_{i,j}+w^{-}\left(1- x_{i,j}\right ) $$ subject to the constraints $$ C1: x_{i,i}=1, \forall i\in \mathbf{F} $$

$$ C2: x_{i,j}+x_{j,k}-x_{i,k} \leq 1, \forall i,j,k \in \mathbf{F}:k>i, j \neq i,k $$

$$ C3: \sum_{j \in F}^{ }x_{i,j} \leq M, \forall i \in \mathbf{F} $$

$$ C4:x_{i,j} \geq 0, \forall i,j \in \mathbf{F} $$

$$ C5: X=\left(x_{i,j} \right )\succeq 0 $$ where, $M \in R^+$ and $X$ is a PSD $(F \times F)$ symmetric matrix. I want to put it in a standard equality form to be able to know number of equality constraints $m$ and the final matrix dimensions of $X$ which is $n$ to estimate the complexity of solving the problem using $O((mn^3+m^2n^2+m^3)\sqrt{n}\log\frac{1}{\epsilon})$

Thank you and Best Regards,

Answer 1

The standard approach to handling linear inequality constraints is add nonnegative slack variables to each of the inequality constraints to make them equality constraints and expand your $X$ matrix to a block diagonal matrix in which the nonnegative slack variables appear as 1x1 blocks on the diagonal.

In computational practice it's important to take advantage of the ability of SDP solvers to exploit this block diagonal structure rather than simply making $X$ larger. Assuming that you just want to show that the SDP can be solved in polynomial time, you should be content to just expand the size of $X$.

So, all that you need to do here is count the number of linear inequality constraints to get the number of slack variables (that will increase the size of $X$), and count the number of resulting equality constraints (to get $m$.)

C1: $F$ equality constraints, no added slack variables.

C2: $C(F,2)(F-2)$ equality constraints with $C(F,2)(F-2)$ slack variables.

C3: $F$ equality constraints, with $F$ slack variables.

C4: $F^{2}$ equality constraints, with $F^{2}$ slack variables.

C5: $X \succeq 0$ is already in standard form.

Adding this up, you end up with

$m=F+C(F,2)(F-2)+F+F^{2}$

and

$n=F+C(F,2)(F-2)+F+F^{2}$

Answer 2

An SDP in standard form is defined by data the matrices $C$ and $A_i$ and scalars $b_i$ ($i=1\ldots m$), parameterizing the primal problem $minimize~C\bullet Z$ subject to $A_i\bullet Z = b_i, Z\succeq 0$ and the dual problem $maximize~b^T$ subject to $C-\sum A_i y_i \succeq 0$. Most solvers today are primal-dual, i.e., they compute $Z$ and $y$ simultaneously. Hence, when facing a problem, it is important to understand that you have an option in how you interpret your model. I have chosen to not call any of the variables $X$ or $x$ to emphasize this freedom you have, don't let the name fool you.

In your case, trying to extract data from the description to fit the primal form (standard equality as you call it) is not necessarily the best choice if you target a standard solver. Instead, when you have many ($O(F^2)$ or more) linear inequalities, it could very well be that you should try to look at your model as something describing the dual. Indeed, $X\succeq 0$ can be seen as a linear matrix inequality $C-\sum A_i y_i$ defined using $F(F+1)/2$ variables, i.e, $y$ corresponds to the elements defining a symmetric matrix. That means your model has complexity $m=F(F+1)/2$, which Brian calls $C(F,2)$. Notably smaller than what you would have obtained trying to fit the model to a standard equality form (primal form). These variables are used in a model with one LMI constraint of size $F$, and a bunch of linear inequalities (total number given by the same analysis as Brian counts when he sums up the number of slacks required, plus the fact that your $F$ equalities have to be written using $2F$ linear constraints).