# An eigenvalue optimization problem

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.

• 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... – Ian Dec 28 '16 at 23:56

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*}