Skip to main content
deleted 7 characters in body
Source Link
Robert Israel
  • 54.2k
  • 1
  • 76
  • 152

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 $\sqrt{(b - A x^*)_i} \le \sqrt{\epsilon}$$(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.

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 $\sqrt{(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.

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.

Source Link
Robert Israel
  • 54.2k
  • 1
  • 76
  • 152

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 $\sqrt{(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.