TransWikia.com

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

Mathematics Asked by DL1 on January 5, 2021

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.

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP