THEOREM — (Ib) and LP(Ā) have the same feasible solutions and the same optimal solutions
ProvedSoysterInexactLP.Auxiliary.theorem_lp_feasible_ifflinear-programmingp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1robust-optimizationsupport-function
Let be nonempty convex activity sets with
let , and let be the matrix with entries . Then
- is feasible for (Ib), i.e. and , if and only if it is feasible for LP, i.e. and ;
- hence, for every , is an optimal solution of over (Ib) if and only if it is an optimal solution of over LP.
This reduces the convex program (Ib), whose constraint is the inclusion of a Minkowski sum of uncertain activity sets in a half-space intersection, to an ordinary linear program; it is the origin of the "worst-case column" robust counterpart in robust linear optimization.
Formalization Note An optimal solution is a feasible point attaining the maximum of ; the paper does not discuss attainment, and the equality of the feasible sets makes the two problems have the same suprema as well. Convexity of the is the paper's standing assumption and is not needed for this statement.
Preamble
import Mathlib import Definitions.Def_SoysterInexactLP_Auxiliary_Problems open Pointwise Matrix
Formal statement
namespace SoysterInexactLP.Auxiliary
theorem theorem_lp_feasible_iff {m n : ℕ} (K : Fin n → Set (Fin m → ℝ))
(hne : ∀ j, (K j).Nonempty) (hconv : ∀ j, Convex ℝ (K j))
(hfin : ∀ i j, supportFun (K j) (Pi.single i 1) < ⊤) (b : Fin m → ℝ) :
{x | FeasibleIb K b x} = {x | FeasibleLP (Abar K) b x} ∧
∀ c x : Fin n → ℝ,
IsOptimal (FeasibleIb K b) c x ↔ IsOptimal (FeasibleLP (Abar K) 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. 1156 (PDF p. 4), THEOREM
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.