0
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ If the optimal solution is non-unique, there's no way to be sure that you'll get the same optimal solution for both versions of the problem, although both solutions should still be optimal and have the same optimal objective value. $\endgroup$ May 2 '19 at 23:54
  • $\begingroup$ How do you say same eigenvalues implies the constraints are equivalent? Would you mind please remind this a bit? $\endgroup$ May 2 '19 at 23:56
  • $\begingroup$ @ Brian Borchers Agreed. Notice, I wrote optimal solutions (argmin), i.e., plural, and optimal objective value (singular). Perhaps a little too subtlely, I was allowing for the possibility of non-unique solutions, and that the collection of solutions is the same for both problems. $\endgroup$ May 2 '19 at 23:58
  • 2
    $\begingroup$ $X \succeq 0$ means that $X$ is symmetric, and has all eigenvalues nonnegative. Because $X$ has the same eigenvalues as $EXE$, and $EXE$ is symmetric, that is the same as requiring all eigenvalues of $EXE$ to be nonnegative, which is what the constraint $EXE \succeq 0$ does. $\endgroup$ May 3 '19 at 0: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.