Rockafellar, §21: Helly's Theorem and Systems of Inequalities #
Existence theorems for systems of convex inequalities, stated as pairs of mutually exclusive alternatives, and the four forms of Helly's theorem that come out of them.
All ten numbered results of §21 are formalized over Rn n = ℝⁿ: Theorems 21.1–21.6 and
Corollaries 21.3.1, 21.3.2, 21.6.1, 21.6.2, together with the unnumbered exercise after Corollary
21.3.2 (helly_recession_iff_exists_isBounded). Theorems 21.1, 21.2 and 21.3 read "one and only
one of the following alternatives holds": theorem_21_k is the disjunction, the half with content,
and theorem_21_k_exclusive says the alternatives cannot both hold.
A system of convex inequalities is fᵢ(x) ≤ αᵢ for i ∈ I₁ together with fᵢ(x) < αᵢ for
i ∈ I₂, with arbitrary index sets and -∞ ≤ αᵢ ≤ +∞. That data is ConvexSystem, its solution
set ConvexSystem.solutions, and the book's "consistent" ConvexSystem.Consistent. Every numbered
theorem is stated with right-hand sides 0, which solutions_normalize justifies.
Two hypotheses look like slips and are not. Theorem 21.1 asks dom fᵢ ⊇ ri C, not
dom fᵢ ⊇ C: separation produces the inequality only where every fᵢ is finite, and Corollary
7.3.3 carries it from ri C to cl C ⊇ C. Alternative (b) is read in EReal, where
0 · (+∞) = 0; without that convention a vanishing multiplier could not drop a constraint whose
fᵢ is +∞ somewhere, and Corollary 21.6.2, which extends a short multiplier vector by zeros,
would be false as stated. No 0⁺ bookkeeping appears in this section.
The "Corollary 21.3.3" cited in the book's Comments and References for Part IV does not exist; the intended reference is Corollary 21.3.2, Helly's theorem.
References #
- R. T. Rockafellar, Convex Analysis, Princeton University Press, 1970, §21.
A system of convex inequalities #
Rockafellar's system of convex inequalities in ℝⁿ: fᵢ(x) ≤ αᵢ for i ∈ I₁ together
with fᵢ(x) < αᵢ for i ∈ I₂, with I₁, I₂ arbitrary and -∞ ≤ αᵢ ≤ +∞. Convexity of the fᵢ
is not a field: the book's own statements about the solution set carry it as a hypothesis.
- weakFn : ι → TdafSurface.Rn n → EReal
The functions of the weak part,
fᵢ(x) ≤ αᵢfori ∈ I₁. - weakBound : ι → EReal
The right-hand sides
αᵢof the weak part, allowed to be±∞. - strictFn : κ → TdafSurface.Rn n → EReal
The functions of the strict part,
fᵢ(x) < αᵢfori ∈ I₂. - strictBound : κ → EReal
The right-hand sides
αᵢof the strict part, allowed to be±∞.
Instances For
The set of solutions x of a system of convex inequalities.
Equations
Instances For
The book's consistent: the system has at least one solution.
Equations
- S.Consistent = S.solutions.Nonempty
Instances For
§21 (p. 185). The solution set is the intersection of the level sets of the constraints.
§21 (p. 185). The solution set of a system of convex inequalities is convex.
A level set {x | f x ≤ α} of a closed function is closed, for an extended-real level α;
lowerSemicontinuous_iff_isClosed_le covers only the finite levels.
§21 (p. 185). With no strict inequalities and every fᵢ closed, the solution set is
closed.
§21 (p. 186). For a finite right-hand side α, f(x) ≤ α is g(x) ≤ 0 for g = f - α,
and likewise for the strict form. This is why every numbered theorem takes right-hand sides 0.
§21 (p. 186). A linear equation enters a system of convex inequalities as a pair of
inequalities: ⟨x, b⟩ = β is ⟨x, b⟩ ≤ β and ⟨x, -b⟩ ≤ -β.
Theorem 21.1 #
Theorem 21.1. For C convex and f₁, …, f_m proper convex with dom fᵢ ⊇ ri C, one and
only one of the following holds:
(a) f₁(x) < 0, …, f_m(x) < 0 for some x ∈ C;
(b) λ₁f₁(x) + ⋯ + λ_mf_m(x) ≥ 0 for every x ∈ C, for some λᵢ ≥ 0 not all zero.
This is the disjunction; theorem_21_1_exclusive is the exclusivity. The hypothesis is ri C and
not C, and the weighted sum is read in EReal, where 0 · (+∞) = 0.
Theorem 21.1, the "only one" half: (a) and (b) cannot both hold. Nothing is assumed about
the fᵢ or C — at a point where every fᵢ is negative, every term λᵢfᵢ(x) is non-positive and
those with λᵢ ≠ 0 are strictly negative.
Theorem 21.2 #
Theorem 21.2. For C convex, f₁, …, f_k proper convex with dom fᵢ ⊇ ri C, and
f_{k+1}, …, f_m affine with f_{k+1}(x) ≤ 0, …, f_m(x) ≤ 0 solvable in ri C, one and only one
of the following holds:
(a) x ∈ C with f₁(x) < 0, …, f_k(x) < 0 and f_{k+1}(x) ≤ 0, …, f_m(x) ≤ 0;
(b) non-negative λ₁, …, λ_m, at least one of λ₁, …, λ_k non-zero, with
λ₁f₁(x) + ⋯ + λ_mf_m(x) ≥ 0 for every x ∈ C.
The convex constraints are indexed by ι and the affine ones by κ, the latter as Rn n →ᵃ[ℝ] ℝ.
Theorem 21.1 is the case κ = Empty but is not derived from this one: 21.1 needs only Theorem
11.3, while 21.2 needs the polyhedral separation of Theorem 20.2.
Theorem 21.2, the "only one" half: at a point of C solving the mixed system the convex
part of the weighted sum is strictly negative and the affine part is non-positive.
Theorem 21.3 and its corollaries #
Theorem 21.3. Let {fᵢ | i ∈ I} be closed proper convex functions on ℝⁿ, I arbitrary,
and C a non-empty closed convex set; assume the fᵢ have no common direction of recession which
also recedes in C. Then one and only one of the following holds:
(a) x ∈ C with fᵢ(x) ≤ 0 for every i ∈ I;
(b) non-negative λᵢ, finitely many non-zero, and ε > 0 with ∑ᵢ λᵢfᵢ(x) ≥ ε for every x ∈ C.
In case (b) at most n + 1 of the λᵢ need be non-zero, which is the t.card ≤ n + 1 clause.
Theorem 21.3, the "only one" half: at a solution of the weak system every term λᵢfᵢ(x) is
non-positive, so the sum cannot be bounded below by a positive ε.
Corollary 21.3.1. Under the recession hypothesis of Theorem 21.3, existence for an
infinite system reduces to existence for its finite subsystems: if for every ε > 0 and every set
of at most n + 1 indices the system f_{i₁}(x) < ε, …, f_{i_m}(x) < ε is solvable in C, then
fᵢ(x) ≤ 0 for all i ∈ I is solvable in C.
Corollary 21.3.2 (Helly's Theorem). Let {Cᵢ | i ∈ I} be non-empty closed convex sets in
ℝⁿ, I arbitrary, with no common direction of recession. If every subcollection of n + 1 or
fewer sets has non-empty intersection, so does the whole collection. The recession hypothesis
cannot be dropped. Compare theorem_21_6, where the collection is finite and neither closedness
nor a recession hypothesis is needed.
§21, the unnumbered exercise after Corollary 21.3.2: assuming every finite subcollection
has a non-empty intersection, the recession hypothesis of Helly's theorem holds if and only if some
finite subcollection has a bounded intersection. Taking S = {i} recovers the sentence before it,
that the hypothesis holds as soon as one Cᵢ is bounded.
Theorems 21.4 and 21.5: the polyhedral refinements #
The book's "fᵢ is an affine function", for a function EReal-valued on all of ℝⁿ:
f(x) = ⟨x, b⟩ - β.
Equations
- Rockafellar.IsAffineFn f = ∃ (b : TdafSurface.Rn n) (β : ℝ), ∀ (x : TdafSurface.Rn n), f x = ↑(inner ℝ x b - β)
Instances For
An affine function of ℝⁿ in the book's sense is exactly an affineFn of the pairing.
Theorem 21.4. When C = ℝⁿ, the recession hypothesis of Theorem 21.3 and Corollary 21.3.1
may be weakened to: there is a finite I₀ ⊆ I with fᵢ affine for i ∈ I₀, such that every
direction of recession common to all the fᵢ is a direction in which fᵢ is constant for each
i ∈ I \ I₀. "Direction in which fᵢ is constant" is constancySpace (f i); theorem_21_3 is
the case I₀ = ∅, since 0 lies in every constancy space.
Theorem 21.4 for Corollary 21.3.1: under the affine-tail hypothesis, an infinite system of
weak convex inequalities on ℝⁿ is solvable as soon as every subsystem of at most n + 1 of the
inequalities is solvable to within an arbitrarily small tolerance.
Theorem 21.5. The recession hypothesis in Helly's theorem may be weakened to: there is a
finite I₀ ⊆ I with Cᵢ polyhedral for i ∈ I₀, such that every direction of recession common to
all the Cᵢ is a direction in which Cᵢ is linear for each i ∈ I \ I₀. "Direction in which Cᵢ
is linear" is linealitySpace (K i).
Theorem 21.6 and its corollaries: finite collections #
Theorem 21.6. For a finite collection of convex sets in ℝⁿ, not necessarily closed, if
every subcollection of n + 1 or fewer sets has non-empty intersection then so does the whole
collection. Rockafellar derives this from Corollary 21.3.2; the proof here goes through Radon's
theorem instead, so Corollaries 21.6.1 and 21.6.2 do not depend on Theorem 21.3.
Corollary 21.6.1. For a system f₁(x) < 0, …, f_k(x) < 0, f_{k+1}(x) ≤ 0, …, f_m(x) ≤ 0
with every fᵢ convex on ℝⁿ: if every subsystem of n + 1 or fewer inequalities has a solution
in a convex set C, the whole system has one in C. The book's 1, …, k is the index type ι
and its k+1, …, m is κ, so "n + 1 or fewer inequalities" is S.card + T.card ≤ n + 1.
Corollary 21.6.2. If alternative (b) of Theorem 21.1 holds, the λᵢ may be chosen with at
most n + 1 of them non-zero. The sparsity is stated as a Finset S of size at most n + 1
outside which every λᵢ vanishes, which avoids deciding λᵢ ≠ 0; extending a short multiplier
vector by zeros is harmless precisely because 0 · (+∞) = 0 in EReal. The book states this for
Theorem 21.2 as well — that half is corollary_21_6_2_affine.
A real affine function of ℝⁿ, read into EReal, is convex. This is what lets the affine
constraints of Theorem 21.2 enter Corollary 21.6.1's collection of convex sets.
Corollary 21.6.2 for Theorem 21.2: if alternative (b) holds there, at most n + 1 of
λ₁, …, λ_m need be non-zero, the count running over the affine multipliers as well as the convex
ones, since the book's λ₁, …, λ_m is one list. The book's proof, verbatim: if (a) fails it
already fails for a subsystem of at most n + 1 inequalities, and Theorem 21.2 applied to that
subsystem produces multipliers which extend by zero.