Mar 11. Linear Programming

Consider a generic linear program:

\max{c^\top x} s.t.

  • Ax \le b
  • x\ge 0

Note that we can write any linear program in this form. Suppose the x \ge 0 was absent. Then we could write x = y - z where y \ge 0, z \ge 0 and this would make it an LP of the above form. Here are a few other forms of the LP that are equivalent:

\max{c^\top x} s.t.

  • Ax = b
  • x \ge 0

We can write the first form by introducing a slack variable, i.e. Ax \le b if and only if there exists s \ge 0 such that Ax + s = b. To write the second form in the first form we observe that Ax = b if and only if Ax \le b and -Ax \le -b.

Suppose we are given a linear program in the first form, i.e.

\max{c^\top x} s.t.

  • Ax \le b
  • x \ge 0

We wish to find an upper bound for the maximum. Notice that for any y \ge 0 such that y^\top A \ge c^\top, y^\top b is a valid upper bound for the maximum. Thus the best upper bound we can find is given by another LP called the dual of the first LP.

\min{y^\top b} s.t.

  • y^\top A \ge c^\top
  • y \ge 0

The first LP is often called the primal and the second program is called the dual. Note that the dual of the dual is the primal program. Let P be the primal optimal value and D the dual optimal value. Then weak LP duality tells us that P \le D.

Strong LP Duality: For a primal and dual pair of LP programs, P = D. In other words

\max\{c^\top \mid Ax \le b, x \ge 0\} = \min\{b^\top \mid A^\top y \ge c, y \ge 0\}.

To prove this we will introduce the following simple lemma.

Farkas Lemma: Let A \in \mathbb{R}^{m \times n} and b \in \mathbb{R}^n. Then exactly one of the following is true:

  1. x \ge 0 such that Ax = b
  2. y such that b^\top y < 0 and A^\top y > 0

Let a_1, \cdots, a_n be the columns of A. Then the first condition is equivalent to saying that the vector b belongs to the cone generated by the columns of A. Notice that the cone generated by the set of vectors \{a_1, \cdots, a_n\} is given by C = \{ \sum_i a_i x_i \mid x_i \ge 0\}. The second condition merely says that if b \notin C (i.e. the first condition does not hold) then one can find a hyperplane H going through the origin such that H separates b from the cone. The hyperplane is given by \{x \mid y^\top x = 0\}. Since y^\top a_i > 0 for every a_i it follows that for every element x\in C satisfies y^\top x \ge 0. However y^\top b < 0 thus separating it.

Leave a Reply

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

You are commenting using your 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