In semidefinite optimization we optimize over a matrix variable that must be symmetric and positive semidefinite.
Assume we want to relax the assumption about symmetry. Is that an important generalization? The answer is no for the following reason. Since
(X+X')/2 is PSD
implies
X
is PSD. Observe
X = (X+X')/2+(X-X')/2
and
y'( (X-X')/2) y >= 0.
implying X is PSD.
Note (X-X')'=-(X-X') implying X-X' is skew symmetric.
Hence, any nonsymmetric semidefinite optimization problem can easily be posed as a standard symmetric semidefinite optimization problem.
No offense, but your blog post is hard to read. If I understand it correctly, you mean:
ReplyDelete---------------------
In semidefinite optimization we optimize over a matrix variable that must be symmetric and positive semidefinite. Assume we want to relax the assumption about symmetry. Is that an important generalization? The answer is no. The following lemma shows that any nonsymmetric semidefinite optimization problem in X can easily be posed as a standard symmetric semidefinite optimization problem in Y.
Lemma: X is PSD if and only if Y = (X+X')/2 is PSD.
Proof (=>): immediate
Proof (<=): Observe X = Y+(X-X')/2 and z'( (X-X')/2) z = 0, implying X is PSD.
Note: (X-X')'=-(X-X') implying X-X' is skew symmetric.
---------------------
I do not understand how requiring symmetry does not alter the problem. Suppose we have X in S^{2x2}_+, the objective is to minimize under some constraints = b_i. How can this particular problem be rephased when C is asymmetric?
The last sentence is shown incorrectly due to the use of inner product brackets. The correct sentence, now using parenthesis for the trace inner product, is: Suppose we have X in S^{2x2}_+, the objective is to minimize (C,X) under some constraints (A_i,X) = b_i. How can this particular problem be rephased when C is asymmetric?
ReplyDeleteHi Ipopt User. I think the missing piece of the transformation is the relation
Delete(C,X) = ((C+C')/2, X) for symmetric X,
using parenthesis for the trace inner product.