Finding the minimum of $x_1 + \cdots + x_n$ on ellipsoid

67 Views Asked by At

Let $A$ be a positive definite matrix $n \times n$ and $u^T = [1 \cdots 1]$. Use Lagrange multipliers to find the minimum of $f(x) = u^Tx$ on $h(x) = \frac{x^TAx}{2} = 2$

This is what I did.

$$L(x,\lambda) = f(x) + \lambda (h(x)-2) = u^Tx + \lambda\bigg(\frac{x^TAx}{2}-2\bigg) $$

$$\nabla_x L(x,\lambda) = \nabla f(x) + \lambda \nabla h(x) = u + \lambda Ax = 0 $$

Multiplying both sides by $x^T$: $$x^Tu + \lambda x^TAx = x^Tu + 4\lambda = 0 \Rightarrow \lambda = \frac{-x^Tu}{4} = \frac{-u^Tx}{4}$$

Substituting $\lambda$ in the first equation:

$$u - \frac{u^Tx}{4} Ax = u - Ax \frac{u^Tx}{4} = 0$$

I got stuck here.

How could I finish it?

Edit

I noticed the following:

$$u - Ax \frac{u^Tx}{4} = 0 \iff A^{-1} u - x \frac{u^Tx}{4} = 0 $$

Multiplying both sides by $u^T$: $$u^TA^{-1} u - u^T x \frac{u^Tx}{4} = 0 \iff u^Tx = \pm 2\sqrt{u^TA^{-1}u}$$

Hence: $$u - Ax \frac{\pm 2\sqrt{u^TA^{-1}u}}{4} = 0 \iff x = \pm \frac{2A^{-1}u}{\sqrt{u^TA^{-1}u}} $$

By inspection, the minimum is attempted at $x = - \frac{2A^{-1}u}{\sqrt{u^TA^{-1}u}} $

I think it solves the problem.