Equivalent between maximisations

36 Views Asked by At

Why

$$ argmax_x \ (x^TAx )/ (x^TBx) $$

equivalent to

$$ argmax_x \ x^TAx \ s.t. \ x^TBx=1 $$

When $x\in \mathbb{R}^n; A\succeq0,B \succ0 \in\mathbb{R}^{n\times n}$

3

There are 3 best solutions below

3
On

Suppose $$ x^TAx\leq z^TAz \ \forall x \ s.t. \ x^TBx = 1.$$

Then, take $x$ and define $y = \frac{x}{\sqrt{x^TBx}}.$ Then, $y^TBy = 1$. From above, $$y^TAy \leq z^TAz.$$ Hence,

$$\frac{x^TAx}{x^TBx} \leq \frac{z^TAz}{z^TBz}, $$ as $ z^TBz= 1.$

Conversely, assume $$ \frac{x^TAx}{x^TBx} \leq \frac{z^TAz}{z^TBz} \ \forall x.$$

Define $z' = \frac{z}{\sqrt{z^TBz}}.$ Then, $z'^TBz'= 1.$ Take $x \ s.t. \ x^TBx = 1.$ Then, from above, we get $ x^TAx \leq z'^TAz'.$

0
On

$$argmax_x x^TAx \ s.t. x^TBx=1 $$

Let's define $y$ following way

$$ x = \frac{y}{\sqrt{y^TBy}} $$

$$argmax_y \frac{y}{\sqrt{y^TBy}}^TA\frac{y}{\sqrt{y^TBy}} \ s.t. \frac{y}{\sqrt{y^TBy}}^TB\frac{y}{\sqrt{y^TBy}}=1 $$

$$argmax_y \frac{y^TAy}{(\sqrt{y^TBy})^2} \ s.t. \frac{y^TBy}{(\sqrt{y^TBy})^2}=1 $$

$$argmax_y \frac{y^TAy}{y^TBy} \ s.t. \frac{y^TBy}{y^TBy}=1 $$

$$argmax_y \frac{y^TAy}{y^TBy} \ s.t. 1=1 $$

$$argmax_y \frac{y^TAy}{y^TBy} \ \blacksquare $$

Based on @Peteto answer

2
On

A nicer way, I believe would be (the idea is correct though)

Start with,

$$argmax_x x^TAx \ s.t. x^TBx=1.$$

Then,

$$\bigg(argmax_x x^TAx \ s.t. x^TBx=1\bigg) = \bigg(argmax_x \frac{x^T}{\sqrt{x^TBx}}A\frac{x}{\sqrt{x^TBx}}\bigg) = \bigg(argmax_x \frac{x^TAx}{x^TBx}\bigg).$$