# A (linear) optimization problem subject to (linear) matrix inequality constraints

Let $$A \in \mathbb{R}^{n \times n}$$ be a Hurwitz matrix, i.e. $$A$$ satisfies $$\mathrm{Re}\,\lambda_i< 0$$, where $$\{\lambda_i\}_{i=1}^n$$ is the set of eigenvalues of $$A$$. Suppose that the trace of $$A$$ is normalized to $$-1$$, that is $$\mbox{trace}(A)=-1$$. Further, let $$\ge$$ denote the standard partial order in the set of positive semidefinite matrices.

Conjecture. $$\min_{\substack{X\in\mathbb{R}^{n\times n},\ X\ge 0\\ AX+XA^\top \le 0 \\ X-\frac{1}{2} I\le 0}} \mathrm{trace}(AX)=-\frac{1}{2}.$$

I numerically verified the above conjecture for $$n=2, 3,\dots,10$$ in Matlab using the built-in LMI optimization solver. Any hint/comment towards the (dis)proof of this conjecture is very appreciated.

The optimal $$X$$ is not full rank, in general. Consider the following $$2\times 2$$ matrix $$A = \begin{bmatrix}-1 & \frac{\sqrt{3}+2}{2} \\ \frac{\sqrt{3}-2}{2} & 0 \end{bmatrix}.$$ Matrix $$A$$ has two eigenvalues at $$-0.5$$.

Let us select $$X = \begin{bmatrix}\frac{1}{2} & 0 \\ 0 & -\frac{\sqrt{3}-2}{2(\sqrt{3}+2)} \end{bmatrix}.$$ It is easy to see that both constraints are satisfied and $$\mathrm{tr}(AX)=-\frac{1}{2}$$.

Observe also that, since $$A+A^\top$$ possesses a positive eigenvalue, $$X=\frac{1}{2}I$$ violates the constraint $$AX+XA^\top\le 0$$ and it is not an admissible solution.

• You dont need the first constraint. Write $A=SDS^{-1}$ with $D$ diagonal and define $Y=S^{-1}XS$. Then $trace(AX)=trace(SDYS^{-1})=trace(DY)$ and $Y<=1/2I$ from which $trace(DY)\geq -1/2 trace(D)=-1/2$ follows. – user35593 Sep 28 '18 at 6:02
• @user35593: I think I'm missing something. Since $S$ is in general not orthogonal, $Y$ is typically non-symmetric. Hence, what does $Y\le \frac{1}{2} I$ mean for a non-symmetric matrix $Y$? – Ludwig Sep 28 '18 at 6:16
• I missed that X is symmetric and thought that <= means all eigenvalues are smaller than. Not sure yet if my "prove" can be fixed. – user35593 Sep 28 '18 at 6:19
• Are you sure that $\begin{bmatrix}-1 & \frac{\sqrt{3}+2}{2} \\ \frac{\sqrt{3}-2}{2} & 0 \end{bmatrix}$ is diagonalizable? – Mahdi Nov 2 '18 at 11:54
• @Mahdi: Yes, you are right: the matrix is not diagonalizable. Thanks for spotting this! However, my conjecture seems to be true (numerically) for every Hurwitz stable matrix (i.e. diagonalizability is not required). I edited the OP accordingly. – Ludwig Nov 2 '18 at 15:47

Obviously, $$trace(AX)=-1/2$$ for $$X=(1/2) I$$. Assume $$A$$ diagonal. Note $$A + A^T \le 0$$, so $$AX+X A^T \le 0$$. If $$A$$ diagonal, then this $$X$$ is obviously optimizes the minimum, as $$X\le (1/2) I$$ is your constraint.

If $$A'$$ is not is diagonal, write $$A'=U A U^*$$, $$trace(UAU^* UXU^*)=trace(AX)$$. And $$UXU^*\le U(1/2)IU^*=(1/2)I$$. And $$UAXU^* + UXA^*U^* \le 0 \Leftrightarrow AX +X A^* \le 0$$, so constraints are invariant under transformation $$U$$. Take optimum $$U X U^*$$.

• Thanks for your answer. However, I think I'm missing something. Are you claiming that the optimal $X$ is always of the form $X=\frac{1}{2}I$? – Ludwig Sep 29 '18 at 15:55
• yes. strangly you could even always take exactly this $X$. – hänsel Sep 29 '18 at 15:58
• Then I don't think your claim is true. See the edit in my OP. – Ludwig Sep 29 '18 at 16:05
• Indeed, then optimum is $U X U^*$ as explained in my answer. $X=1/2$ for $A$ diagonal. – hänsel Sep 29 '18 at 16:08
• Ok, so your claim is that the solution is invariant under unitary similarity transformations. I agree. Further, I would say that the optimum is $X=\frac{1}{2}I$ in the case $A+A^\top\le 0$ (not just $A$ diagonal). Otherwise, the explicit form of the optimum $X$ seems tricky (cf. the explicit example in my edited OP). – Ludwig Sep 29 '18 at 16:11

Up to a unitary matrix $$U$$, $$X$$ is diagonal with all eigenvalues between $$0$$ and $$1/2$$ the other constraint on $$AX$$ implies that the diagonal entries of $$U^*AUU^*XU$$ are $$\le 0$$ and so are those of $$U^*AU$$. Take $$\text{tr}(AX)$$ summing the diagonal terms we see that as convex combination the minimum could be atteigned as $$\frac{1}{2}\text{tr}(A)$$.

The $$X$$ is the diagonal with entries equal $$1/2$$ except the terms $$x_{i,i}$$ where $$x_{i,i}=0$$ if $$a'_{i,i}=0$$ (entry of $$U^*AU$$) is possible but in general there (is) should be a counter example to your conjecture.

• Thanks for your comment. I see your point, however I couldn't find any numerical counterexample yet (I've run an extensive number of random numerical simulation for $n=2,3,\dots,10$). If you have some ideas about how to construct such a counterexample, please let me know. – Ludwig Sep 30 '18 at 18:12
• Pick $A$ with strictly negative diagonal and $A+A^T$ having some positive eigenvalue, just that. – Toni Mhax Sep 30 '18 at 20:09
• Or it is more complicated – Toni Mhax Sep 30 '18 at 20:20
• Yes, I think it is more complicated than that. However, if you manage to find an explicit counterexample, please let me know. – Ludwig Sep 30 '18 at 20:22
• Try to find $A+A^T$ a $2\times 2$ matrix having one positive eignevalue at least and such that $U^*AU$ has strictly negative diagonal for all unitary $U$, the counter example is equivalent to that. – Toni Mhax Sep 30 '18 at 20:40