Inexact LP with hypersphere uncertainty is the LP with columns aⱼ + ρⱼ·e
ProvedSoysterInexactLP.Auxiliary.hyperBall_lplinear-programmingp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1robust-optimization
Let be an matrix, , , and let be the Euclidean ball of radius around . Then is feasible for (Ib) with these activity sets if and only if
where is the vector of all ones. Consequently, for every objective , the optimal solutions of (Ib) are exactly the optimal solutions of
This is the paper's application: a linear program whose activity vectors are known only up to a ball of radius is solved by an ordinary linear program with inflated columns.
Formalization Note "Optimal solution" means a feasible point attaining the maximum of over the feasible set. The norm is Euclidean and the radii are nonnegative.
Preamble
import Mathlib import Definitions.Def_SoysterInexactLP_Auxiliary_Problems open Pointwise Matrix
Formal statement
namespace SoysterInexactLP.Auxiliary
theorem hyperBall_lp {m n : ℕ} (A₀ : Matrix (Fin m) (Fin n) ℝ)
(ρ : Fin n → ℝ) (hρ : ∀ j, 0 ≤ ρ j) (b : Fin m → ℝ) :
{x | FeasibleIb (hyperBall A₀ ρ) b x} =
{x | (∀ j, 0 ≤ x j) ∧ ∑ j, x j • (fun i => A₀ i j + ρ j) ≤ b} ∧
∀ c x : Fin n → ℝ,
IsOptimal (FeasibleIb (hyperBall A₀ ρ) b) c x ↔
IsOptimal (fun y => (∀ j, 0 ≤ y j) ∧ ∑ j, y j • (fun i => A₀ i j + ρ j) ≤ b) c x := by sorry
end SoysterInexactLP.Auxiliary
Source
Soyster, Convex Programming with Set-Inclusive Constraints and Applications to Inexact Linear Programming, Operations Research 21 (1973), p. 1157 (PDF p. 5), §Inexact Linear Programming, last display
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.