1
$\begingroup$

Given $ A \in \mathcal{S}_{+}^{n \times n} $ (PSD Matrix) with $ \lambda_{max} \left( A \right) < 1 $ solve the following optimization problem:

$$ \arg \min_{X \in \mathcal{S}_{+}^{n \times n}} \operatorname{Tr} \left( A X \right), \; \text{subject to} \; \operatorname{Tr} \left( X \right) \geq a $$

Where $ a \geq 0 $ is a given parameter.

$\endgroup$
6
  • 2
    $\begingroup$ The trace of the product of two positive semidefinite matrices is always nonnegative. When $X$ is close to zero, the trace of $AX$ is also close to zero. Therefore the infimum is zero. $\endgroup$
    – user1551
    Mar 15, 2020 at 11:36
  • $\begingroup$ @user1551 :X must be positive definite matrix $\endgroup$
    – hichem hb
    Mar 15, 2020 at 12:43
  • 1
    $\begingroup$ @hichemhb That doesn't change anything; the argument still applies and the infimum is zero. If we instead had a constraint of $\operatorname{Tr}(X) = a$, we would have a non-zero infimum. $\endgroup$ Mar 15, 2020 at 14:22
  • $\begingroup$ @user1551 i saw your answer in (math.stackexchange.com/questions/239352/… ) however I did not understand the utility of the two theorems annones and the finding on the matrix Q. i think that we can use the same idea ? $\endgroup$
    – hichem hb
    Mar 15, 2020 at 17:40
  • $\begingroup$ In your new edit, does "PSD" mean "positive semidefinite"? Can $A$ and $X$ be singular? $\endgroup$
    – user1551
    Mar 15, 2020 at 18:14

1 Answer 1

1
$\begingroup$

We may assume that $A=\operatorname{diag}(\mathbf a)$, where the entries of $\mathbf a=(a_1,a_2,\ldots,a_n)$ are arranged in descending order. Let the diagonal of $X$ be $\mathbf x$. Since $\operatorname{tr}(AX)=\langle\mathbf a,\mathbf x\rangle$ and $\operatorname{diag}(\mathbf x)$ is positive definite when $\mathbf x>0$ entrywise, we may further assume that $X=\operatorname{diag}(\mathbf x)$. Therefore, if we denote $$ S=\left\{\mathbf x:\ \mathbf x>0,\ \langle\mathbf x,\mathbf 1\rangle\ge a\right\} $$ where $\mathbf 1=(1,1,\ldots,1)$, the problem reduces to finding $\inf_{\mathbf x\in S} \langle\mathbf x,\mathbf a\rangle$.

Let $\mathbf x_0=(0,\ldots,0,a)$. It isn't hard to see that

  • $\mathbf x_0$ is an accumulation point of $S$ and $\langle\mathbf x_0,\mathbf a\rangle=aa_n$,
  • $\langle\mathbf x,\mathbf a\rangle\ge\langle\mathbf x_0,\mathbf a\rangle$ for every $\mathbf x\in S$
  • $\langle\mathbf x,\mathbf a\rangle>\langle\mathbf x_0,\mathbf a\rangle$ for every $\mathbf x\in S$ if $a_1>a_n$ or $a_n>0=a$.

It follows that $\inf_{\mathbf x\in S} \langle\mathbf x,\mathbf a\rangle=aa_n$ and this infimum value is unattainable unless $a_1=a_n$ and (i) $a_n=0$ or (ii) $a>0$, i.e. unless (i) $A=0$ or (ii) $A$ is a positive multiple of the identity matrix and $a>0$.

$\endgroup$

You must log in to answer this question.

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