Short introduction on linear programing

In this below, we make a brief introduction on Linear Programing in finite dimension.

Consider following optimization problem: For a given matrix ${A\in \mathbb{R}^{m \times n}}$ and two column vectors ${c \in \mathbb{R}^n}$ and ${b\in \mathbb{R}^m}$ maximize linear cost

$\displaystyle \langle c, x \rangle$

over the constarints

$\displaystyle \{x \in \mathbb{R}^{n} | A x \le b, \ x \ge 0. \}$

For the notational convenience, let’s denote this in the following succinct way:

$\displaystyle V = \sup_{0\le x\in \mathbb{R}^n} \{\langle c, x \rangle | Ax \le b \} \hspace{1 in} (LP).$

The value ${V}$ of the problem (LP) is closely connected to the value of the dual problem given as below:

$\displaystyle U = \inf_{0 \le y\in \mathbb{R}^m} \{\langle b, y \rangle | A^* y \ge c \} \hspace{1 in} (LP').$

In the above, ${A^*}$ is the transpose of ${A}$.

The two important facts reveal the relation of the value functions of the above dual problems: one is called weak duality theorem and the other strong duality theorem.

Weak duality gives upper bound of the value ${V}$ without any assumption, and its proof is short. This result also holds under inifinite dimensional linear programing.

Proposition 1 (Weak duality) ${V \le U}$.

Proof: For arbitrary ${x\in \mathbb{R}^n}$ adimissible for (LP), and ${y\in \mathbb{R}^m}$ adimissible for (LP’), we have

$\displaystyle \langle c, x \rangle \le \langle A^*y, x \rangle \le \langle y, Ax \rangle \le \langle y, b \rangle.$

$\Box$

Strong duality gives sufficient condition for the equality in Weak duality, and the proof is more involved.

Proposition 2 (Strong duality) Assume (LP) has a finite value ${V}$, then ${V = U}$.

Proof: later. $\Box$