Mathematical Programming-Notes-Part 1-Strong Duality in Linear Programming

Programming is the basis for a wide range of fields. This blog summarized the sufficient conditions for strong duality. Moreover, it is a summery of Mathematical Programming lecture notes (David P. Williamson).

1. Separating Hyperplane Theorem

1.1 Weierstrass Theorem

Let $C \subset \mathbb{R}^n$ be a closed, non-empty and bounded set. Let $f$: $C \rightarrow \mathbb{R}$ be continuous on $C$. Then $f$ attains a maximum (and a minimum) on some point of C.

1.2 Separating Hyperplane Theorem

Let $C \subset \mathbb{R}^n$ be closed, non-empty and convex set. Let $y \notin C$, then there exists a hyperplane $a \ne 0$, $a \in \mathbb{R}^n, b \in \mathbb{R}$, such that $a^Ty > b$ and $a^Tx

2. Farkas’ Lemma

Let $A \in \mathbb{R}^{m \times n}$ and $b \in \mathbb{R}^m$. Then exactly one of the following two conditions holds for a given A, b:

(1) $\exists x \in \mathbb{R}^n$, such that $Ax=b, x\ge 0$

(2) $\exists y \in \mathbb{R}^m$, such that $A^Ty \ge 0$, $y^Tb < 0 $

2.1 Proof:

Step 1: We cannot have two statements hold at the same time.

Assume $\exists x \in \mathbb{R}^n$, such that $Ax=b, x\ge 0$; Assume $\exists y \in \mathbb{R}^m$, such that $A^Ty \ge 0$, $y^Tb<0$. Note that $ x^TA^Ty = y^TAx = y^Tb < 0 $, which means $x \ge 0$ and $A^Ty \ge 0$ cannot hold at the same time.

Step 2: If (1) doesn’t hold, then (2) holds.

Let $v_1, v_2, \dots, v_n$ be the column vectors of A. Define

$Q = conv(v_1, v_2, \dots, v_n) = \{s \in \mathbb{R}^m: s = \sum_{i=1}^{n}\lambda_i v_i, \lambda_i \ge 0, \forall i\}$

(Note that Q is a conic combination rather than a convex combination, since we don’t need $\sum_{i=1}^{n} \lambda_i = 1$)

Then $Ax = \sum_{i=1}^n x_iv_i$, there exists $x$ such that $Ax=b$ and $x \ge 0$ iff $b \in Q$. In other words, $b$ is an element in the space, whose basis vectors are the columns of A. If (1) does not hold then $b \notin Q$, according to hyperplane separating theorem, there exists $\alpha \in \mathbb{R}^m$, $\alpha \ne \vec{0}$, and $\beta$ such that $a^Tb > \beta$, $a^Ts < \beta$ for all $s \in Q$. Note that $0 \in Q$, then $\beta > 0$. Note also that $a^T\lambda v_i < \beta$, then $a^T v_i \le 0$ (take $\lambda \rightarrow 0$). We prove that $\beta$ has to be 0 here.

Then we can find $y = -a$ (splendid), we obtain $y^Tb < 0$ and $y^Tv_i \ge 0$ for all i. Condition (2) holds.

2.2 The equivalence of a variant on Farka’s lemma

(1’) $\exists x \in \mathbb{R}^n$, such that $Ax=b$

(2’) $\exists y \in \mathbb{R}^m$, such that $A^Ty = 0$, $y^Tb=-1$, $y \ge 0$

The equivalence is trivial by finding a proper ‘y’ in section 2.1.