5
$\begingroup$

Given a positive definite matrix $A \in \mathbb{R}^{n \times n}$, I would like to compute $$\max_{x \in \Delta_n} \lambda_{\rm min} \left( {\rm diag}(x) A \right)$$ where

  • $\Delta_n$ is the simplex, i.e., $\Delta_n = \{x \in \mathbb{R}^n ~|~ x_i \geq 0, \sum_i x_i = 1\}$
  • ${\rm diag}(x)$ is the standard operation which transforms the vector $x \in \mathbb{R}^n$ into a diagonal matrix by putting the elements of $x$ on the diagonal.
  • $\lambda_{\rm min}(W)$ returns the smallest eigenvalue of the matrix $W$.
  • In this case, since ${\rm diag}(x)A$ is conjugate to ${\rm diag(x)}^{1/2} A {\rm diag(x)}^{1/2}$ and $A$ is positive definite, we have that ${\rm diag}(x)A$ has real eigenvalues, and it makes sense to talk about the smallest eigenvalue.

I have a vague suspicion there might be an explicit formula for the solution of this problem, though I'm not sure. If that was the case, that would be great. If not, is there a polynomial-time algorithm which computes the optimal solution? Can this maybe be reduced to a semi-definite program?

Something to go on is that $\lambda_{\rm min}(W)$ is a concave function of the symmetric matrix $W$. On the other hand, I haven't been able to translate this into concavity or convexity of $\lambda_{\rm min}({\rm diag}(x)A)$ as a function of $x$; the issue is that ${\rm diag}(x)A$ is not symmetric, so I'm not sure how useful this is.

$\endgroup$
  • $\begingroup$ I think you may want to think about your domain as being the set $\{ \operatorname{diag}(x)^{1/2} A \operatorname{diag}(x)^{1/2} : x \in \Delta_n \}$. Try to understand the geometry of this set... $\endgroup$ – Ian Dec 28 '16 at 23:56
2
$\begingroup$

It's been a while since the question was asked, but hopefully this is still helpful.

Let's assume that $A$ is symmetric. Then, letting $X=diag(x)$, this problem can be formulated as a semidefinite program in $X$, since $$ \lambda \leq \lambda_{\min}(X A) \implies \lambda: X A \succeq \lambda I,$$ and $XA$ is symmetric so the eigenvalues are well-defined (if $A$ is not symmetric then we can replace $XA$ with $\frac{1}{2}XA+\frac{1}{2}XA^\top$).

We can write the SDP as: \begin{align*} \max \quad & \lambda\\ \text{s.t.} \quad & X A \succeq \lambda I,\\ & tr(X)=1,\\ & X_{i,j}=0, \forall i \neq j,\\ & X_{i,i} \geq 0, \forall i. \end{align*}

$\endgroup$

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.