While this submission is a draft, it cannot be used by other submissions.

Attainment of a finite linear-programming optimum

Lax109476.PrimalAttainment · concepts/Lax109476/PrimalAttainment.lean · lax-109476

proven

Loading review…

Sign in with ORCID

Community review

Flags

Each flag is tied to a public ORCID identity and explains why this concept may be incorrect.

No flags have been submitted.

    Community review

    Flag this concept

    State precisely what appears incorrect. This explanation will be public under your ORCID name.

    No source line selected.

    Natural 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
    2 concepts
    100%
    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on A
    Evidence

    Each proof establishes this claim relative to its assumptions.

    Lean source view on GitHub

    1import Lax109476.LinearProgram
    2
    3/-!
    4---
    5title: Attainment of a finite linear-programming optimum
    6type: theorem
    7---
    8If a real linear program is feasible and its objective is bounded above on
    9the feasible set, it attains its maximum at a feasible point.
    10
    11# Formalization notes
    12
    13No compactness assumption is imposed on the feasible polyhedron. Linear
    14objectives attain their finite optima on nonempty polyhedra even when those
    15polyhedra are unbounded. This is the attainment step used with Farkas'
    16lemma to obtain an optimal dual certificate. The supplied proof applies Farkas'
    17lemma to the original system with an objective threshold equal to the finite
    18supremum; a separating certificate would contradict feasibility or produce
    19a strictly smaller dual upper bound.
    20-/
    21
    22namespace Lax109476.PrimalAttainment
    23
    24open Lax109476.LinearProgram
    25
    26/-- A nonempty polyhedron attains every bounded-above linear objective. -/
    27axiom exists_primal_optimizer :
    28 ∀ (m n : ℕ) (P : Program ℝ m n), IsFeasible P → IsBoundedAbove P →
    29 ∃ x : Fin n → ℝ, IsPrimalOptimal P x
    30
    31end Lax109476.PrimalAttainment
    32
    Show Proof
    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.

    Builds on
    Used by

    none

    From Mathlib

    none

    Discussion

    Ask a question or add context. Endorsements and structured flags are kept in the review panel above.

    Loading discussion…