Minimize $\|x\|^2_2$ subject to $(v+x)^\top M (v+x)=a$

70 Views Asked by At

Given a symmetric positive definite matrix $M$, a vector $v$ and $a\in\mathbb{R}_+$ I would like to find

$$\min\|x\|^2_2 \quad\text{subject to}\quad (v+x)^\top M (v+x)=a.$$ If I'm not mistaken, the geometrical interpretation is to find the point $v+x$ on an (hyper)ellipsoid which is closest in the sense of the Euclidian norm to $v$ (btw $v$ is inside the ellipsoid in my case).

I am looking for a closed-form solution, if possible. I defined the Lagrangian:

$$f(x,\lambda)=\|x\|^2 + \lambda \big((v+x)^\top M (v+x)-a\big)$$

and the optimality conditions reads as

$$ \partial_1 f = 2x+2\lambda M(x+v)=0 \quad \text{and}\quad \partial_2 f = (v+x)^\top M (v+x)-a=0.$$

From the first equality,

$$x=-\lambda (I+\lambda M)^{-1} Mv.$$

Injecting this expression in the second equality: $$\big(v-\lambda(I+\lambda M)^{-1}Mv\big)^\top M \big(v-\lambda(I+\lambda M)^{-1}Mv\big) =a$$

How can I solve this equation for the real $\lambda$?

1

There are 1 best solutions below

6
On BEST ANSWER

There is a closed-form solution. Actually the problem is quadratic in $\lambda$. To simplify matters, diagonalize $M$ first, and let $y = v + x$. The optimality condition would be $$y = \left( I+\lambda M\right)^{-1}v$$ and $$y^TMy=a$$ $\Rightarrow$ $$v^T(I+\lambda M)^{-T}M(I+\lambda M)^{-1}v=a$$ Suppose $M = diag(\sigma_1,\sigma_2,...,\sigma_n)$. Expanding the above equation, we'll get a quadratic equation for $\lambda$.

Modification in response to some questions (explaining what "diagonalize $M$ first" means): Let $M = Q^TDQ$, where $Q$ is orthogonal and $D$ is diagonal. Then the problem becomes $$\min\|x\|^2_2 \quad\text{subject to}\quad (v+x)^T Q^T DQ (v+x)=a$$ Let $\tilde{v} = Qv$, $\tilde{x}=Qx$. Note that $\|\tilde{x}\|_2=\|x\|_2$. Then the problem is $$\min\|\tilde x\|^2_2 \quad\text{subject to}\quad (\tilde v+ \tilde x)^T D (\tilde v+ \tilde x)=a$$