Skip to content
DraconiticResearch
Search Sources API
197,768 studies31 sourcesUpdated 5 min ago
PreprintarXiv licencearXiv

Feasibility Correction in Linear Programs

  • Pedro Abdalla
  • Roman Vershynin
  • Guangyi Zou
Open at sourcePDFDOICite

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 pth-moment bound for some p>2 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.

Related

  1. Optimization for One, Feasibility for Most: Decoupling Optimization from Feasibility in Chance-Constrained Programs
    Justin Dumouchelle, Shunyu Yao, Beste Basciftci +1
    arXivPreprintarXiv licenceFull textOptimisation & controlarXiv
  2. Two Linear Programs are Better than One
    Alexander E. Black, Christoph Hertrich, Stefan Kober +1
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsOptimisation & controlarXiv
  3. Smooth or Separable? Sparse Block Acceleration for Entropy-Regularized Linear Programs
    Irina Podlipnova, Maxim Mashtaler, Artem Agafonov +2
    arXivPreprintCC BY 4.0Full textOptimisation & controlarXiv
  4. On the Complexity of Linear Programs with Parametric Constraint Matrices
    Laurie Boveroux, Margarida Carvalho, Andrea Lodi +1
    arXivPreprintCC BY-SA 4.0Full textOptimisation & controlarXiv
  5. Randomized Branch Methods with Inexact Subproblems for Bouligand Stationarity in Linear and Quadratic Programs with Complementarity Constraints
    Ziyin Hu, Xin Liu, Shangzhi Zeng +1
    arXivPreprintarXiv licenceFull textOptimisation & controlarXiv

Cite

BibTeXRIS
BibTeX
@misc{abdalla2026feasibility,
  title = {{Feasibility Correction in Linear Programs}},
  author = {Pedro Abdalla and Roman Vershynin and Guangyi Zou},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.36192},
  eprint = {2609.36192},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.36192},
}
RIS
TY  - UNPB
TI  - Feasibility Correction in Linear Programs
AU  - Pedro Abdalla
AU  - Roman Vershynin
AU  - Guangyi Zou
PY  - 2026
DA  - 2026/09/28
PB  - arXiv
DO  - 10.48550/arxiv.2609.36192
UR  - https://arxiv.org/abs/2609.36192
AB  - 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 pth-moment bound for some p>2 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.
ER  -