0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – coffeemath
    Commented Aug 15, 2023 at 4:12

1 Answer 1

1
$\begingroup$

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$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .