Feasibility Correction in Linear Programs
Pedro Abdalla, Roman Vershynin, Guangyi Zou
Source abstract
We study feasibility correction for linear programs. Suppose an initial point satisfies most of the constraints. Can it be moved into the feasible region without changing the objective value? Our main deterministic result says that this is possible if the constraint matrix satisfies a restricted isometry property (RIP). We apply the correction theorem to obtain lower bounds for random linear programs with finite-moment or sub-Weibull entries. We complement these with matching-order upper bounds under a uniform th-moment bound for some and a delocalization condition on the objective direction. As an application of our techniques, we also derive lower bounds for the Gaussian width of feasible regions under RIP assumptions.
Evidence graph
No public relationships recorded yet.
Integrity note: This page is a factual metadata record created by deterministic ingestion. It is not a claim that the work moves a mathematical frontier or has been independently verified.