Maximum value of quadratic form over unit hypercube

77 Views Asked by At

Let $$f(A) = x^T A^{-1} x$$ where the elements of vector $x\in \mathbb{R^{n\times 1}}$ are $0\le x_i \le 1$ and $A\in\mathbb{R}^{n\times n}$ is a covariance matrix (i.e. $A$ is symmetric positive definite matrix). Also the off-diagonal entries of $A$ are $0\le a_{ij} \lt 1$ and the diagonal entries are $0\le a_{ii}\le 1$. I want to find $A$ such that $f(A)$ is maximized for each vector $x$. I think it holds that $$\forall i:0\le x_i\le1 \implies x^T A^{-1} x \le x^Tx$$and the equality occurs for $A = I$ where $I$ is the identity matrix. I tried multiple examples but I couldn't show that formally. Does the mentioned implication hold?

Edit: @Pestertennis has provided a counterexample. So I revised the inequality: $$x^TA^{-1}x \le x^Tx \frac{1}{\max(A)}$$

1

There are 1 best solutions below

1
On BEST ANSWER

Consider $A = cI$ where $c > 0$. Then $x^TA^{-1}x = \frac{1}{c}x^Tx$. So, if $c = \frac{1}{2}$ for example, then the implication does not hold.


As for your new inequality: Consider $A = \begin{pmatrix}3 & 1 \\ 1 & 3\end{pmatrix}$ and $A^{-1} = \frac{1}{8}\begin{pmatrix}3 & -1 \\ -1 & 3\end{pmatrix}$. Taking $x = e_1$ gives $x^TA^{-1}x = \frac{3}{8}$ while $x^Tx\frac{1}{\text{max}(A)} = \frac{1}{3}$ contradicting your claim.