A linear subspace is only one kind of constraint. A feasible vector may instead have nonnegative coordinates, or lie on one side of a hyperplane. In such cases the residual from a nearest point is generally not orthogonal to every feasible direction: some directions are forbidden. The right replacement is an inequality, and it leads to an iterative method for constrained minimization.
Definition 4.2.1
(Convex set and its projection)
Throughout, is a real Hilbert space. A set is convex if whenever and . When is nonempty, closed and convex, its projection means the unique point of nearest to ; existence and uniqueness are part of the next theorem.
Nearest points and an inequality
Theorem 4.2.2
(Projection onto a closed convex set)
Let be nonempty, closed and convex. For each there is a unique with . A point is this nearest point if and only if
Proof
(Minimizing sequence and a one-sided derivative)
Let and choose with . Convexity puts in , so its distance from is at least . The parallelogram identity gives
The right side tends to zero, so is Cauchy. Completeness gives a limit and closedness places it in ; continuity of the norm gives distance .
For , the segment is feasible for . Minimizing at yields
Divide by and let to obtain (1). Conversely, (1) implies
Thus is nearest and no distinct can be equally near. In particular the nearest point found in the first paragraph is the unique point satisfying (1).
Proof X-ray
Why both assumptions matter
The proof has an existence half and a characterization half, and they use the hypotheses differently. Existence uses convexity once, to put the midpoint in so that its distance is at least ; the parallelogram identity then converts near-optimality of two points into closeness of the points. Completeness of produces a limit, and closedness of keeps it feasible. The characterization uses convexity a second time, in a different way: whole segments stay in , but only for . That one-sidedness is the key move. It is why the first-order condition is an inequality rather than an equation: dividing by keeps the sign, while negative is not available. The converse closes the argument because the expansion of contains exactly the term controlled by (1), and the leftover gives uniqueness without a separate argument.
If is a closed linear subspace, for every and . Applying (1) with and gives , recovering the familiar orthogonal projection. Both remaining hypotheses are genuinely needed, as two subsets of the real line show.
Counterexample mode
Without closedness or without convexity
Claim: every nonempty convex set, or every nonempty closed set, has exactly one nearest point to each . In , the convex set has , and no has , so there is no nearest point to . The closed nonconvex set has , so has two nearest points. The theorem needs both hypotheses: closedness for existence and convexity for uniqueness (and for the Cauchy argument).
Common mistake
(Replacing the inequality by orthogonality)
For a general closed convex set, the residual need not be orthogonal to . Take and . Then and , which is negative, not zero, for . Orthogonality holds when every feasible direction can also be reversed, as in a subspace; at a boundary point of a convex set only the inequality (1) is available.
Worked example 4.2.3
(Projection onto the closed unit ball)
Let . If , then . Otherwise put , so and with . For , Cauchy–Schwarz gives , hence
By (1), . At the boundary case both formulas give .
The projection is stable
Proposition 4.2.4
(Firm nonexpansiveness of the projection)
For a nonempty closed convex and all ,
In particular .
Proof
(Add the two variational inequalities)
Set and . Applying (1) at with gives ; applying it at with gives . Adding,
which rearranges to (2). Cauchy–Schwarz bounds the right side of (2) by ; cancellation when gives , and the same estimate is trivial when .
Thus small changes of input cannot increase the distance between projections. The inequality is stronger than mere continuity and does not claim strict contraction.
Worked example 4.2.5
(Projection onto a half-space)
Fix nonzero and , and set . If , then . Otherwise put and . Then , so lies on the boundary, and for every ,
By (1), . For instance, the projection of onto in uses , and , giving .
A constrained quadratic and an iteration
Let be bounded and self-adjoint, and suppose there are constants such that
For fixed , minimize over a nonempty closed convex set .
Theorem 4.2.6
(Constrained quadratic minimization)
Under these assumptions, has a unique minimizer on , characterized by the variational inequality
For and any , the projected iteration satisfies with .
Proof
(A contraction whose fixed point solves the inequality)
If , everything is immediate. Otherwise define . By (2), in particular nonexpansiveness, and self-adjointness,
For nonzero , Cauchy–Schwarz gives , so and . The step-size bound makes it strictly less than one; thus lies in . The contraction theorem on complete gives a unique fixed point , and the iterates satisfy . By (1) applied to the point , the equation says for all , which is exactly (3) since .
For any , writing and using self-adjointness gives
Hence is the unique minimizer. Conversely, if minimizes over , the one-sided derivative of at for is and is nonnegative, so (3) holds.
Common mistake
(The contraction comes from the gradient step)
The projection alone is not a contraction: for and inputs and , both projections equal their inputs and . The factor in the proof comes from , which uses the coercivity constant . Nonexpansiveness of only guarantees that projecting does not undo that gain.
The bound on is a sufficient condition, not a claim that every larger step fails, but some limit on the step size is necessary.
Counterexample mode
A step that is too long
Claim: the projected iteration converges for every step size . Take , (closed and convex), and , so and . The iteration is . For it becomes ; from the iterates alternate and never converge. For they double in absolute value. Convergence for every starting point holds exactly when , that is , which here coincides with the guaranteed range .
Worked example 4.2.7
(An active constraint reached in finitely many steps)
Take , , and , so . The unconstrained stationary point solves , so it is , which is infeasible. Here (3) holds at , since for every . With the guaranteed range is ; take . Then , so
Starting at gives , , and , after which the iterates stay at . The constraint is active at the solution, and the projection is what stops the iterates from following the gradient to .
Practice
Quick check
(Find and check (1).)
The nearest nonnegative number to a negative number is a boundary point.
Solution · Answer
The projection is . For every , , so (1) holds.
Quick check
(Show that if is closed and convex, then . Does this imply that is linear?)
A point of is at distance zero from itself.
Solution · Answer
already belongs to , so its unique nearest point in is itself. Linearity need not hold: for , .
Quick check
(Minimize over , and verify (3).)
Write in the form .
Solution · Answer
Here and . The candidate is : for , , so (3) holds. The minimum value is .
Quick check
(For , show that equality can hold in the nonexpansive estimate for two distinct inputs.)
Choose inputs that are already feasible.
Solution · Answer
For and , both projections equal their inputs, so .