LP Strong Duality

We have three forms of linear programs, which are equivalent — in that an algorithm for any one of them could be used to solve all of them. They are:

  • max c^T x subject to A x \le b
  • max c^T x subject to A x \le b and x \ge 0
  • max c^T x subject to A x = b and x \ge 0

There are three possible outcomes to a linear program:

  1. a vector x satisfying the system and optimizes the objective value
  2. system is unbounded, i.e. no optimum value
  3. system is infeasible, i.e. no possible solution to the constraints

Decision problem: Does the exist an x satisfying A x \le b, x \ge 0, c^T x \ge z?

Is the problem in NP? Yes, output a vector x which satisfies each inequality. We need to worry about the bit sizes of x; perhaps there is an x which satisfies the system, but it takes exponentially many bits to represent it. It turns out that if A,b,c,z are all rational numbers with a polynomial number of bits, then if there is a solution to the system, there will be a polynomial sized solution x.
Is the problem in Co-NP? Yes, by LP duality. If there does exist such an x, then there will be a certificate y proving this.

Consider the following LP:

\begin{aligned}  \max \quad & x_1 + 5 x_2 - x_3 & \\\  s.t. & \quad & \\  &2 x_1 - x_2 - 2 x_3 & \le 10 \\  & 4 x_1 + x_2 + x_2 & \le 20 \\  & - x_1 + 2 x_2 + x_3 & \le 4 \\  & x_1, x_2, x_3 & \ge 0  \end{aligned}

How can we show that this LP has no solution higher than a certain value z? We could consider nonnegative linear combinations of the inequalities, where each coefficient is at most the corresponding coefficient in the objective function. Then because the variables are all \ge 0, this gives an upper bound on how large the objective value can be.

We can express the smallest bound we can get on the primal LP,  i.e. the original LP, by this method as the dual LP. Let y_i be the multiplier for equation i in the primal LP. Then the dual is of the above LP as follows:

\begin{aligned}    \min \qquad & 10 y_1 + 20 y_2 + 4 y_3 & \\    s.t. & \quad & \\    & 2 y_1 + 4 y_2 - y_3 &\ge 1 \\    & - y_1 + y_2 + 2 y_3 & \ge 5 \\    & -2 y_1 + y_2 + y_3 & \ge -1 \\    & y_1, y_2, y_3 & \ge 0    \end{aligned}
Note that the we could apply the above dual transformation to obtain dual LP’s for each of the 3 equivalent forms of LP’s given above:

  1. The dual of max c^T x s.t. A x \le b is \min b^t y s.t. A^T y= c, y \ge 0.
  2. The dual of max c^T x s.t. A x \le b and x \ge 0 is \min b^t y s.t. A^T y \ge c, y \ge 0.
  3. The dual is max c^T x s.t. A x = b and x \ge 0 is \min b^T y s.t. A^T y \ge c.

By definition of a dual LP, we have proved the following theorem.

Theorem (weak LP Duality). Let x satisfy Ax \le b, x \ge 0 and let y satisfy A^T y \ge c, y \ge 0. Then, \max c^T x \le \min \quad b^t y.

Corollary. If the primal program is unbounded, then the dual program is infeasible. Similarly, if the dual is unbounded, then the primal is infeasible.

Question: If both the primal and dual LP’s are feasible, then are their optimal values equal? Yes, and this phenomenon is referred to as strong LP duality.

Lemma (Farkas) For all A \in \mathbb{R}^{m \times n}, b \in \mathbb{R}^m, one of the following is true:

  • there exists x such that A x = b, x \ge 0.
  • there exists y such that A^T y \ge 0, b^t y < 0.

Proof: The idea of the proof is to show that if there does not exist an x satisfying the system, then there must exist a separating hyperplane of b from the set \text{Cone}(A) = \{Ax : x \ge 0 \} . The proof is left as a homework 9 exercise.

Theorem (strong LP duality). Let (P) be an LP and (D) be its dual. Suppose that both systems are feasible. Then their optimal values are equal.

Proof: We will focus on the standard form where (P) is specified as max c^T x s.t. A x = b and x \ge 0 and its dual (D) is \min b^T y s.t. A^T y \ge c. Let z be the optimal value of the dual. We then show that z is the optimal value of the primal. Consider the system: Ax = b, c^T x = z. Then, by Farkas Lemma, one of the following must be true:

  • There exists an x\ge 0 such that (A; c^T) x = (b; z)
  • There exists a y \in \mathbb{R}^m, \alpha \in \mathbb{R} such that (A^T c) \cdot (y; \alpha) \ge 0 and (b^T z) (y; \alpha) < 0.

Suppose for contradiction that there is no solution x \ge 0 to (A; c^T) x = (b; z).

Take a feasible x \ge 0 that satisfies Ax=b. Then

x^T A^T y + \alpha x^T c = b^T y + \alpha (x^T c) \ge 0

If \alpha > 0, then x^T c > z, which contradicts weak duality.

If \alpha < 0, then A^T y \ge -\alpha c \Rightarrow A^T(-y/\alpha) \ge c and also b^T y < -\alpha z \Rightarrow b^T(-y/\alpha) < z, which contradicts the optimality of z.

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