Rockafellar, §20: Some Applications of Polyhedral Convexity #
The separation theorems, closure conditions and conjugacy formulas of Parts II and III, refined by assuming some of the convexity polyhedral.
All eight numbered results of §20 are formalized over Rn n = ℝⁿ: Theorems 20.1–20.5 and
Corollaries 20.1.1, 20.2.1, 20.3.1, together with the unnumbered all-polyhedral computation of the
opening paragraph (theorem_20_1_pair_exact).
The asymmetry of Theorem 20.1 #
Theorem 16.4 makes (f₁ + ⋯ + fₘ)* = f₁* □ ⋯ □ fₘ* exact when the sets ri (dom fᵢ) have a common
point. Theorem 20.1 says that for a polyhedral summand the relative interior may be dropped: only
dom fᵢ need take part in the intersection, and when every summand is polyhedral no relative
interior appears at all. The asymmetry comes from two segment lemmas: a proper polyhedral function
is already closed, so Corollary 7.5.1 asks only for a point of dom f, whereas Theorem 7.5 asks
for a point of ri (dom g).
IsExactSum and IsExactFinsetSum are the backbone's names for the conclusion Theorems 16.4 and
20.1 share; the m-ary statements are proved for the family, not by induction on the binary ones,
and the index set is split membership-wise so that no DecidableEq instance enters a statement.
IsPolyhedral is Rockafellar's §19 definition quantified over vectors bᵢ, bridged to the
backbone's functional-indexed Polyhedral by isPolyhedral_iff_polyhedral; a polyhedral convex
function is the backbone's PolyhedralFn directly.
References #
- R. T. Rockafellar, Convex Analysis, Princeton University Press, 1970, §20.
Polyhedral convex sets, in the book's own words #
§19 (p. 170). A polyhedral convex set in ℝⁿ is an intersection of finitely many
closed half-spaces {x | ⟨x, bᵢ⟩ ≤ βᵢ}. Nothing below unfolds the definition.
Equations
- Rockafellar.IsPolyhedral C = ∃ (s : Finset (TdafSurface.Rn n × ℝ)), C = {x : TdafSurface.Rn n | ∀ q ∈ s, ((TdafSurface.pairing n) x) q.1 ≤ q.2}
Instances For
Rockafellar's vector-indexed system of half-spaces and the backbone's functional-indexed one
describe the same sets, linFn and exists_linFn being the round trip.
Separation that does not swallow the second set #
§20 (p. 181). There exists a hyperplane separating C₁ and C₂ properly and not
containing C₂. The side convention is §11's: C₁ lies in the closed half-space
{x | ⟨x, b⟩ ≥ β} and C₂ in the opposite one.
Equations
- Rockafellar.SeparableProperlyNotContaining C₁ C₂ = ∃ (b : TdafSurface.Rn n) (β : ℝ), Rockafellar.SeparatesProperlyRn b β C₁ C₂ ∧ ¬C₂ ⊆ {x : TdafSurface.Rn n | ((TdafSurface.pairing n) x) b = β}
Instances For
The bridge from SeparableProperlyNotContaining to the backbone's functional form.
Theorem 20.1 and its corollary #
§20 (p. 179), the all-polyhedral case: if f and g are proper polyhedral convex
functions whose effective domains meet at all, then (f + g)* = f* □ g*. No relative interior
appears in the hypothesis. Rockafellar gives this unnumbered, as the computation motivating
Theorem 20.1.
§20 (p. 179), the all-polyhedral case, attainment: the infimum defining (f* □ g*)(x*) is
attained for every x*.
Theorem 20.1. For f and g proper convex with f polyhedral and
dom f ∩ ri (dom g) ≠ ∅,
(f + g)*(x*) = (f* □ g*)(x*) = inf {f*(x₁*) + g*(x₂*) | x₁* + x₂* = x*}.
The asymmetry is the point: the polyhedral summand contributes only a point of dom f, the
other a point of ri (dom g). Compare theorem_16_4_exact, which asks for a point of
ri (dom f) ∩ ri (dom g), and theorem_20_1_pair_exact, which asks for neither.
Theorem 20.1, the attainment clause: under the same qualification the infimum
inf {f*(x₁*) + g*(x₂*) | x₁* + x₂* = x*} is attained for each x*.
Corollary 20.1.1. For f and g closed proper convex with f polyhedral and
dom f* ∩ ri (dom g*) ≠ ∅, the infimal convolute f □ g is a closed proper convex function.
Rockafellar's proof verbatim: apply Theorem 20.1 to the conjugates, f* being polyhedral by
Theorem 19.2, and read back through Theorem 12.2.
Corollary 20.1.1, the attainment clause: the infimum defining (f □ g)(x) is attained for
every x.
Theorem 20.1 in the book's m-ary form. Let f₁, …, fₘ be proper convex with
f₁, …, f_k polyhedral, and suppose
dom f₁ ∩ ⋯ ∩ dom f_k ∩ ri (dom f_{k+1}) ∩ ⋯ ∩ ri (dom fₘ)
is non-empty. Then (f₁ + ⋯ + fₘ)* = f₁* □ ⋯ □ fₘ*. Here t is the book's {1, …, k} and u its
complement. Compare theorem_16_4_exact_finset, which asks for a relative interior point on every
index.
Theorem 20.1, the attainment clause for m summands:
inf {f₁*(x₁*) + ⋯ + fₘ*(xₘ*) | x₁* + ⋯ + xₘ* = x*} is attained for each x*.
Corollary 20.1.1 in the book's m-ary form. Let f₁, …, fₘ be closed proper convex with
f₁, …, f_k polyhedral, and suppose
dom f₁* ∩ ⋯ ∩ dom f_k* ∩ ri (dom f_{k+1}*) ∩ ⋯ ∩ ri (dom fₘ*)
is non-empty. Then f₁ □ ⋯ □ fₘ is a closed proper convex function.
Corollary 20.1.1, the attainment clause: the infimum defining (f₁ □ ⋯ □ fₘ)(x) is
attained for every x.
Theorem 20.2 and its corollary #
Theorem 20.2. For non-empty convex C₁, C₂ with C₁ polyhedral, a hyperplane separating
C₁ and C₂ properly and not containing C₂ exists iff C₁ ∩ ri C₂ = ∅. Compare Theorem 11.3,
which asks ri C₁ ∩ ri C₂ = ∅ and promises nothing about containment: polyhedrality of C₁ buys
both improvements at once. Convexity of C₁ follows from polyhedrality and is not assumed.
Corollary 20.2.1. For non-empty convex C₁, C₂ with C₁ polyhedral, C₁ ∩ ri C₂ is
non-empty iff every x* with δ*(x* | C₁) ≤ -δ*(-x* | C₂) satisfies
δ*(x* | C₁) = δ*(x* | C₂). The hypothesis on x* says some hyperplane orthogonal to x*
separates the two sets; the conclusion says every such hyperplane contains C₂.
Theorem 20.3 and its corollary #
Theorem 20.3. Let C₁ be polyhedral and C₂ closed, both non-empty convex, and suppose
every direction of recession of C₁ whose opposite recedes in C₂ is a direction in which C₂ is
linear. Then C₁ + C₂ is closed. "Linear in the direction v" is v ∈ 0⁺C₂ given -v ∈ 0⁺C₂.
Compare Corollary 9.1.1, which asks in addition that such a v lie in the lineality space of
C₁.
Corollary 20.3.1. Disjoint non-empty convex C₁ polyhedral and C₂ closed can be
separated strongly, provided their only common directions of recession are ones in which C₂ is
linear. Compare Corollary 11.4.1, which forbids common recession directions outright, and
Corollary 19.3.3, where both sets are polyhedral and no recession hypothesis is needed.
Theorems 20.4 and 20.5 #
Theorem 20.4. For C closed and bounded and D convex with C ⊆ int D, there is a
polyhedral convex P with P ⊆ int D and C ⊆ int P.
Rockafellar also assumes C non-empty and convex; neither hypothesis is used. The argument is
a finite subcover of C by polyhedral neighbourhoods and never combines two points of C
convexly.
Theorem 20.5. Every polyhedral convex set is locally simplicial. The book's proof is a
two-line sketch which asserts the triangulation of a bounded polyhedron; the proof here produces
the simplices explicitly, as the convex hulls of the affinely independent subsets of a generating
Finset.
Theorem 20.5, second clause: every polytope is locally simplicial.