Theorem 10 (Everett) — a minimizer of the Lagrangian solves the problem with budget b′ = g(x⁰(θ))
ProvedServiceParts.StockLevels.everettLet be a set, let and be real functions on , and let . Problem 1 is
and for a multiplier its Lagrangian relaxation, Problem 2, is .
Theorem (Everett). Suppose is an optimal solution of Problem 2 for the multiplier , and let . Then also solves Problem 3,
it is feasible for Problem 3 and for every with .
By varying one obtains optimal solutions of the constrained problem for a family of budgets; if for some , Problem 1 itself is solved.
Formalization Note The book assumes and convex and a vector; the statement here drops both assumptions (a labelled generalization: the proof uses neither, and the book applies the theorem to integer stock vectors, where convexity in the vector-space sense is not defined). The conclusion is stated as: is the least value of on .
import Mathlib
namespace ServiceParts.StockLevels
theorem everett {X : Type*} (S : Set X) (f g : X → ℝ) (b θ : ℝ) (hθ : 0 ≤ θ)
(x0 : X) (hx0 : x0 ∈ S)
(hopt : ∀ x ∈ S, f x0 + θ * (g x0 - b) ≤ f x + θ * (g x - b)) :
IsLeast (f '' {x | x ∈ S ∧ g x ≤ g x0}) (f x0) := by sorry
end ServiceParts.StockLevels
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.