Exercise 10.7 — interior solutions: a bounded feasible primal has a strictly positive dual feasible point
ProvedVanderbeiLP.CentralPath.dual_strictly_feasible_of_boundedLet be a real matrix, and , and consider the linear program "maximize subject to , " with its dual "minimize subject to , ". If the primal has feasible solutions and its set of feasible solutions
is bounded, then there is a strictly positive dual feasible solution: vectors and with
Corollary 17.3 derives existence of the central path from Theorem 17.2 and this statement: a bounded primal with nonempty interior supplies both interiors that Theorem 17.2 asks for.
Formalization Note "Bounded" is Bornology.IsBounded of the primal feasible set in (equivalently, of the region of pairs , since ). The feasibility hypothesis is needed: an empty feasible set is bounded, and for , , no dual point with exists. The objective is arbitrary.
import Mathlib import Definitions.Def_VanderbeiLP_CentralPath_BarrierProblem open Matrix Filter Topology
namespace VanderbeiLP.CentralPath
/-- Exercise 10.7 (p. 150). If the LP `maximize cᵀx s.t. Ax ≤ b, x ≥ 0` has feasible solutions and
its set of feasible solutions is bounded, then there is a strictly positive dual feasible solution:
`Aᵀy − z = c` with `y > 0` and `z > 0`. -/
theorem dual_strictly_feasible_of_bounded {m n : ℕ} (A : Matrix (Fin m) (Fin n) ℝ)
(b : Fin m → ℝ) (c : Fin n → ℝ) (hne : (primalFeasibleSet A b).Nonempty)
(hbdd : Bornology.IsBounded (primalFeasibleSet A b)) :
DualStrictlyFeasible A c := by sorry
end VanderbeiLP.CentralPath
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.