Find closest point(s) in subset of $\mathbb{R}^4$

Question

I am trying to solve the following problem I came up with:

Let $W = \{(x_1, x_2, x_3, x_4) \in \mathbb{R}^4 : x_1 + x_2 + x_3 + x_4 = 1\}$

Then, for any $p \in \mathbb{R}^4$, what are the $k$ points $\{q_j\}_{j=1}^k$ closest to $p$, where $q_j \in W$

I don't know what to do since, normally I would work with a subspace of $\mathbb{R}^4$ and use orthogonal decomposition. In this case, $W$ is not a subspace of $\mathbb{R}^4$. Eventually, I want to do the same thing, but with the convex subset $V = \{(x_1, x_2, x_3, x_4) \in \mathbb{R}^4 : \sum_{j=1}^4x_j=1, x_j\geq0\}$.

Answer 1

Even though $W$ is not a subspace of $R^4$, it is still nonempty, closed and convex. These three conditions imply that there is still a unique point $w \in W$ which is closest to a given point $p \in R^4$.

You could calculate it explicitly by finding a vector which is orthogonal to all three directions of the (hyper)plane defined by $W$. Since you can write $$W = \{ (0,0,0,1)+r(1,0,0,−1)+s(0,1,0,−1)+t(0,0,1,−1) : r,s,t \in R \} $$ as I explained in the other post (Finding basis of subspace of $\mathbb{R}^4$ such that $x_1 + x_2 + x_3 + x_4 = 1$), you need to find a vector in $R^4$ that is orthogonal the three spanning vectors.

To do that, you can for example use a generalization of the cross product, as explained here (Cross product in higher dimensions).

Once you have this vector, just construct a line through $p$ in the direction of this vector, and intersect it with the plane $W$. That should give you the best approximation to $p$ in $W$.

Answer 2

In general, if $C$ is a closed convex subset of $\mathbb{R}^n$ then for any $p$ there is a unique minimiser of the problem $\min_{x \in X} \|p-c\|$, where $\|\cdot\|$ is the euclidean norm.

You could solve the problem using Lagrange multipliers, in particular, you want to solve $\min \{ {1 \over 2} \|p-w\|^2 | e^T w = 1 \}$, where $e=(1,1,1,1)^T$.

This gives $p-w+\lambda e = 0$ from which we get $e^Tp-1+4\lambda = 0$. Solving for $\lambda$ gives an expression for the minimiser $w$.