Convex feasibility and projection geometry

For a nonempty closed convex set C in a real Hilbert space, the projection p of x is the unique point minimizing squared distance to x. It is characterized by $\langle x-p,z-p\rangle\le0$ for every z in C. Necessity follows by differentiating squared distance along the feasible segment from p to z. Sufficiency follows by expanding the squared distance to any z: the cross term has the correct sign, so no feasible point is closer. This certificate proves a global nearest-point statement without searching the whole set numerically.

Projection is the proximal map of the indicator and the resolvent of the normal cone. Its firm nonexpansiveness therefore follows from the preceding lesson, but the variational inequality also gives a useful Pythagorean inequality relative to every feasible z. Orthogonal projection onto an affine subspace gives equality in the associated orthogonality relation; a curved set or a halfspace generally yields an inequality. Confusing these cases can produce an incorrect geometric proof. Closedness matters for attainment, and convexity matters for uniqueness and the global normal certificate.

Now take nonempty closed convex C and D in $\mathbb R^d$, with a nonempty intersection, and iterate x_{k+1}=P_C(P_Dx_k). For any fixed z in the intersection, applying the Pythagorean inequality twice shows that distances to z never increase and that the squared correction lengths have a finite sum. This is Fejér monotonicity with respect to the intersection. The corrections therefore tend to zero. The iterates stay bounded, so finite-dimensional compactness gives a cluster point; vanishing corrections and closedness place it in both sets.

Once a cluster point lies in the intersection, Fejér monotonicity forces the full sequence to converge to it: the distances to that particular point are nonincreasing and have a subsequence tending to zero. This proves norm convergence in the stated finite-dimensional setting. It gives neither a universal convergence rate nor a guarantee that the limit equals projection of the starting point onto C∩D. Computing that nearest point is a different optimization task; methods such as Dykstra’s algorithm add correction variables rather than simply alternating the unmodified projections.

If the intersection is empty, the preceding argument has no feasible reference z. Alternating points may approach a best-approximation pair, may fail to attain an inter-set distance, or may escape to infinity. Two disjoint closed convex sets can even have distance zero: take the epigraph of exp(x) in the plane and the lower halfspace y≤0. Their vertical gap can be arbitrarily small as x tends to negative infinity, yet they share no finite point. Thus a small distance between two repaired points is not an exact feasibility certificate.

A practical stopping rule should measure the original constraints and say whether its tolerance is absolute or relative to chosen units. To certify infeasibility one needs additional information, such as a strict separating inequality with a verified gap; a long sequence of unsuccessful projections is insufficient. For equality subspaces, projection can often be computed by solving a linear system, whose numerical conditioning also matters. The abstract nearest-point operator assumes exact evaluation. Approximate projections require an error-controlled convergence argument, especially when errors accumulate instead of diminishing along the iteration.