The maximum of a convex function #
Maximising a convex function behaves nothing like minimising one. The maximum principle says
that a maximiser in the relative interior of C forces f to be constant on C, so maxima live
on the boundary: on faces, and ultimately on extreme points. Taking a convex hull raises neither
the supremum nor the maximiser set, so the supremum over a closed convex set is already carried by
its relative boundary and — when C contains no lines and f is bounded above on each half-line
of C — by the extreme points of C. That boundedness is what makes the extreme directions
invisible: f x = x on C = [0, ∞) has supremum ⊤ over C and 0 over the one extreme point,
and ConvexFn.iSup_extremePoints_add_coneHull is the unconditional statement keeping them.
Main definitions #
BddAboveOnRays f C—fis bounded above on every half-line ofC. The direction0makes this includeC ⊆ dom f, so it carries both standing hypotheses of the extreme point principle.
Main results #
ConvexFn.eq_of_isMaxOn_mem_relint— the maximum principle (Theorem 32.1 in [^1]), withexists_isFace_forall_eq_of_isMaxOnfor the face it forces;ConvexFn.iSup_convexHull,exists_eq_of_isMaxOn_convexHull— the convex hull raises neither the supremum nor the maximiser set;ConvexFn.iSup_sdiff_relint,exists_notMem_relint_eq_of_isMaxOn— the relative boundary carries both.ConvexFn.iSup_extremePoints_of_containsNoLine,ConvexFn.iSup_extremePoints_inter_of_isCompl,ConvexFn.iSup_extremePoints_add_coneHull— the extreme point principle (Theorem 32.3 in [^1]): for a line-freeC, for a generalCcut down by a complement of its lineality space, and in representation form.exists_isMaxOn_of_polyhedral_of_bddAboveOnRays,exists_mem_extremePoints_isMaxOn_of_finitelyGenerated— attainment over a polyhedral and over a finitely generated set;ConvexFn.iSup_extremePoints,exists_mem_extremePoints_isMaxOn_of_isCompact— the compact case.mem_normalCone_of_mem_subgradient_of_isMaxOn— at a maximiser, every subgradient is normal.
Implementation notes #
Maximisation is spelled ∀ z ∈ C, f z ≤ f x rather than IsMaxOn, the form every proof consumes;
isMaxOn_iff bridges. The lineality space L of C is quotiented out by intersecting with a
complement N rather than by passing to E ⧸ L: C = L + (C ∩ N) holds for any N, so no
inner product is needed where the book takes N = L⊥.
References #
[^1]: R. T. Rockafellar, Convex Analysis, Princeton University Press, 1970, §32.
The maximum principle #
The maximum principle: a convex function attaining its supremum over a convex C ⊆ dom f
at a relative interior point of C is constant on C.
Every maximiser lies in a face of C on which f is constant, so the maximiser set is a union
of faces: the maximum principle applied on the face whose relative interior contains it.
Passing to the convex hull #
Taking the convex hull does not raise the supremum of a convex function: the sublevel set at
the supremum over S is convex and contains S, hence contains conv S.
The convex hull creates no new maximisers either, because the strict sublevel set is convex too.
The supremum over the relative boundary #
A closed convex set that is neither an affine set nor a closed half of one is the convex hull of its relative boundary.
The supremum over a closed convex set is already its supremum over the relative boundary. The
hypothesis — C neither an affine set nor a closed half of one — cannot be dropped: over [0, ∞)
the relative boundary is {0}, yet f x = x has supremum ⊤.
Attainment: a maximiser can be replaced by one on the relative boundary.
The relative-boundary supremum under a hypothesis easier to check: a closed convex set of dimension at least two containing no lines is neither affine nor a closed half of an affine set.
The extreme point principle #
A convex function bounded above on a half-line does not increase along it: if
f (u + t • v) ≤ β for every t ≥ 0 then f (u + v) ≤ f u.
Bounded above on C implies non-increasing along a direction of recession of C — the
analytic core of the extreme point principle.
f is bounded above on every half-line of C: for every u and v with u + t • v ∈ C
for all t ≥ 0, some real β bounds f there. The direction v = 0 makes it say C ⊆ dom f as
well, so this one predicate carries both standing hypotheses of the extreme point principle.
Equations
Instances For
The degenerate half-lines — the points — of C already force C ⊆ dom f.
The previous bound weakened to the one half-line the proof actually uses.
Bounded above on the half-lines of C implies constant along the lineality space of C:
the two opposite directions of recession give inequalities that close on each other.
Reduction of C to C ∩ N at the level of values: for any complement N of the lineality
space of C, every point of C carries the same value of f as some point of C ∩ N. The
decomposition C = L + (C ∩ N) is algebraic: no closedness, no finite dimension.
A convex function bounded above on the whole space is constant — the unbounded companion of
the maximum principle, where the absence of any boundary replaces ri C.
Every point of C is dominated by a point of conv (ext C), for f bounded above on the
half-lines of a closed convex line-free C; the representation of C splits x as u + v.
The extreme point principle for L = 0: the supremum of a convex function over a closed
convex C with no lines, bounded above on every half-line of C, is its supremum over ext C.
BddAboveOnRays is genuinely weaker than a uniform bound: f (ξ₁, ξ₂) = ξ₁ on
C = {(ξ₁, ξ₂) | ξ₁² ≤ ξ₂} is bounded on each half-line and unbounded on C.
A supremum over a closed convex line-free set, if attained at all, is attained at an extreme
point. No boundedness hypothesis is needed, but f x ≠ ⊤ is: on [0, ∞) with f = 0 on [0, 1)
and ⊤ beyond, ⊤ is a maximum yet the extreme point carries 0.
The extreme point principle in representation form, with no boundedness hypothesis: the supremum over a closed convex line-free set is the supremum over the sums of an extreme point and a non-negative combination of extreme directions.
The lineality space quotiented out #
The extreme point principle in full: for any complement N of the lineality space of a
closed convex C, the supremum of a convex function bounded above on the half-lines of C is its
supremum over the extreme points of C ∩ N. The book takes N = L⊥; every complement works.
Attainment for an arbitrary complement N of the lineality space: a maximiser over C can be
replaced by an extreme point of C ∩ N.
Finitely generated sets #
The extreme point principle for a finitely generated set: bounded above on every half-line
of a nonempty finitely generated line-free convex set, f attains its supremum at an extreme
point — of which there are only finitely many.
A convex function bounded above on a nonempty polyhedral convex set containing no lines attains its supremum at one of its finitely many extreme points.
A convex function bounded above on every half-line of a nonempty polyhedral convex C ⊆ dom f
attains its supremum relative to C. Unlike the previous result this asks nothing about lines in
C, and claims nothing about extreme points of C — a set containing a line has none. The
maximiser is an extreme point of C ∩ N and depends on the complement N chosen, hence the bare
attainment conclusion.
The extreme point principle, compact case #
For compact C the supremum over the set is its supremum over the extreme points:
Minkowski's theorem fed to the convex hull identity.
A maximiser over a compact convex set is matched by an extreme point.
The "supremum is attained" clause: a convex function attains its supremum over a nonempty
compact convex C ⊆ ri (dom f) at an extreme point. The hypothesis is C ⊆ ri (dom f), not the
book's C ⊆ dom f, under which the clause is false.
Subgradients at a maximiser #
At a point where f attains its supremum over C, every subgradient of f is normal to C.
All that is needed is that f x be real.
Non-vanishing clause: if f is not constant on C, no subgradient at a maximiser can be
zero.
A vector normal to C at x is one whose linear functional attains its supremum over C
at x.