Solving a strange optimization problem

Question

introduction

Let $M\in\mathbb{R}^{3\times 3}$ be a covariance matrix (i.e. a symmetric and positive definite matrix) and let's call absolute sum (question: does already exists this operator? if yes, what is his name?) the following operator \begin{equation*} \text{asum}(M)\triangleq \sum_{i,j=1}^3 |M_{i,j}| \end{equation*}

Now, let's suppose that the diagonal matrix of the matrix $M$ is given, while the non-diagonal elements are degrees of freedom.

I'm interest into finding, if it exists, the matrix $M$ that maximise the absolute sum above. As already mentioned, the the following two constraint must be satisfied:

1. $M$ is a covariance matrix;
2. the diagonal elements $M_{1,1}$, $M_{2,2}$, $M_{3,3}$ are already fixed.

problem formulation

The problem can be expressed as follows \begin{equation*}\begin{aligned} \max_{M_{1,2}, M_{1,3}, M_{2,3} \in \mathbb{R}} \quad &|M_{1,2}|+ |M_{1,3}|+ |M_{2,3}|\\ \textrm{s.t.} \quad & \text{det}(M)\succ0 \end{aligned} \end{equation*} where $\text{det}(\cdot)$ is the determinant operator. Writing explicitly (e.g. by employing Sylvester) the constraint $\text{det}(M)\succ0$ gives 3 non-linear equations in the three unknowns $M_{1,2}$, $M_{1,3}$, $M_{2,3}$ and the three parameters $M_{1,1}$, $M_{2,2}$, $M_{3,3}$.

To be honest, I don't even know if the problem is convex (and thus solvable via the KKTs) or has finite solution. The only thing that I'm able to say about this problem is that the feasable set is not empty (because, clearly, otherwise there will not exist any covariance matrix).

Maybe a better approach should be to study the simpler $2\times 2$ case, and extend the solution to the current $3\times3$ case.

question

Is there a chance to find an analytic solution of my problem? I'd like to dont waste time in this problem if the only way to solve it is by employing numerical optimizers.

Answer 1

You do not need to consider the determinant here and can use semidefinite programming right away. This is a convex problem which is formulated as

$$\max_{M\in\mathbb{S}^3}\ \mathrm{asum}(M)\ \mathrm{s.t.}\ M\succ0$$

where $\mathbb{S}^3$ is the cone of symmetric matrices of dimension 3 and $M\succ0$ means that $M$ is positive definite.

The issue is that there is no maximum only a supremum in that case. Also, one can see that $m_{12}$, $m_{13}$ and $m_{23}$ can be chosen as positive values. So, we can drop the absolute value sign.

Let $m_{12}=\sqrt{m_{11}m_{22}}-\epsilon$, $m_{13}=\sqrt{m_{11}m_{33}}-\epsilon$, and $m_{23}=\sqrt{m_{22}m_{33}}-\epsilon$. Then, we have that

$$M=\begin{bmatrix} m_{11} & \sqrt{m_{11}m_{22}} & \sqrt{m_{22}m_{33}}\\ \sqrt{m_{11}m_{22}} & m_{22} & \sqrt{m_{22}m_{33}}\\ \sqrt{m_{11}m_{33}} & \sqrt{m_{22}m_{33}} & m_{33} \end{bmatrix}-\epsilon \begin{bmatrix} 0 & 1 & 1\\ 1 & 0 & 1\\ 1 & 1 & 0\\ \end{bmatrix}.$$

The first matrix is equal to

$$ \begin{bmatrix} m_{11} & \sqrt{m_{11}m_{22}} & \sqrt{m_{22}m_{33}}\\ \sqrt{m_{11}m_{22}} & m_{22} & \sqrt{m_{22}m_{33}}\\ \sqrt{m_{11}m_{33}} & \sqrt{m_{22}m_{33}} & m_{33} \end{bmatrix}=\begin{bmatrix}\sqrt{m_{11}}\\\sqrt{m_{22}}\\\sqrt{m_{33}}\end{bmatrix}\begin{bmatrix}\sqrt{m_{11}}\\\sqrt{m_{22}}\\\sqrt{m_{33}}\end{bmatrix}^T $$

which is of rank one and the positive eigenvalue is $m_{11}+m_{22}+m_{33}$. This also means that when $\epsilon=0$, we are on the boundary of the feasible set. We can also show that when $\epsilon>0$ and small, $M$ is positive definite.

So, the supremum is given by $\sqrt{m_{11}m_{22}}+\sqrt{m_{22}m_{33}}+\sqrt{m_{11}m_{33}}$.