# Find the orthogonal projection of $y \in \mathbb{R}^3$ onto the space $\{x: x_1^2 + 2 x_2^2 + 3 x_3^2 \leq 1\}$

Find a formula for the orthogonal projection of $$y \in \mathbb{R}^3$$ onto the space $$\{x: x_1^2 + 2 x_2^2 + 3 x_3^2 \leq 1\}$$. The formula should depend on a single parameter that is a root of a strictly decreasing one-dimensional function.

It's obvious that $$x = y$$ when $$y$$ is in the set in question, so throughout assume that $$y$$ is not in the space onto which we are projecting (which also gives us that $$y$$ is non-zero).

Here's what I feel is my best attempt so far: Write $$f(x) = \|x - y\|^2 = x^Tx - 2 x^T y + y^T y$$ and $$g(x) = x^T Q x - 1$$, where

$$Q = \begin{pmatrix} 1 & 0 & 0\\ 0 & 2 & 0 \\ 0 & 0 & 3 \end{pmatrix}$$

Then $$\nabla f(x) = 2x - 2y$$ and $$\nabla g(x) = 2Qx$$. Notice that both $$f$$ and $$g$$ are strictly convex. This means that the solution to the problem can be found by solving the system of equations

$$\begin{cases} \lambda_0 \nabla f(x) + \lambda_1 \nabla g(x) = 0 \\ \lambda_1 g(x) = 0 \end{cases} = \begin{cases} \lambda_0 x - \lambda_0 y + \lambda_1 Qx = 0 \\ \lambda_1 x^T Q x = \lambda_1 \end{cases}$$

with $$\lambda_1, \lambda_2 \in \mathbb{R}_+$$. I cannot get past this point. I feel like I got really close when I found that this can be written as

$$\begin{cases} x = \left(I + \frac{\lambda_1}{\lambda_0}Q\right)^{-1} y \\ x^T (y - x) = \frac{\lambda_1}{\lambda_0}\end{cases}$$

After this point though I just go in circles.

• What you call "space" there in the first line is not a linear space, so what do you mean by "space"? – DonAntonio Oct 27 '18 at 0:19
• @DonAntonio it's a set, a subset of $\mathbb{R}^3$. So it's not a vector space. – cgmil Oct 27 '18 at 0:41
• you should use the KKT conditions instead of the Fritz John conditions (so $\lambda_0=1$) – LinAlg Oct 27 '18 at 1:20
• @LinAlg That's better but I basically end up in the same place. – cgmil Oct 27 '18 at 7:01
• @KaviRamaMurthy your answer does not satisfy $x = (I+\lambda Q)^{-1}y$. – LinAlg Oct 27 '18 at 15:22

The KKT conditions are $$\begin{cases} x - y + \lambda Qx = 0 \\ \lambda( x^T Q x-1) = 0 \\ x^T Q x\leq1 \\ \lambda \geq 0 \end{cases}$$ If $$\lambda=0$$, you get $$x=y$$, which is feasible only if $$y^TQy \leq 1$$. Therefore, $$x=y$$ is optimal if $$y^TQy \leq 1$$.
If $$y^TQy > 1$$, $$\lambda \neq 0$$, so $$x^T Qx = 1$$. You already mentioned $$x = (I+\lambda Q)^{-1}y$$, so $$x_i = y_i / (1+\lambda i)$$, so $$x^T Qx = \sum_i i y_i^2 / (1+\lambda i)^2 = 1$$, which you can solve for $$\lambda$$ (taking the solution with $$\lambda>0$$).
• I basically reached this point but I cannot figure out how to solve for $\lambda$. Maybe it's in front of my face and I can't see it but in any case can you show how to solve for $\lambda$? I even tried using SymPy and the solver hung. Is it possible that you need to solve for $\lambda$ numerically? – cgmil Oct 27 '18 at 17:20
• @cgmil consider $h(\lambda) = \sum_i i y_i^2 / (1+\lambda i)^2 - 1$ for $\lambda >0$. This seems like one-dimensional function in your question. Bisection search will work to numerically find a root. – LinAlg Oct 27 '18 at 17:27