Is there an analytical solution for the following optimization problem?

Question

We need to solve the following least square problem $$\min_x (Y-Ax)^T(Y-Ax)$$ $$s.t. x^TA^TAx=1$$ in a closed form, where $Y \in \mathbb{R}^{n\times 1}$ and $A \in \mathbb{R}^{n\times n}$ are given.

Can anyone help us? Thanks a lot!

Answer 1

There is if $A$ is full rank. To see that, you can build the Lagrangian

$$(y-Ax)^T(y-Ax)-\lambda(x^TA^TAx-1).$$

The derivative with respect to $x$ is given by

$$2x^TA^TA-2y^TA-2\lambda x^TA^TA.$$

Equating this to zero yields the solution

$$x^{*T}=y^TA(A^TA)^{-1}/(1-\lambda).$$

The Hessian is given by $2A^TA(1-\lambda)$ and must be positive to ensure that we have a minimum. We will get back to that later.

From the constraint $x^TA^TAx-1=0$, we get that

$$(1-\lambda)^2=y^TA(A^TA)^{-1}A^Ty.$$

Solutions to that equation are

$$\lambda=1\pm\sqrt{\alpha},\ \alpha:=y^TA(A^TA)^{-1}A^Ty.$$

The minimum is attained for

This yields $\lambda=1-\sqrt{\alpha}$ since this value makes the Hessian positive definite, which yields

$$x^*=\dfrac{(A^TA)^{-1}A^Ty}{(y^TA(A^TA)^{-1}A^Ty)^{1/2}}$$