Use feasible geometry to certify nearest points

Try

Find the nearest point to z=(3,0) on the line x+y=1. Moving perpendicular to that line subtracts a multiple of (1,1). Solving (3−t)+(−t)=1 gives t=1, so the projection is p=(2,−1). For any other point p+d on the line, d has coordinate sum zero and is perpendicular to z−p=(1,1). The Pythagorean identity then proves that p is globally nearest, not merely a visually plausible point.

Predict

Predict what changes for a half-plane instead of a line. The displacement toward the projection need not be perpendicular to every feasible direction, because some directions point deeper into the set. The correct condition becomes an inequality. Also predict whether a closed set always has a unique nearest point: the two-point set {−1,1} has two equally near points to zero. Convexity is the additional geometric condition that removes this ambiguity in Euclidean projection.

Experiment

For C=[0,2] and z=4, the projection is p=2. Test the projection certificate (z−p)(x−p)≤0 at several feasible points.

Feasible x	x−p	Certificate product
0	−2	−4
1	−1	−2
2	0	0

The point checks illustrate a general proof: every feasible x≤2 makes the product nonpositive. A finite table alone would not establish the condition for all points in an arbitrary set. Change z to 1 and verify that its projection is itself, making every certificate product zero.

Understand

A set C is convex when (1−t)x+ty belongs to C for all x,y in C and t in [0,1]. Intersections of convex sets are convex because the segment remains in every constituent set. Affine sets, half-spaces and Euclidean balls are convex. Unions generally are not. Empty sets satisfy the segment definition vacuously, but projection and optimization existence require nonemptiness explicitly.

For a nonempty closed C in finite dimensions, restricting the distance search to a sufficiently large closed ball gives a compact search set, so a nearest point exists. If C is also convex, two distinct nearest points would have a midpoint with strictly smaller squared distance, contradicting minimality. For a feasible p, the exact projection characterization is (z−p)·(x−p)≤0 for every x in C. Necessity follows by differentiating the squared distance along the feasible segment from p toward x at its initial endpoint. Sufficiency follows by expanding ||z−x||² into ||z−p||²+||x−p||²−2(z−p)·(x−p).

Apply

Prove that projections are nonexpansive. If p=P_C(z) and q=P_C(w), apply the certificate once with x=q and once with x=p. Adding and rearranging gives ||p−q||²≤(p−q)·(z−w). Cauchy–Schwarz then gives ||p−q||≤||z−w||, with the zero-distance case handled directly. This stability property will support projected algorithms later. It depends on the same closed convex set for both projections.

As a counterexample exercise, project zero onto C={−2,2}. Both points minimize distance, and the convex projection inequality fails if either is tested against the other. The issue is not numerical accuracy: the needed segment between the two points is absent from the feasible set.

Continue

Use the projection certificate to turn a proposed nearest point into a proof. State the set’s nonemptiness, closedness and convexity rather than relying on a picture. Continue to Convex functions and certificates. There, a related supporting inequality will convert local derivative information into a global objective bound and explain why convex optimization has stronger guarantees than arbitrary nonlinear search.