Let be a set of points in , and let denote the convex hull of . We are often interested in finding the point in that is nearest to some reference point , known as the Euclidean projection onto . Let’s denote this point by .
Optimality condition for when
Wolfe (1976) (Reference 1) provides an optimality condition for when the reference point is the origin, i.e. .
Theorem. Let be a point in . if and only if
Rearranging the condition above gives us . Fixing , note that represents the hyperplane passing through which is orthogonal to the line segment going from to . Hence, the condition means that the directed line segment from to and the directed line segment from to make an angle that is . Geometrically, this means that and lie on different sides of the hyperplane , and so is nearer to than .
The diagram below demonstrates this in two dimensions. In both figures, the candidate for being the nearest point, , is . is the nearest point to the origin in the left figure but not the right figure. The angles that the optimality condition looks at are the angles between the black arrow and the colored arrows: they are also marked by little arcs. We see that in the left figure, both the angles are . In the right figure, the yellow angle is . It corresponds to a vertex of the polytope that is on the same side of the hyperplane (dotted line) as the origin, and hence some point on the line is going to be closer to the origin than .
Optimality condition for any
Let . Projecting onto is equivalent to projecting onto and then adding to it:
Hence, a point is if and only if
(Note: I learned of the iff condition for general from Reference 2.)
- Wolfe, P. (1976). Finding the nearest point in a polytope.
- Ramanath, R. (2022). Efficient vertex-oriented polytopic projection for web-scale applications.