1
$\begingroup$

Let $A$ be a given matrix and $X$ a symmetric positive definite matrix which shall be optimized:

min $tr (AX)$ subject to $X>0$

This optimization problem is convex if $A$ is symmetric as it is the standard form of Semidefinite Programming. But is the problem convex for non-symmetric $A$ as well?

$\endgroup$
1
$\begingroup$

Yes, the program is convex for any $A$.

Let $X \in S^n$ (the space of $n\times n$ dimensional symmetric matrices). Then,

\begin{align*} \textrm{trace}(AX) &= \textrm{trace}\left(A\left(\sum_{i=1}^n\nu_i x_i x_i^T\right)\right)\\ &= \textrm{trace}\left(\sum_{i=1}^n\nu_i A x_i x_i^T\right)\\ &= \sum_{i=1}^n\nu_i \textrm{trace}\left( A x_i x_i^T\right)\\ &= \sum_{i=1}^n\nu_i \textrm{trace}\left(x_i^T A x_i \right)\\ &= \sum_{i=1}^n\nu_i \left(x_i^T A x_i \right)\\ \end{align*} We will use the following identity: For any square matrix $A$ $$ x^TAx = \frac{1}{2}x^T(A+ A^T)x$$ Proof: \begin{align*} \frac{1}{2}x^T(A+ A^T)x &= \frac{1}{2}x^TAx + \frac{1}{2}x^TA^Tx\\ &= \frac{1}{2}x^T(Ax) + \frac{1}{2}(Ax)^Tx\\ &= \frac{1}{2}x^T(Ax) + \frac{1}{2}x^T(Ax)\\ &= x^TAx \end{align*} Thus, we get \begin{align*} \textrm{trace}(AX) &= \sum_{i=1}^n\nu_i \left(x_i^T \frac{1}{2}(A+ A^T)x_i \right)\\ &= \frac{1}{2}\textrm{trace}\left(\sum_{i=1}^n\nu_i x_i^T(A+ A^T)x_i \right)\\ & = \frac{1}{2}\textrm{trace}\left((A+ A^T)\sum_{i=1}^n\nu_i x_ix_i^T \right)\\ & = \frac{1}{2}\textrm{trace}\left((A+ A^T)X\right) \end{align*} The term $\textrm{trace}\left((A+ A^T)X\right)$ is in standard form as desired.

$\endgroup$

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.