Theorem 6.5 — Lagrangian and convexified decomposition bounds
DisprovedPochetWolsey.Decomposition.lagrangian_convexified_boundLet be rational data defining . Let be real and set and . Assume is nonempty and is bounded below on . Let be a tight finite formulation with real data. Define
The full column master ranges over all finite convex combinations of points of plus nonnegative combinations of nonzero recession directions , , subject to . Let be its infimum. Under the preceding section's literal maximum convention, put . The assertion is
There exist a minimizing represented in the full master, a maximizing nonnegative multiplier , and a point minimizing the Lagrangian at . The LP supremum is also asserted to be attained. The convexified optimizer is not required to lie in .
This identifies the common convexification bound claimed for Lagrangian relaxation, the full column master, and tight reformulation.
Formalization Note The faithful goal retains the maximum definition of the LP bound from p. 198, to which p. 201 explicitly refers. That inherited clause is false (F3); the separately labeled correction uses a minimum. Rationality of makes explicit the rational integer-program convention underlying polyhedrality of the integer hull; remain real. Extended-real infima handle unbounded subproblems without assigning them zero; all finite optimum and multiplier attainments are explicit. The master includes arbitrary recession rays, hence also extreme rays, and permits an empty ray family for bounded cases.
import Mathlib
namespace PochetWolsey.Decomposition
theorem lagrangian_convexified_bound {n m q t : ℕ}
(A : Matrix (Fin m) (Fin n) ℚ) (b : Fin m → ℚ)
(D : Matrix (Fin q) (Fin n) ℝ) (d : Fin q → ℝ)
(c : Fin n → ℝ)
(B : Matrix (Fin t) (Fin n) ℝ) (e : Fin t → ℝ) :
let Y : Set (Fin n → ℝ) := {x | (∀ j, 0 ≤ x j) ∧
(∀ i, (b i : ℝ) ≤ ∑ j, (A i j : ℝ) * x j) ∧
(∀ j, ∃ z : ℤ, x j = (z : ℝ))}
let PZ : Set (Fin n → ℝ) := {x | (∀ j, 0 ≤ x j) ∧
∀ i, d i ≤ ∑ j, D i j * x j}
let H := convexHull ℝ Y ∩ PZ
let PYtight : Set (Fin n → ℝ) := {x | (∀ j, 0 ≤ x j) ∧
∀ i, e i ≤ ∑ j, B i j * x j}
let cost : (Fin n → ℝ) → ℝ := fun x => ∑ j, c j * x j
let lag : (Fin q → ℝ) → (Fin n → ℝ) → ℝ := fun π x =>
cost x + ∑ i, π i * (d i - ∑ j, D i j * x j)
let L : (Fin q → ℝ) → EReal := fun π =>
sInf ((fun x => (lag π x : EReal)) '' Y)
let master : Set (Fin n → ℝ) := {x | x ∈ PZ ∧
∃ (k r : ℕ) (v : Fin k → (Fin n → ℝ))
(u : Fin r → (Fin n → ℝ)) (lam : Fin k → ℝ) (μ : Fin r → ℝ),
(∀ a, v a ∈ Y) ∧
(∀ a, u a ≠ 0 ∧ (∀ j, 0 ≤ u a j) ∧
∀ i, 0 ≤ ∑ j, (A i j : ℝ) * u a j) ∧
(∀ a, 0 ≤ lam a) ∧ (∑ a, lam a) = 1 ∧ (∀ a, 0 ≤ μ a) ∧
x = (fun j => (∑ a, lam a * v a j) + ∑ a, μ a * u a j)}
let w : EReal := sInf ((fun x => (cost x : EReal)) '' H)
let zLP : EReal := sSup ((fun x => (cost x : EReal)) '' (PYtight ∩ PZ))
PYtight = convexHull ℝ Y → H.Nonempty → BddBelow (cost '' H) →
∃ (xstar ystar : Fin n → ℝ) (πstar : Fin q → ℝ),
xstar ∈ H ∧ (∀ x ∈ H, cost xstar ≤ cost x) ∧
(∀ i, 0 ≤ πstar i) ∧ ystar ∈ Y ∧
(∀ y ∈ Y, lag πstar ystar ≤ lag πstar y) ∧
w = (cost xstar : EReal) ∧
w = L πstar ∧ (∀ π : Fin q → ℝ, (∀ i, 0 ≤ π i) → L π ≤ L πstar) ∧
w = zLP ∧ w = sInf ((fun x => (cost x : EReal)) '' master) ∧
xstar ∈ master ∧
∃ xmax ∈ PYtight ∩ PZ, (∀ x ∈ PYtight ∩ PZ, cost x ≤ cost xmax) ∧
zLP = (cost xmax : EReal) := by sorry
end PochetWolsey.Decomposition
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Fix natural numbers and the following data:
- a rational matrix and a rational vector , both used only after casting their entries to real numbers;
- a real matrix and ;
- a real cost vector ;
- a real matrix and .
All points below live in . The statement defines these sets and functions:
the nonnegative integer points satisfying ;
where is the convex hull in ;
The following quantities take values in the extended reals :
Note that is a supremum, not an infimum.
Finally, ("master") is the set of for which there exist:
- natural numbers ;
- points ;
- vectors , each nonzero, each componentwise nonnegative, and each with ;
- weights with , and ;
such that
Hypotheses. Assume three things:
- (as sets);
- is nonempty;
- the real-valued set is bounded below.
Conclusion. There exist and such that all of the following hold:
- and for every ;
- for all ;
- and for every ;
- and ;
- for every with ;
- ;
- (extended-real infimum) and ;
- there is with for all , and .
No relation between and is asserted. Under hypothesis 1, . The conclusion therefore asserts that the infimum and the supremum of over the same set coincide and are finite; that is, is constant on . The conclusion likewise asserts a cost-maximizer on .
Degenerate cases.
- empty. If (for instance, some when , or has no nonnegative integer solution), then . So , hypothesis 2 fails, and the statement is vacuous.
- . Here is a single point, all sums over are , and is that point exactly when every . No nonzero exists, so forces .
- . is all of , and the ray condition is empty.
- . is the nonnegative orthant, , and ranges over the single empty vector, so .
- . is the nonnegative orthant, so hypothesis 1 demands .
- and in . In , is forced by , while is allowed.
- Extended-real conventions. In the extended reals, if is empty and if is unbounded below on . Also, if is unbounded above on , and if that set is empty. The conclusions , however, assert that all of these values are the same finite real number.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.