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}$? 



Complementary slackness for approximately optimal Dual solution
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.


