1
$\begingroup$

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.

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

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$).

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – cgmil Oct 27 '18 at 17:20
  • $\begingroup$ @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. $\endgroup$ – LinAlg Oct 27 '18 at 17:27
  • $\begingroup$ Okay, that actually sounds like how the problem was intended to be solved, so you get the credit. Thanks! $\endgroup$ – cgmil Oct 27 '18 at 17:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.