Let $S$ be a set of ordered vectors. Find $\min_{x \in S} \| y-x\|$. Find closest ordered vector.

Question

Let $S=\{ (x_1,x_2,x_3,) : x_1 \le x_2 \le x_3 \}$

For a given by ${\bf y}$ how to solve the following problem \begin{align} \min_{ {\bf x} \in S} \| {\bf y}-{\bf x}\|. \end{align}

The question asks what is the closest ordered vector any other vector.

If ${\bf y} \in S$, then the minimizer is given by ${\bf x}={\bf y}$. Therefore, the interesting case occurs when ${\bf y} \in S^c$.

Answer 1

There is no simple formula; rather, you have to consider cases. Assuming $\mathbf{y}\notin S$, the nearest point $\mathbf{x}\in S$ will lie on the boundary of $S$. We can partition this boundary into three parts:

• the half-plane $x_1=x_2<x_3$;
• the half-plane $x_1<x_2=x_3$;
• the line $x_1=x_2=x_3$.

Here is a recipe for finding the nearest point of $S$:

• Find the nearest point to $\mathbf{y}$ on the plane $x_1=x_2$. If this point is in $S$, we are done.
• Otherwise, find the nearest point to $\mathbf{y}$ on the plane $x_2=x_3$. If this point is in $S$, we are done.
• Otherwise, find the nearest point to $\mathbf{y}$ on the line $x_1=x_2=x_3$.