# Maximizing a function of the maximal and minimal eigenvalues

In my work, I encountered the following optimization problem.

Given symmetric, positive definite matrices $$K_1, K_2, \dots, K_n$$, find symmetric, positive definite matrix $$R$$ that minimizes

$$\max \{ |1-\alpha_{\max}|, |1-\alpha_{\min}| \}$$

where $$\alpha_{\min}$$ and $$\alpha_{\max}$$ are the minimal and maximal eigenvalues of $$K_1 R, K_2 R, \dots, K_n R$$.

Are there any explicit solutions for this problem? If not, are there any numerical algorithms?

Edit 1: Now, I am looking for a numerical solution based on the gradient descent technique. The eigenvalues of $$K_1 R, K_2 R, \dots, K_n R$$ are the same as the symmetric tensors $$S_1=\sqrt{R}K_1 \sqrt{R}, S_2=\sqrt{R}K_2 \sqrt{R}, \dots, S_n=\sqrt{R}K_n \sqrt{R}$$. The derivatives of eigen value $$\alpha$$ with respect to the original Hermitian matrix $$S_i$$ is available in the link Derivatives of eigenvalues.

Shortly we have $$\partial \alpha/\partial S_i=v\otimes v$$ where $$v$$ is the asociated eigen vector. The remaining work is to find $$\partial S_i/\partial R$$. Are there explicit expressions for $$\partial S_i/\partial R$$ or $$\partial \sqrt{R}/\partial R$$?

• Hmm. This seems a very challenging problem, as the eigenvalues of $K_iR$ have no simple relationship to those of $K_i$ or $R$... even the case where $R$ is diagonal seems very tough. Commented Jun 22, 2018 at 8:18
• This looks like a research-level question. Why not move it to MathOverflow? Commented Jul 7, 2018 at 12:35

Let us consider the simplest case, i.e., the case where $$n=1$$. Rephrasing slightly:

Given symmetric and positive definite $$\rm A$$, find symmetric and positive definite $$\rm X$$ that minimizes

$$\max \big\{ | 1 - \lambda_{\max} (\mathrm A \mathrm X) |, | 1 - \lambda_{\min} (\mathrm A \mathrm X) | \big\}$$

Note that

\begin{aligned} \max \big\{ | 1 - \lambda_{\max} (\mathrm A \mathrm X) |, | 1 - \lambda_{\min} (\mathrm A \mathrm X) | \big\} &= \max \big\{ | \lambda_{\min} (\mathrm I - \mathrm A \mathrm X) |, | \lambda_{\max} (\mathrm I - \mathrm A \mathrm X) | \big\}\\ &= \max \big\{ \big| \lambda_{\min} \big( \mathrm I - \mathrm A^{\frac 12} \mathrm X \mathrm A^{\frac 12} \big) \big|, \big| \lambda_{\max} \big( \mathrm I - \mathrm A^{\frac 12} \mathrm X \mathrm A^{\frac 12} \big) \big| \big\}\\ &= \rho \left( \mathrm I - \mathrm A^{\frac 12} \mathrm X \mathrm A^{\frac 12} \right) = \left\| \mathrm I - \mathrm A^{\frac 12} \mathrm X \mathrm A^{\frac 12} \right\|_2 = \left\| \mathrm A^{\frac 12} \mathrm X \mathrm A^{\frac 12} - \mathrm I\right\|_2\end{aligned}

Replacing the constraint $$\mathrm X \succ \mathrm O$$ (positive definite) with $$\mathrm X \succeq \mathrm O$$ (positive semidefinite), we obtain the following convex optimization problem

$$\begin{array}{ll} \text{minimize} & \left\| \mathrm A^{\frac 12} \mathrm X \mathrm A^{\frac 12} - \mathrm I\right\|_2\\ \text{subject to} & \mathrm X \succeq \mathrm O\end{array}$$

• Thank you for your comments. During the last few days and after some manipulation, I arrive at the same result as Rodrigo. It is indeed a simple and elegant result. It is a research question on the optimization of Neumann series. I was not aware the difference between the two web site MathOverflow and stackexchange when posting this. However, since I am a physicist and mechanician, I can not judge the level of difficulty of the question in the mathematic community.. Commented Jul 9, 2018 at 8:09
• Due to the non existing problem of derivatives of eigen values, I have now switched to gradient free methods for optimization. It seems working. Commented Jul 9, 2018 at 8:18
• Which exact problem are you solving? I assume you're dealing with $n > 1$. Commented Jul 9, 2018 at 8:22
• I am dealing with solution of periodic anisotropic heterogeneous conduction problem in the homogenization context using FFT methods. The method is based on the iterative scheme. To achieve the best convergence rate, I have to estimate the spectral radius and minimize it. Currently, I am writing a paper on this. If you are interested, I send you the manuscript when finished. Commented Jul 13, 2018 at 9:18
• @Q.-D.To Will the paper be uploaded to arXiv or the like? If so, please consider posting the link here so I can take a look. Commented Jul 14, 2018 at 18:29