Positive semidefinite with zero constraints optimization

Question

Suppose $S\in\mathbb{R}^{n\times n}$ is a symmetric positive semidefinite matrix. I wonder how to solve the following optimization problem

\begin{equation*} \begin{aligned} & \underset{\Omega=\Omega^T}{\text{minimize}} & & \mbox{tr} \left( S \Omega^2 \right) \\ & \text{subject to} & & \Omega_{ii}=1, \quad i=1,\dots,n \\ && & \Omega_{ij}=0, \quad (i,j) \in \mathcal{O} \\ &&& \Omega \succeq 0. \end{aligned} \end{equation*}

Here, $\mathcal{O}$ is a set of indexes so that $\Omega_{ij}=0, \forall (i,j)\in\mathcal{O}$.

---

I think this is a convex optimization problem because the function $\mbox{tr} \left( S \Omega^2 \right)$ is a convex function of $\Omega$ and the constraint set is also convex. This is because

$$\mbox{tr} \left( S \Omega^2 \right) = \sum_{i=1}^n \omega_{i.} S \omega_{.i}$$

which is a sum of convex quadratic form, and for any $\Omega_1$ and $\Omega_2$ satisfying the constraints,

$$\forall \lambda \in (0,1), \lambda \Omega_1 + (1 - \lambda) \Omega_2$$

also satisfies the constraints. Is there a (fast) way to solve this optimization problem?

I understand that if we remove the zero, we can use MATLAB CVX, etc. But what if there is zero constraints?

Answer 1

This can be modeled in CVX as a convex optimization problem.

The constraints, $ \Omega_{ij}=0, \text{ }(i,j) \in \mathcal{O} $, are linear constraints which can be directly entered in CVX.

The key to handling trace(S*Omega^2) in CVX is to reformulate it as square_pos(norm(Omega*sqrtm(S),'fro')). Actually it is numerically better not to square the norm in the objective, and instead use norm(Omega*sqrtm(S),'fro'), and then square the optimal objective value after the optimization is completed, if you really need trace(S*Omega^2).

The reformulation is based on

trace(S*Omega^2) = trace(sqrtm(S)*sqrtm(S)*Omega*Omega) =

trace (sqrtm(S)*Omega*Omega*sqrtm(S)) =

norm(Omega*sqrtm(S),'fro')^2,

where I made us of the cyclic permutation invariance of trace., as well as Omega and sqrtm(S) being symmetric.

The CVX program would be:

cvx_begin
variable Omega semidefinite
minimize(norm(Omega*sqrtm(S),'fro'))
<Incorporate constraints on certain elements of Omega being 0>
cvx_end

The writing of the constraints on certain elements of Omega being 0 is just a matter of indexing to the desired elements to be constrained to 0.