Rows and columns permutation of SDP variable $X\in\mathbf{S}^n$

67 Views Asked by At

We know the standard form of SDP is

\begin{equation}\label{eq:ex_m} \begin{aligned} & {\underset{X}{\min}} & & \mbox{tr}(CX)\\ & \text{s.t.} & & \mbox{tr}(A_iX)=b_i, \ \ i=1,\cdots,p \\ & & & X\succeq0 \end{aligned} \end{equation}

Now, if I consider the following

\begin{equation} \begin{aligned} & {\underset{X}{\min}} & & \mbox{tr}(CX)\\ & \text{s.t.} & & \mbox{tr}(A_iX)=b_i, \ \ i=1,\cdots,p \\ & & & EXE\succeq0, \end{aligned} \end{equation}

where $E$ is a permutation matrix which permutes row and column. For example, permute row $i$ and row $j$, column $i$ and column $j$ with $i < j$. So $E$ is a orthogonal matrix. Note that, in this case, $E = E^{-1} = E^T$

I roughly ran a few examples, it seems that we can get the same cost. Not quite sure.

Q: Will we get the same cost and solution from both SDPs?

1

There are 1 best solutions below

4
On BEST ANSWER

The optimal solutions (argmin) and optimal objective value are the same for both problems, presuming optimization is performed exactly.

That is because $EXE = E^{-1}XE$, which is similar to $X$. Therefore their eigenvalues are identical (see https://en.wikipedia.org/wiki/Matrix_similarity#Properties), so the constraints $X \succeq 0$ and $EXE \succeq 0$ are equivalent, in exact arithmetic.

If numerically solved in finite precision to finite optimality tolerance, it is possible for the solutions returned by a numerical optimizer to differ.