# Closest feasible point of a linear program

I have a standard linear program with inequality and equality constraints: $$\text{maximize } c^Tx \text{ subject to } Ax \leq 0, Bx = 1, x \geq 0$$

I know the feasible region is non-empty and that there is an optimal solution. Even more, x is a probability vector (equality constraints are the simplex constraint). Now, I have a candidate point that satisfies the equality constraints but violates some of the inquality constraints up to $$\epsilon$$. In other words, I have a solution $$x'$$, where $$Ax'\leq \epsilon$$ and $$Bx = 1$$. Clearly this is not feasible for the original LP. But, I want to know how far the closest (L1 norm) point to $$x'$$ that lies the feasible region is.

Does anyone have some intuition about how to reason about this? I'm not sure how to specifically move toward the feasible region is a way that satifies equality constraints and lowers the constraint violation.

• You might look up two-phase simplex method. In one phase you begin with a non-feasible point and pivot etc until getting a feasible point, and in the other phase one starts with that feasible set and pivots in such a way that one keeps to feasible points only until done. Commented Aug 15, 2023 at 4:12

It might not be easy to get a useful bound. Consider the case with one inequality $$\varepsilon x_2 + x_3 \le 0$$ (besides $$x_1, x_2, x_3 \ge 0$$) and one equality $$x_1 + x_2 + x_3 = 1$$. The only feasible solution is $$(1,0,0)$$, but $$(0,1,0)$$ satisfies the inequality up to $$\varepsilon$$.