Friday, May 22, 2015

Nonsymmetric semidefinite optimization problems.

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.

4 comments:

  1. No offense, but your blog post is hard to read. If I understand it correctly, you mean:
    ---------------------
    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?

    ReplyDelete
  2. 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?

    ReplyDelete
    Replies
    1. Hi Ipopt User. I think the missing piece of the transformation is the relation
      (C,X) = ((C+C')/2, X) for symmetric X,
      using parenthesis for the trace inner product.

      Delete
    2. Well, I guess this and the fact that when you substitute
      X (nonsymmetric psd) = Y (symmetric psd) + Z (skew-symmetric psd),

      you can also reformulate Z in terms of Z' (symmetric psd), by updating all coefficients:
      (C,Z) = (C',Z')
      where C' defined as C with strictly lower triangular elements negated and diagonal elements set to zero. With all variable domains correct, now update coefficients as stated in my previous post.

      Delete