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

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s