12
$\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.

Improve this question
$\endgroup$
6
  • 1
    $\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
    Commented Sep 28, 2018 at 6:02
  • 1
    $\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
    Commented Sep 28, 2018 at 6:16
  • 1
    $\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
    Commented Sep 28, 2018 at 6:19
  • 1
    $\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 - Free Palestine
    Commented Nov 2, 2018 at 11:54
  • 1
    $\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
    Commented Nov 2, 2018 at 15:47

2 Answers 2

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

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

Improve this answer
$\endgroup$
9
  • 1
    $\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
    Commented Sep 30, 2018 at 18:12
  • 1
    $\begingroup$ Pick $A$ with strictly negative diagonal and $A+A^T$ having some positive eigenvalue, just that. $\endgroup$
    – Toni Mhax
    Commented Sep 30, 2018 at 20:09
  • 1
    $\begingroup$ Or it is more complicated $\endgroup$
    – Toni Mhax
    Commented Sep 30, 2018 at 20:20
  • 1
    $\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
    Commented Sep 30, 2018 at 20:22
  • 1
    $\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
    Commented Sep 30, 2018 at 20:40

You must log in to answer this question.

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