§§5–6, pp. 141–143 — ranked least absolute deviations equal a linear program
ProvedExecCompLP.LAD.lp_equivalenceFor arbitrary real factor ratings , nonnegative-weight salary constraints (2), specified levels , and targets , compare minimizing with the transformed linear program minimizing subject to (2), , and for . The two problems have the same attainable objective thresholds:
Moreover, minimizes if and only if minimizes , where ; and every LP minimizer projects to a minimizer of .
This states both the agreement of optimal values and the correspondence of optimal solutions claimed in §§5–6.
Formalization Note There is at least one ranked level. No existence of a feasible point or minimizer is assumed; the threshold statement retains meaning when the constraints are infeasible. The LP's split variables are free subject to (4)–(5), including feasible pairs with both entries positive.
import Mathlib import Definitions.Def_ExecCompLP_LAD_Setting
namespace ExecCompLP.LAD
theorem lp_equivalence {n L : ℕ} [NeZero L]
(x : Fin n → Fin L → ℝ) (sM sm : ℝ) (K : Finset (Fin L))
(s : Fin L → ℝ) :
(∀ t : ℝ,
(∃ a : Fin n → ℝ, Feasible x sM sm a ∧ obj x K s a ≤ t) ↔
(∃ (a : Fin n → ℝ) (u v : Fin L → ℝ),
LPFeasible x sM sm K s a u v ∧ lpObj K u v ≤ t)) ∧
(∀ a : Fin n → ℝ,
IsMinimizer x sM sm K s a ↔
IsLPMinimizer x sM sm K s a
(fun k => posPart (salary x a k - s k))
(fun k => negPart (salary x a k - s k))) ∧
(∀ (a : Fin n → ℝ) (u v : Fin L → ℝ),
IsLPMinimizer x sM sm K s a u v → IsMinimizer x sM sm K s a) := by sorry
end ExecCompLP.LAD
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.