2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.