Attainment of a finite linear-programming optimum
Lax109476.PrimalAttainment · concepts/Lax109476/PrimalAttainment.lean · lax-109476
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
If a real linear program is feasible and its objective is bounded above on the feasible set, it attains its maximum at a feasible point.
Concept map
Evidence
Each proof establishes this claim relative to its assumptions.
Lean source view on GitHub
| 1 | import Lax109476.LinearProgram |
| 2 | |
| 3 | /-! |
| 4 | --- |
| 5 | title: Attainment of a finite linear-programming optimum |
| 6 | type: theorem |
| 7 | --- |
| 8 | If a real linear program is feasible and its objective is bounded above on |
| 9 | the feasible set, it attains its maximum at a feasible point. |
| 10 | |
| 11 | # Formalization notes |
| 12 | |
| 13 | No compactness assumption is imposed on the feasible polyhedron. Linear |
| 14 | objectives attain their finite optima on nonempty polyhedra even when those |
| 15 | polyhedra are unbounded. This is the attainment step used with Farkas' |
| 16 | lemma to obtain an optimal dual certificate. The supplied proof applies Farkas' |
| 17 | lemma to the original system with an objective threshold equal to the finite |
| 18 | supremum; a separating certificate would contradict feasibility or produce |
| 19 | a strictly smaller dual upper bound. |
| 20 | -/ |
| 21 | |
| 22 | namespace Lax109476.PrimalAttainment |
| 23 | |
| 24 | open Lax109476.LinearProgram |
| 25 | |
| 26 | /-- A nonempty polyhedron attains every bounded-above linear objective. -/ |
| 27 | axiom exists_primal_optimizer : |
| 28 | ∀ (m n : ℕ) (P : Program ℝ m n), IsFeasible P → IsBoundedAbove P → |
| 29 | ∃ x : Fin n → ℝ, IsPrimalOptimal P x |
| 30 | |
| 31 | end Lax109476.PrimalAttainment |
| 32 |
Formalization notes
No compactness assumption is imposed on the feasible polyhedron. Linear objectives attain their finite optima on nonempty polyhedra even when those polyhedra are unbounded. This is the attainment step used with Farkas' lemma to obtain an optimal dual certificate. The supplied proof applies Farkas' lemma to the original system with an objective threshold equal to the finite supremum; a separating certificate would contradict feasibility or produce a strictly smaller dual upper bound.
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments