Ratio between min and max value of a quadratic function

117 Views Asked by At

Let $A\in\mathbb{R}^{n\times n}$ be a symmetric matrix and $x\in\mathbb{R}^{n}$. I'm interested in finding an upper bound $\beta\in\mathbb{R}^+$ for the following quotient: $$ \left\vert\dfrac{\min_x x^{\intercal} A x}{\max_x x^{\intercal} A x}\right\vert \leq \beta$$ under the assumption that $\max_x x^{\intercal} A x > 0$.

In particular, I'm interested in finding a bound $\beta$ directly depending on properties of $A$, e.g. its entries, eigenvalues, spectral radius, etc.

I suspect one could gain some insight by analysing the following ratio $$\left\vert\dfrac{\lambda_{\text{min}}(A)}{\lambda_{\text{max}}(A)}\right\vert$$ where $\lambda_{\text{max}}(A)$ and $\lambda_{\text{min}}(A)$ are the largest and smallest eigenvalue of $A$, respectively, though I have tried to follow this path with no luck. Any insight will be highly appreciated!

Edit: I can assume that $x$ is bounded. To simplify, as $\Vert x \Vert \leq 1$.

1

There are 1 best solutions below

0
On

If you look at the case where $A$ is symmetric positive definite, you can get some insight onto how to better formulate this problem. First, you need to actually constrain $\Vert x \Vert > 0$ to make the problem well defined. At that point, the argument that maximizes $x^\top A x$ is the unit-length eigenvector corresponding to $\lambda_\text{max}$. However, a problem becomes apparent in that you can pick $\Vert x \Vert$ to be an arbitrarily small $\epsilon$, in which case there is no well defined minimizing $x$, and the $\beta$ you seek can be any positive number, no matter how small. The infimum of the quadratic form should be zero over all allowed $x$.

I think you probably want to constrain the norm of $\Vert x \Vert$ to be exactly equal to 1. That will give you a well formed problem, and the answer will actually be the ratio of eigenvalues you gave (for positive definite $A$). That's because , if $x^* = \frac{v_\text{min}}{\Vert v_\text{min}\Vert}$, where $v_\text{min}$ is an eigenvector of $A$ corresponding to $\lambda_\text{min}$, then

$$ x^{*\top} A x^* = \frac{v_\text{min}^\top A v_\text{min}}{\Vert v_\text{min}\Vert^2} = \frac{v_\text{min}^\top (\lambda_\text{min} v_\text{min})}{\Vert v_\text{min}\Vert^2} = \frac{\lambda_\text{min} \Vert v_\text{min}\Vert^2}{\Vert v_\text{min}\Vert^2} = \lambda_\text{min}$$

And a similar argument can be made for the maximum value.