1
$\begingroup$

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?

$\endgroup$

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Thank you for your answer. Is there a step-by-step explanation of the algorithm? I am looking for some explanation of the answer here by Royi. $\endgroup$
    – Tan
    Commented Oct 30, 2021 at 19:07
  • $\begingroup$ This must be solved by a numerical linear SDP solver, whose algorithms are rather complicated. You need not know the details of the algorithm to use the solver, and if you use a modeling tool such as CVX or YALMIP, among others, you need not understand the complexities of solver standard form. If you just want to solve the problem, for instance in the thread you linked, I suggest you use the approach in my answer there, not Royi's. $\endgroup$ Commented Oct 30, 2021 at 19:29
  • $\begingroup$ Actually, I may have found an easier solution here. Please let me know if you disagree with the linked method. Thank you! $\endgroup$
    – Tan
    Commented Nov 4, 2021 at 5:22

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .