How to show that $\min_{x \in \mathbb{R}^4} x^Tx$ subject to $x^TAx \geq 1$ has a global minimizer?

323 Views Asked by At

Consider the following problem:

$$\min_{x \in \mathbb{R}^4} x^Tx$$

over $C=\{x \in \mathbb{R}^4 \mid x^TAx \geq 1\}$ where $A \in \mathbb{R}^{4 \times 4}$ is a symmetric matrix with two distinct positive eigenvalues and other eigenvalues of $A$ are nonpositive.

How to show that this problem has a global minimizer?

I need to show that there exist $x_*$ in $C$ for which I have $$ x_*^Tx_* \leq x^Tx \,\,\, \forall x \in \mathbb{R}^4 $$

or to come up with something like the following $$ \|x\|^2= \|x_*\|^2 + \alpha \,\,\, \forall x \in \mathbb{R}^4 ,\,\,\, 0<\alpha \in \mathbb{R} $$

My try:

$A$ is symmetric, so it can be written as $A=u \Lambda u^T$. Hence,

$$ x^TAx=x^Tu \Lambda u^Tx \geq 1 $$

So

$$ z^T \Lambda z \geq 1 $$ where $u^Tx=z \in \mathbb{R}^4$. So the optimization problem would be

$$\min_{x \in \mathbb{R}^4} z^Tz$$ over $z^T \Lambda z \geq 1$. How can we proceed?

1

There are 1 best solutions below

4
On BEST ANSWER

Choose some $R>0$ such that $B_R:=\{z^Tz\le R^2\}$ has nonempty intersection with $F:=\{z^TAz\ge1\}$. Now $B_R\cap F$ is compact and has a global minimiser, which must also be a global minimiser for the original problem (why?).

Hint: minimisation over $F$ is minimisation over $(F\cap B_R)\cup (F\cap\text{cl}( B_R^c))$. But minimising $\|x\|^2$ over $(F\cap B_R)$ must yield an optimal value that is smaller than or equal to minimising over $(F\cap\text{cl}( B_R^c))$.