Complementary slackness for approximately optimal Dual solution

Question

Given a Primal LP (P) and it Dual LP (D) we know that the optimal solutions to P ($x_{opt}$) and D $(y_{opt})$ satisfy complementary slackness condition, i.e. under optimal solutions either a constraint is tight in P or the corresponding variable in D is zero. If we know that a Dual feasible point, $y$, is approximately optimal then does there exist any (approximate) complementary slackness like condition between $y$ and $x_{opt}$?

Answer 1

Yes, we do have "approximate complementary slackness" in the following sense.

Consider the standard (primal) linear programming problem:

max $c^T x$ s.t. $A x \le b$, $x \ge 0$

If $x^*$ and $y^*$ are primal and dual feasible solutions, we have

$$ c^T x^* \le y^* A x^* \le y^* b$$ with equality iff $x^*$ and $y^*$ are optimal.

Now let's say $x^*$ is optimal with objective value $c^T x^* = v$, while $y^*$ is "approximately optimal" in the sense that it is feasible with objective value $y^* b \le v + \epsilon$, where $\epsilon > 0$ is small. Thus

$$y^* (b - A x^*) \le y^*b - c^T x^* \le \epsilon$$

In particular, for each $i$ we have $y^*_i (b - A x^*)_i \le \epsilon$, so $y^*_i \le \sqrt{\epsilon}$ or $(b - A x^*)_i \le \sqrt{\epsilon}$: i.e. the dual variable value must be near $0$ or the corresponding primal constraint must be nearly tight.