Why supporting slopes lead to a different algorithm
A gradient describes the unique tangent plane to a differentiable function. At a corner there may be many supporting planes, and each gives a valid global lower bound. This extra choice is useful: absolute values, maxima of affine losses, and sums of such terms can be optimized without smoothing away their corners. It also changes the convergence argument. A negative subgradient need not be a direction of decrease, so the smooth descent lemma cannot simply be reused.
We will first establish calculus rules whose assumptions can actually be checked. Throughout the calculus section, functions are convex and finite on all of . This restriction removes domain-boundary complications; it is stronger than some general convex-analysis theorems require. We will prove the sum rule in this setting and later exhibit its failure when the restriction is dropped. For the algorithm, the constraint is a separate nonempty closed convex set , while the objective remains finite on the whole space.
The geometric prerequisites are Euclidean projection and the finite-dimensional separation theorem used in the preceding note on separation and strong duality: two disjoint nonempty open convex sets admit a nonzero separating linear functional; an open convex set and a point outside it admit a nonzero weak separator. These are the separation results used below.
A subgradient is a lower bound, not a chosen derivative
For a finite convex function , define
The quantifier “every ” matters. A vector that supports the graph only for a few tested points has not been shown to be a subgradient. The set is closed and convex, because each displayed inequality defines a closed half-space in the variable .
Two immediate consequences help interpret the definition. First, exactly when is a global unconstrained minimizer. Second, differentiability at forces : test a supporting inequality at , divide by positive , and let tend to zero; repeat with . Convexity supplies the supporting inequality for the gradient.
Why a supporting slope exists in the finite case
Lemma 5.2.1
(Finite convex functions are continuous and subdifferentiable)
Let be convex. Then is continuous, and is nonempty for every .
Proof
(A local bound and a supporting hyperplane)
We need continuity before applying open separation. Here is a useful elementary argument. Fix and a cube , with . Let be the maximum of at its finitely many vertices. Every point of the cube is a convex combination of the vertices, so on the cube. In particular .
For , put and . Convexity gives . The same upper bound holds for . Since , we obtain
Thus is continuous at every . This is a local estimate about the fixed center ; we have not assumed a global Lipschitz constant.
Now the strict epigraph is open and convex, while is outside it. Separation and a limit from to that point give a nonzero pair with
Sending upward shows . If , the inequality holds for every and forces , a contradiction. Hence . Letting decrease to shows that . Full finiteness on the whole space is doing real work in the argument that cannot vanish.
Calculus with explicit hypotheses
Theorem 5.2.2
(Finite convex sum rule)
Let be finite convex functions. At every ,
where the right side is the Minkowski sum .
For , . If , then
Adding the two supporting inequalities proves the inclusion from right to left in the sum rule. Scaling and the affine rule follow in both directions by dividing or subtracting the corresponding defining inequalities. The reverse sum inclusion requires an argument; it does not follow from addition alone.
Proof
(Split by separating two open sets)
Take . For , write and . Consider
They are nonempty open convex sets. They are disjoint because the subgradient inequality says . Both have in their closures. Their separator can therefore be written, with a nonzero , as
The common threshold is zero because both closures contain the origin. The upward vertical rays of force . If , the first inequality holds for every , since contains a point above every ; hence , contradicting nonzero separation. Normalize to .
Taking limits to the two graph boundaries gives
Consequently and . This proves the missing inclusion and the equality.
Proof X-ray
Why the hard inclusion needs separation
Adding supporting inequalities gives only . The reverse inclusion must split one supporting plane of the sum into two pieces, and the inequality does not say how. The proof turns this into geometry: lies above the graph of , lies below the graph of , and the subgradient inequality for is exactly their disjointness. Finiteness on enters twice. It makes and continuous, so both sets are open and open separation applies; and it puts a point of above every , which forces . With the separating slope is the piece assigned to , and the piece assigned to . The counterexample below shows that when one function is finite only on a half-line, no such split need exist.
Repeated use gives a finite-sum rule. The rule for a zero coefficient should be handled directly: the constant zero function has subdifferential . Negative multiplication does not preserve convexity in general.
Exact calculus for a maximum of affine functions
Let
Proposition 5.2.3
(Subdifferential of a maximum of affine functions)
With and as above, for every ,
Proof
(Active pieces and a projection)
Each active affine function is a global lower bound touching at . Its slope is therefore a subgradient, and convex combinations remain subgradients.
For the converse, let lie outside the convex hull of the active slopes. This hull is nonempty, compact and convex. Put and . The projection inequality gives for every active slope, while . Thus . Inactive affine functions have positive gaps at . Since there are finitely many, for all sufficiently small none can exceed at . An active slope attaining does attain that value, so . This contradicts the supporting inequality for . Thus the stated hull contains every subgradient.
Concept lensGeometric
A corner records several active linear models
For , the active slopes at zero are and , and their convex hull is . Away from zero only one affine function is active. The interval at the corner does not mean that an ordinary derivative can be chosen arbitrarily; it records all globally supporting lines.
If a finite convex is globally -Lipschitz in the Euclidean norm, every satisfies . Indeed, the supporting and Lipschitz inequalities at give for each unit and . For , choose . A maximum of affine functions with has this property, and the hull formula also proves the subgradient bound directly.
Worked example 5.2.4
(Subgradients of a maximum of three lines)
Find and the global minimum of .
At zero the first two affine functions are active, with slopes and ; the third value is . Therefore , which contains zero. The minimum is . Directly, for the first affine function is at least one, and for the second is at least one. These bounds are strict when , so zero is the unique minimizer.
What fails without the domain assumptions
Counterexample mode
The unrestricted extended-valued sum rule is false
Permit the value to exclude points from a function's domain. At a domain point, use the same supporting-inequality definition of the subdifferential; the inequality is automatic where the function value is . On , define
These are proper lower semicontinuous convex functions: “proper” means never and finite somewhere. At zero, would require for every , or . No finite can satisfy this as decreases to zero. Hence is empty. On the other hand, , while and therefore . The sum of the individual subdifferentials is empty.
The repair is to use a qualified sum theorem with its actual hypotheses. Our finite-on- theorem is one sufficient version. We have not proved a general domain-relative-interior rule here.
Projected subgradient steps
Let be nonempty, closed and convex; let be finite and convex. Choose , positive step sizes , and any . Set
The projection is uniquely defined under these hypotheses. The subgradient choice is part of the algorithm: at a corner, different legitimate choices can produce different next iterates. We assume a minimizer of over exists and write . Closedness of alone does not guarantee such a minimizer.
For the quantitative bound, assume that the selected vectors satisfy with a known . Global -Lipschitz continuity is a sufficient condition, but the proof only needs the selected-vector bound. Choose a known with . These are bounds to justify, not quantities automatically returned by the method.
Theorem 5.2.5
(Best-iterate and averaged-point guarantees)
For every integer , put
Then , and both and are at most
In particular, for a horizon fixed in advance and the constant step throughout that run, both gaps are at most .
Proof
(Projection, expansion and telescoping)
Let and . The projection inequality gives
Apply this with and . Expanding the square and then using the subgradient inequality yields
Rearrange and sum from to . The intermediate squared distances cancel. Discarding the final nonnegative squared distance gives
The smallest gap is no larger than the weighted average of these gaps. Also, convexity of makes feasible, and convexity of gives . Thus each requested gap has the stated bound. For the prescribed constant step, and , proving .
Proof X-ray
Telescope distance because objective decrease is unavailable
A subgradient step need not decrease , so the proof never tracks directly; it tracks the squared distance to a fixed minimizer. Projection onto the convex set does not increase the distance to any feasible point, so the constraint costs nothing. The key move is the subgradient inequality at evaluated at : it converts the cross term into the objective gap . The only price is the error term , which is why the bound compares with . Summation cancels the intermediate distances, and the argument closes because the final distance is nonnegative. Convexity is used once more at the end: convexity of makes feasible, and convexity of bounds by the weighted average of the .
Common mistake
(The guarantee is not about the last iterate)
The theorem evaluates ; it does not replace their best value by . Nor does it compare the objective at the average with the best objective: either can be smaller. The bound concerns objective accuracy, not distance to a particular minimizer.
For an arbitrary fixed , the same argument gives . Taking to infinity leaves a positive upper bound; this estimate does not establish exact convergence with a fixed nonzero step. In the horizon-tuned bound, changing changes the chosen step for the run. If , then already minimizes globally and the method can stop; no rate calculation is needed.
Worked example 5.2.6
(Projection onto a Euclidean ball)
Prove the projection formula onto the Euclidean ball , where . Why can this formula not be replaced by independently clipping each coordinate to ?
If , the projection is . Otherwise, for any feasible , the reverse triangle inequality gives , attained by . Projection is unique, so . Coordinate clipping instead projects onto a box: in two dimensions it leaves unchanged, although that point has norm and is outside the ball.
A complete calculation at two kinks
Worked example 5.2.7
(A valid step can leave an exact minimizer)
Minimize over . The sum and scaling rules give slopes for , for , and for . At the corners,
For , ; for , ; for , . These formulas show that the unique minimizer is , with . All subgradients have norm at most .
Use , start at , and make the following admissible choices. Projection onto the interval is clipping; it does not change any trial point in this trace.
| selected | |||
|---|---|---|---|
Every row follows from . The step from the exact minimum to increases the objective. Choosing zero at that minimum would instead keep the point fixed. Both choices are legitimate subgradients.
For a separate run with horizon , starting again from , the known bounds and prescribe . The theorem guarantees best and averaged gaps at most among the specified first 100 evaluation points. That is a worst-case guarantee; the table above uses a different step.
Counterexample mode
A negative subgradient need not be downhill
The claim “if is nonzero, then sufficiently short steps along decrease ” is false. For at , choose . Every gives . Even the exact minimizer admits nonzero subgradients.
A subgradient gives a lower bound on future values. It gives no upper bound along its negative direction. This is why the proof controls accumulated objective gaps through distances instead of assuming stepwise decrease. The optimality test is the existence of the zero subgradient, not the vanishing of every subgradient.
Practice with complete solutions
Quick check
(Find the subdifferential of at . Does have an unconstrained minimum?)
Treat each coordinate separately, then add the affine gradient.
Solution · Answer
At the supporting slopes of form in the first coordinate, and those of form in the second. Adding the affine gradient gives , which excludes zero. This only rules out that particular point as a minimum. To decide the whole problem, take and let tend to : . Hence no unconstrained minimum exists.
Quick check
(For with , prove directly that .)
Bound one affine piece at by its value at .
Solution · Answer
For every , . Taking the maximum over gives . Exchange and for the reverse inequality.
Quick check
(Suppose the projected-subgradient theorem applies with , . Choose a horizon and constant step that guarantee an objective gap at most . State exactly which outputs are covered.)
Solve for .
Solution · Answer
It suffices that , so choose and . The guarantee covers and . It does not assert the same bound for the final update , and the distance and subgradient hypotheses must hold for the actual problem.