10
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$ – user35593 Sep 28 '18 at 6:02
  • $\begingroup$ @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$? $\endgroup$ – Ludwig Sep 28 '18 at 6:16
  • $\begingroup$ I missed that X is symmetric and thought that <= means all eigenvalues are smaller than. Not sure yet if my "prove" can be fixed. $\endgroup$ – user35593 Sep 28 '18 at 6:19
  • $\begingroup$ Are you sure that $\begin{bmatrix}-1 & \frac{\sqrt{3}+2}{2} \\ \frac{\sqrt{3}-2}{2} & 0 \end{bmatrix} $ is diagonalizable? $\endgroup$ – Mahdi Nov 2 '18 at 11:54
  • $\begingroup$ @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. $\endgroup$ – Ludwig Nov 2 '18 at 15:47
0
$\begingroup$

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^*$.

$\endgroup$
10
  • $\begingroup$ 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$? $\endgroup$ – Ludwig Sep 29 '18 at 15:55
  • $\begingroup$ yes. strangly you could even always take exactly this $X$. $\endgroup$ – hänsel Sep 29 '18 at 15:58
  • $\begingroup$ Then I don't think your claim is true. See the edit in my OP. $\endgroup$ – Ludwig Sep 29 '18 at 16:05
  • $\begingroup$ Indeed, then optimum is $U X U^*$ as explained in my answer. $X=1/2$ for $A$ diagonal. $\endgroup$ – hänsel Sep 29 '18 at 16:08
  • $\begingroup$ 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). $\endgroup$ – Ludwig Sep 29 '18 at 16:11
0
$\begingroup$

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.

$\endgroup$
9
  • $\begingroup$ 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. $\endgroup$ – Ludwig Sep 30 '18 at 18:12
  • $\begingroup$ Pick $A$ with strictly negative diagonal and $A+A^T$ having some positive eigenvalue, just that. $\endgroup$ – Toni Mhax Sep 30 '18 at 20:09
  • $\begingroup$ Or it is more complicated $\endgroup$ – Toni Mhax Sep 30 '18 at 20:20
  • $\begingroup$ Yes, I think it is more complicated than that. However, if you manage to find an explicit counterexample, please let me know. $\endgroup$ – Ludwig Sep 30 '18 at 20:22
  • $\begingroup$ 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. $\endgroup$ – Toni Mhax Sep 30 '18 at 20:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.