1

Given a positive semidefinite matrix $A\in\mathcal{C}\subset\mathbb{S}^n_+$, where $\mathcal{C}$ is a convex set. Define the following minimizers: $$ \bar{A} = \arg\min_{A\in\mathcal{C}} \frac{\lambda_{max}(A)}{\lambda_{min}(A)}, \quad \tilde{A} =\arg\min_{A\in\mathcal{C}} \lambda_{max}(A) - \lambda_{min}(A) $$ $\bar{A}$ is the minimizer of the ratio of largest eigenvalue and smallest eigenvalue; while $\tilde{A}$ is the minimizer of the difference between the largest eigenvalue and smallest eigenvalue. Are the two minimizer equals, i.e., $\bar{A} = \tilde{A}$?

I presume they are not the same in general and perhaps depends on the convex set $\mathcal{C}$. But I think they are somehow connected, as these two objective functions are both trying to bring the largest and smallest eigenvalues closer together.

Shih-Chi Liao
  • 132
  • 7
  • 2
    The reason why one defines the condition number as the first quantity (but not the second) is that it is invariant under scaling. Philosophically, how bad the matrix behaves under perturbations should not change when you scale the matrix. – Levent Oct 04 '22 at 20:44

1 Answers1

2

You can embed any polytope $P\subset\mathbb{R}^n_+$ as a convex set in $\mathbb{S}_+$ via the embedding $(x_1,x_2,\dots,x_n)\mapsto diag(x_1,x_2,\dots,x_n)$. Let $\mathcal{C}$ be the image of $P$ under this embedding. Then, the quantities in question in the polytope world become $$ \kappa_1(P) = \arg\min_{x\in P} \frac{\max_i x_i}{\min_i x_i},\quad\quad \kappa_2(P) = \arg\min_{x\in P}\;\big( (\max_i x_i)-(\min_i x_i)\big). $$

These two minimisers are not necessarily equal. A very simple example is the following: $$ P = \{(x,y)\in\mathbb{R}^2_+\mid x+y=1 \}. $$ Then $\kappa_1(P) = (0.5,0.5)$ but $\kappa_2(P)=(1,0)$ or $(0,1)$.

Levent
  • 4,804