1
$\begingroup$

I've been working on some distributed optimization problems and faced a bit of a challenge with the following question.

Given $A_1, A_2, .., A_m \in M_n({\mathbb{R})} $ symmetric positive definite matrices, find a symmetric positive definite matrix $B_*$ that minimizes the following quantity : \begin{equation} \min_B \max_i \kappa(A_iB^{-1}) \end{equation}

Where $\kappa(M) = \frac{\sigma_{max}(M)}{\sigma_{min}(M)}$ is the condition number of matrix $M$ (With respect to the euclidean norm), defined as the ratio between the largest and smallest singular value of $M$, $\sigma_{max}(M)$ and $\sigma_{min}(M)$ respectively.

$ \kappa(A_iB^{-1}) $ can be seen as a relative condition number of $A$ with respect to a "slightly" more general geometry, induced by the matrix $B$

In other words, the aim is to find a matrix that minimizes the worst relative condition number of the initial matrices.

Do you think it's possible to have an exact form of $B_*$, or a decent approximation to $B_*$ in certain cases ? And in general, can you think of an implementable (preferably distributed) optimization method that can converge to the optimum $B_*$ ?

Improve this question
$\endgroup$
2
  • $\begingroup$ Do you mean symmetric, positive definite, when you write positive definite? Be careful that the product of symmetric matrices need not be symmetric. The condition number of $A_iB^{-1}$ is usually not defined in terms of the eigenvalues of the matrix, as this matrix is not symmetric. $\endgroup$
    – Fabian Wirth
    Commented Jul 26, 2022 at 23:13
  • $\begingroup$ Thank you for pointing that out. Indeed the initial matrices are supposed to be symmetrical. I edited the question to account for that confusing definition of condition number. $\endgroup$
    – TrevLou
    Commented Jul 28, 2022 at 9:19

0

Reset to default

You must log in to answer this question.