Mar 23. Linear Programming II

Consider the following standard form of an LP:

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

  • Ax = b
  • x \ge 0

The decision problem associated with this LP is the following: does there exist an x \ge 0  such that c^\top x > t and Ax = b. To certify a yes instance, we can simply give as our certificate a solution x \ge 0 such that c^\top x > t and Ax=b. To certify a no instance we will use the dual LP. Recall the dual form of the above LP:

\min{b^\top y}

  • A^\top y \ge c

Weak LP Duality: Let OPT(P) denote the optimal value of the primal program and let OPT(D) denote the optimal value of the dual program. We claim that OPT(P) \le OPT(D) (if the optima exist).

Proof: Let x be a feasible solution of the primal and let y be a feasible solution to the dual. Then c^\top x \le y^\top Ax = y^\top b.

Farkas’ Lemma: Let A \in \mathbb{R}^{m \times n} and b \in \mathbb{R}^m then exactly one of the following holds:

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

Proof: Let C_A = \{ Ax \mid x \ge 0\} be the cone generated by the columns of A. In other words if \{a_1, \cdots, a_n\} are the columns of A, then C_A = \{ \sum_{i=1}^n a_i x_i \mid x_i \ge 0\}. Suppose there exists an x \ge 0 such that Ax = b, then clearly b \in C_A. Note that C_A is a convex set – since if x, y \in C_A then for any 1\ge \lambda \ge 0, \lambda x + (1-\lambda)y \in C_A since \lambda, (1-\lambda) \ge 0. From the homework, if b \notin C_A, then \exists y, \alpha such that y^\top b < \alpha and Ay \ge \alpha \bf{1}, where \bf{1} is the all 1‘s vector. Note that \alpha cannot be positive. Suppose \alpha < 0. We may raise \alpha till there must be some subset of columns of A such that y^\top A_{|S} = -\epsilon where \epsilon > 0. But then for a large enough M > 0, and scaling every column of A_{|S} by M we get y^\top A_{|S} < \alpha. This contradicts the fact that y^\top x \ge \alpha for any \alpha \in C_A. Thus we may raise \alpha till it is equal to 0.

Strong LP Duality: If the primal and dual are feasible, then OPT(P) = OPT(D).

Proof: Let z = OPT(D). Suppose there exists an x such that

  • Ax = b
  • c^\top x = z
  • x \ge 0

In this case we would be done. Let B^\top = [A^\top, c] and d^\top = [b^\top, z]. Then by Farkas’ lemma, either:

  1. \exists x\ge 0 such that Bx = d, in which case we have an x\ge 0 such that Ax = b and c^\top x = OPT(D).
  2. \exists [y, \alpha] such that A^\top y + \alpha c \ge 0 and b^\top y + \alpha z < 0. In this case, choose a feasible x for the primal program. Then 0 \le x^\top A^\top y + \alpha(x^\top c) = b^\top y + \alpha (x^\top c) which implies (if \alpha \ge 0) that c^\top x > z which contradicts weak duality. If \alpha < 0 then A^\top y \ge -\alpha c while b^\top y < -\alpha z which implies A^\top (-y)/\alpha \ge c while b^\top (-y)/\alpha < z. This contradicts optimality of z. Thus this option is not possible.

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