How to prove strict complementary slackness by means of Farkas' lemma

1.1k Views Asked by At

This question relates to pages 89 and 96 the following text (pages 102 and 109 of the pdf):

https://promathmedia.files.wordpress.com/2013/10/alexander_schrijver_theory_of_linear_and_integerbookfi-org.pdf

The author gives the following variant of Farkas' lemma:

Let $A$ be a matrix and $b$ be a vector. Then the system of linear inequalities $Ax \le b$ has a solution $x$, if and only if $yb \ge 0$ for each row vector $y \ge 0$ with $yA = 0$.

He then proves that:

for a bounded and feasible linear program

$$\max \{ cx \mid Ax \le b \} = \min \{ yb \mid y \ge 0, yA = c \} $$

if the maximum problem has no optimum $x_0$ with $a_ix_0 \lt b_i$ then the minimum problem must have an optimum $y_0$ with a positive $\mathit{i}$th component.

The proof starts as follows:

It is assumed that there is no optimum solution $x_0$ for the maximum problem with $a_ix_0 \lt b_i$. Then, if $\delta$ is the optimum value of the maximum and minimum problems, $Ax \le b, cx \ge \delta$ implies $a_ix \ge \beta_i$. So, by Corollary 7.1e (Farkas' lemma as given above), $yA - \lambda c = -a_i$ and $yb - \lambda \delta \le -\beta_i$ for some $y, \lambda \ge 0$.

My question is:

How does the last sentence ("So") follow from what preceeds it?

Specifically, how can "$Ax \le b, cx \ge \delta$ implies $a_ix \ge \beta_i$" be cast in a form such that application of Farkas' lemma yields $yA - \lambda c = -a_i$ and $yb - \lambda \delta \le -\beta_i$ for some $y, \lambda \ge 0$?

Neither the positive form ("$Ax \le b, -cx \le -\delta, -a_ix \le -\beta_i$ has a solution") nor the negative form ("$Ax \le b, -cx \le -\delta, a_ix \le \beta'_i$, with $\beta'_i \lt \beta_i$, has no solution") yields exactly the desired inequalities when Farkas' lemma is applied. For example, signs or inequality directions differ from those sought.

Any help would be greatly appreciated.