[Math] Minimize Trace for non-symmetric matrix

convex optimization

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?

Best Answer

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.

Related Solutions

Matrices – How to Find Closest Positive Definite Matrix of Non-Symmetric Matrix

A real, square matrix $B$ is positive definite iff $v^TBv> 0$ for all $v\neq 0$. But $$v^TBv = \tfrac{1}{2}(v^TBv+v^TB^Tv) = \tfrac{1}{2}v^T(B+B^T)v.$$ It follows then that $B$ is positive definite iff $B+B^T$ is positive definite. Therefore, your model becomes $$\begin{array}{ll} \text{minimize} & \|A-B\|_F \\ \text{subject to} & B+B^T \succ 0 \end{array}$$ This remains a convex optimization problem. For example, in CVX the model is

n = size(A,1);
cvx_begin sdp
    variable B(n,n)
    minimize(norm(A-B,'Fro'))
    subject to
        B+B' >= 0
cvx_end

(Disclaimer: I am the author of CVX. You do not need to use it to solve this problem, however. Any SDP solver can handle this problem.)

Note that the CVX model relaxes the condition to require $B$ to be positive semidefinite. That will be necessary with any numerical solver you are likely to employ here. Of course, an interior-point method would get you a sequence of strictly positive definite solutions that converge to an optimum, but this optimum may itself be positive semidefinite.

[Math] Minimize trace($MX$) with $M$ rank-deficient and $X$ positive semidefinite

You removed the rank-one constraint. The optimization will no longer find a rank-one matrix. However, for your problem, you may not need a solver. Let $M$ be a $n\times n$ matrix. Observe that $X\geq 0$ and $rank(X)=1$ implies that $X=xx^T$ for some vector $x\in\mathbb{R}^n$. Then $trace\{MX\}=x^TMx $. Also, $diag(X)=Id$ will imply $x_i^2=1$ where $x=[x_1,\dots,x_n]$. Thus, your optimization problem becomes $$\min_{x\in\mathbb{R}^n}~x^TMx \\s.t.~x_i\in\{-1,1\} \forall i .$$ Let $M$ be symmetric (try convincing yourself that this doesn't lose generality). Then $M$ has a decomposition of form $$M =\sum_{i=1}^{n}\lambda_iv_iv_i^T$$ where $\lambda_1<\dots<\lambda_n$ are eigenvalues and $v_i$ are corresponding eigenvectors. Thus, we have $$x^TMx=\sum_{i=1}^{n}\lambda_i(x^Tv_i)^2$$ Also, note that $\sum_{i}x_i<=n$. Given this, can you try and show that $x = sign(v_1)$. Here $sign(.)$ is +1 or -1 corresponding to positive and negative entries of the argument vector.

Best Answer

Related Solutions

Matrices – How to Find Closest Positive Definite Matrix of Non-Symmetric Matrix

[Math] Minimize trace($MX$) with $M$ rank-deficient and $X$ positive semidefinite

Related Question