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.