11
$\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, 2018 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, 2018 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, 2018 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, 2018 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, 2018 at 15:47

2 Answers 2

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, 2018 at 15:55
  • $\begingroup$ yes. strangly you could even always take exactly this $X$. $\endgroup$
    – hänsel
    Sep 29, 2018 at 15:58
  • $\begingroup$ Then I don't think your claim is true. See the edit in my OP. $\endgroup$
    – Ludwig
    Sep 29, 2018 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, 2018 at 16:08
  • 1
    $\begingroup$ This answer assumes that $A$ is symmetric. But this is not assumed in the original question. For $A$ symmetric the answer is correct, but this is not the interesting case. $\endgroup$ Jan 4, 2019 at 15:12
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, 2018 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, 2018 at 20:09
  • $\begingroup$ Or it is more complicated $\endgroup$
    – Toni Mhax
    Sep 30, 2018 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, 2018 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, 2018 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.