The point in a plane that minimizes the sum of distances to points outside it This is a simplified version of an exercise in Bertsekas's nonlinear programming.
Let $ V = \{ x \in \mathbb{R}^3 : a^T x = a_0 \}$  be a hyperplane in $\mathbb{R}^3$ where $a \neq 0$.
Let $x_1 \not\in V$ and $x_2 \not\in V$ be distinct points in $\mathbb{R}^3$.
Let $x^* \in V$  minimize $f(x) = \|x-x_1\| + \|x-x_2\|$ over all $x \in V$.
I want to know if there is a closed form expression for such an $x^*$.
My work:
Any such $x^* \in V$ must satisfy $ \langle \nabla f(x^*),x-x^* \rangle \geq 0$ for all $x$ in $V$. As $x$ varies over $V$, $x-x^*$ varies over all vectors $v$ which satisfy $a^Tv =0$.
So we must have  $ \langle \nabla f(x^*),v \rangle \geq 0$ for all $v$ with $a^T v = 0$. Since $a^T v = 0 \iff a^T (-v) = 0$ we must also have,$ \langle \nabla f(x^*), -v \rangle \geq 0$ for all $v$ such that $a^T v = 0$, i.e., $ \langle \nabla f(x^*), v \rangle = 0$ for all $v$ such that $a^T v = 0$. So there is a scalar $\alpha$ such that $\nabla f(x^*) = \alpha a $, i.e., $\dfrac{x^*-x_1}{\|x^*-x_1\|} +  \dfrac{x^*-x_2}{\|x^*-x_2\|} = \alpha a$.   Geometrically, this says the bisector of the angle determined by $x_1, x^*, x_2$ is parallel to $a$. Is it possible to determine an explicit expression for $x^*$ from this?
 A: If $x_1$ and $x_2$ are on different sides of $V$, you want $x^*$ to be where the straight line from $x_1$ to $x_2$ intersects $V$. The reason that this is true should be rather obvious, but can be formalized by noting that this point yields $$\|x^*-x_1\|+\|x^*-x_2\|=\|x_1-x_2\|$$and then appeal to the triangle inequality.
If they are on the same side, the solution is to first reflect one of the points across $V$, then take the straight line between the two points, and take where that line intersects $V$.
To prove it, consider this: Let's say we reflect $x_2$ across $V$ to $x_2'$. Then we have $\|x-x_2\|=\|x-x_2'\|$ for any $x\in V$, so whichever $x^*$ solves the problem for $x_2'$ (which is given by the straight line as per the first paragraph above), that same $x^*$ will necessarily solve the problem for $x_2$.
So now the question becomes: Can you find a closed form for the reflection of a point, can you find a closed form for the line between two points, and can you find a closed form for the intersection between a line and a plane.
The answers to the above are all yes. If you need to reflect $x_2$, you take the normal vector from $x_2$ to the plane, and add it to $x_2$ twice:
$$
x_2'=x_2+2\frac{a_0-\langle x_2,a\rangle}{\|a\|}\cdot\frac a{\|a\|}
$$
With that out of the way, we want a closed form for the line between $x_1$ and $x_2$ (or maybe $x_2'$, substitute of needed). This is a standard parametrised line solution:
$$
\gamma(t)=t\cdot x_1+(1-t)x_2
$$
Given a parametrised line $\gamma$ and a plane, you find the intersection by solving $$\langle\gamma(t),a\rangle=a_0$$
The closed form solution of this is possible to write down, but a little messy, and I honestly would rather just solve that equation every time rather than trying to remember some formula.
