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

Proof of `Optimal dual multipliers`

groundedproofs/Lax109476Proofs/Duality.lean · lax-109476

What this proof establishes

Assuming the claims on the left, the claim on the right holds — checked by the archive's pipeline. Proof code is not displayed here.

Read the Lean proof on GitHub

Description

Apply Farkas' lemma to the proposed dual multipliers with the additional constraint bTy≤cTxb^T y\le c^T x. If this system is infeasible, its separating vector consists of a nonnegative vector dd and scalar λ\lambda satisfying Ad≤λbAd\le\lambda b and cTd>λcTxc^T d>\lambda c^T x. For λ>0\lambda>0, the point d/λd/\lambda improves the alleged optimum. For λ=0\lambda=0, the point x+dx+d improves it. Both are contradictions. The system is therefore feasible, and weak duality gives equality.