2
$\begingroup$

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,

$\endgroup$
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Actually, you can exploit the symmetry of $X$ to reduce the number of $X_{i,j} \geq 0$ constraints to $C(F,2)$. You could then replace the $F^{2}$ terms in the formulas for $m$ and $n$ with $C(F,2)$. $\endgroup$ – Brian Borchers Jun 2 '13 at 16:57
  • $\begingroup$ Dear Sir, thank you so much for your response, it was really helpful to me. Actually i was using SeDuMi in the CVX package to solve the above problem. However, what has caused me a confusion is that, SeDuMi reports in its solution the number of variables and the number of equality constraints it has found during solving the problem. Those numbers however, are far below the anticipated numbers when i calculated them using the same approach as you sir discussed. So, any ideas sir what might be the difference due to ?? $\endgroup$ – Amr Jun 4 '13 at 2:42
  • $\begingroup$ Did you use CVX to formulate your problem? CVX may well have simplified the problem in ways that reduced the number of constraints or variables. It would also certainly have used block diagonal structure as described above to reduce the number of variables. $\endgroup$ – Brian Borchers Jun 4 '13 at 4:56
2
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ So, sir i don't get it. Do you mean that if i put the problem in its dual form , this will lead to lower complexity in terms of number of variables and equality constraints ?? $\endgroup$ – Amr Jun 5 '13 at 7:09
  • $\begingroup$ If you interpret the model as something describing the dual problem, you will have a much smaller model. Example 3.2 in users.isy.liu.se/en/rt/johanl/2009_OMS_DUALIZE.pdf might be illustrative (a model which is much better interpreted in primal space than dual space, i.e., the reverse from yours) $\endgroup$ – Johan Löfberg Jun 5 '13 at 11:32
  • $\begingroup$ Ah, i got your point sir. So, one more thing, can you recommend me some document showing how to transform between primal and dual SDPs and vice versa? $\endgroup$ – Amr Jun 5 '13 at 23:16
  • $\begingroup$ The linked paper. You really don't transform any model, you re-interpret the underlying model you have on paper to extract the data $C$, $A$, and $b$. $\endgroup$ – Johan Löfberg Jun 6 '13 at 8:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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