Lemma 4.1 โ ๐ข1 and ๐ข2 with ฮป > 0 certify that no exact solution exists
ProvedFracPackCover.General.lemma_4_1dualitylagrangean-relaxationp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a real matrix, , with , and convex. Let with , let with and , and let attain . If
then there is no exact solution: no satisfies .
This is the certificate that lets the algorithm stop with "infeasible": a pair of primal and dual solutions satisfying the relaxed optimality conditions with positive .
Formalization Note. is represented by a point attaining the minimum, and the conclusion is stated as the nonexistence of with for all .
Preamble
import Mathlib import Definitions.Def_FracPackCover_General_Basic
Formal statement
namespace FracPackCover.General
/-- Lemma 4.1 (p. 25). If `x โ P` with `ฮป = ฮป(x) > 0`, a dual vector `y โฅ 0`, `y โ 0`, and
`xฬ โ P` attaining `C_๐ข(y) = min_{x' โ P} y^t(Ax' โ b)` satisfy (๐ข1) and (๐ข2), then no `x' โ P`
has `Ax' โค b`. -/
theorem lemma_4_1 {m n : โ} [NeZero m] (A : Matrix (Fin m) (Fin n) โ) (b d : Fin m โ โ)
(P : Set (Fin n โ โ)) (hP : Convex โ P) (hd : โ i, 0 < d i)
(x : Fin n โ โ) (hx : x โ P) (y : Fin m โ โ) (hy : 0 โค y) (hy0 : y โ 0)
(xt : Fin n โ โ) (hxt : xt โ P) (hmin : โ x' โ P, lagr A b y xt โค lagr A b y x')
(hG1 : G1 A b d x (lam A b d x) y)
(hG2 : G2 A b d x (lam A b d x) y (lagr A b y xt))
(hlam : 0 < lam A b d x) :
ยฌ โ x' โ P, โ i, FracPackCover.Covering.rowVal A x' i โค b i := by sorry
end FracPackCover.General
Source
Plotkin, Shmoys, Tardos, Fast Approximation Algorithms for Fractional Packing and Covering Problems, Cornell ORIE Tech. Rep. 999 (1992), p. 25, Lemma 4.1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.