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 subject to
- max subject to and
- max subject to and

There are three possible outcomes to a linear program:

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

**Decision problem:** Does the exist an satisfying ?

**Is the problem in NP?** Yes, output a vector which satisfies each inequality. We need to worry about the bit sizes of ; perhaps there is an which satisfies the system, but it takes exponentially many bits to represent it. It turns out that if 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 .

**Is the problem in Co-NP?** Yes, by LP duality. If there does exist such an , then there will be a certificate proving this.

Consider the following LP:

How can we show that this LP has no solution higher than a certain value ? 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 , 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 be the multiplier for equation in the primal LP. Then the dual is of the above LP as follows:

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:

- The dual of max s.t. is s.t. .
- The dual of max s.t. and is s.t. .
- The dual is max s.t. and is s.t. .

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

**Theorem (weak LP Duality).** Let satisfy and let satisfy . Then, .

**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 , one of the following is true:

- there exists such that .
- there exists such that .

**Proof:** The idea of the proof is to show that if there does not exist an satisfying the system, then there must exist a separating hyperplane of from the set . 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 s.t. and and its dual (D) is s.t. . Let be the optimal value of the dual. We then show that is the optimal value of the primal. Consider the system: . Then, by Farkas Lemma, one of the following must be true:

- There exists an such that
- There exists a such that and .

Suppose for contradiction that there is no solution to .

Take a feasible that satisfies . Then

If , then , which contradicts weak duality.

If , then and also , which contradicts the optimality of .