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$

1 Answer 1

Reset to default
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$
    – Brian Borchers
    May 2, 2019 at 23:54
  • $\begingroup$ How do you say same eigenvalues implies the constraints are equivalent? Would you mind please remind this a bit? $\endgroup$
    – sleeve chen
    May 2, 2019 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$
    – Mark L. Stone
    May 2, 2019 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$
    – Mark L. Stone
    May 3, 2019 at 0:02

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .