Typed version of some of my notes on Linear Programming for the Graduate Algorithms course I am taking. Not formatted the best, but it gets the job done.

Linear programming provides a way of describing and solving optimization problems via the use of linear functions.

## Standard Form of Primal LP

*max*c^{T}x*subject to*Ax ≤ b*and*x ≥ 0

## Standard Form of Dual LP

*min*b^{T}y*subject to*A^{T}y ≥ c*and*y ≥ 0

## Example Primal LP

*max*x_{1}- 2x_{3}**x**_{1}- x_{2}≤ 1**2x**_{2}- x_{3}≤ 1**x**_{1},x_{2},x_{3}≥ 0

## Linear Algebra (Matrix) View of LP

We can view the Primal LP above as a series of matrices where *b* is a vector containing the coefficients of the objective function, *A* is a matrix containing the coefficients for each *x* variable in each of the constraints (the omission of a variable in a constraint results in a 0), and *c* is a vector containing the right-hand side value of each constraint inequality.

## Finding Dual LP from Primal LP

My method for writing out the Dual LP:

Create a new variable *y* for each condition (except for the ≥ 0 constraints)

The objective function for the Dual LP will consist of the right side of the inequalities of the Primal LP as the coefficients for each *y*. For example the Primal LP above has the following constraints:

**x**_{1}- x_{2}≤ 1**2x**_{2}- x_{3}≤ 1

This would result in the following objective function for the Dual LP:

*min*1y_{1}+ 1y_{2}

Now we come up with the constraints for the Dual LP based on variables in the Primal LP. First let’s do the left-hand side of the inequalities:

**x**_{1}- x_{2}≤ 1

Becomes

**1x**_{1}y_{1}- 1x_{2}y_{1}

and

**2x**_{2}- x_{3}≤ 1

Becomes

**2x**_{2}y_{2}- 1x_{3}y_{2}

Put these both together and we get:

**1x**_{1}y_{1}- 1x_{2}y_{1}+ 2x_{2}y_{2}- 1x_{3}y_{2}≥ 1y_{1}+ 1y_{2}

Now let’s factor out the *x* variables to create our constraints for our Dual LP.

**x**_{1}(1y_{1}) + x_{2}(-1y_{1}+ 2y_{2}) + x_{3}(-1y_{2})

We have three *x* variables so we’ll have three constraints. We’ll use the coefficiences of the *x* variables from the objective function of the Primal LP to use on the right-hand side of our Dual LP’s inequalities.

**x**_{1}(1y_{1})

Will give us this inequality:

**1y**_{1}≥ 1

And

**x**_{2}(-1y_{1}+ 2y_{2})

Will give us this inequality:

**-1y**_{1}+ 2y_{2}≥ 0 (zero because x_{2}is not in the objective function)

And

**x**_{3}(-1y_{2})

Will give us this inequality:

**-1y**_{2}≥ -2

All in all this gives us the following Dual LP:

## Example Dual LP

*min*1y_{1}+ 1y_{2}**1y**_{1}≥ 1**-1y**_{1}+ 2y_{2}≥ 0**-1y**_{2}≥ -2**y**_{1},y_{2}≥ 0

## Converting LP into Standard (Canonical) Form

As you can see, the Dual LP above looks a bit different. It is minimizing instead of maximizing and using greater-than-or-equal-to instead of less-than-or-equal-to in its inequalities. We can convert it into standard for pretty simply, though.

Just multiply the objective function and both sides of the inequality by -1!

*max*-1y_{1}+ -1y_{2}**-1y**_{1}≤ -1**1y**_{1}+ -2y_{2}≤ 0**1y**_{2}≤ 2**y**_{1},y_{2}≥ 0

## Determining if an LP is Infeasible

The **feasible region** of a linear program is the section of space where a valid point can lie. An LP is said to be infeasible when this feasible region is empty and therefore there is no valid assignment of its variables that can satisfy all of the LP’s constraints.

For example, take the following LP:

*max*x_{1}+ x_{2}**-1x**_{1}+ -1x_{2}≤ -5**1x**_{1}≤ 1**1x**_{2}≤ 1**x**_{1},x_{2}≥ 0

As you can probably tell, there is no way that we can have both x_{1} and x_{2} be both less than 1 **and** have their negated sum be less than 5. This LP is obviously infeasible. How can we programmatically determine this, though?

One was is by adding a new variable, *z*, to one of the constraints of our LP to create a new LP.

**-1x**_{1}+ -1x_{2}+ z ≤ -5

*z* can be anything we need it to be. It can be as low as necessary to make this constraint feasible. What we want to see, though, is if we can find value of *z* such that **z ≥ 0**. If we can find one, this shows that *z* is not contributing anything to satisfy the inequality and that the original inequality without it is satisfiable on its own. We can determine this by creating a new objective function to maximize *z*.

*max*z**-1x**_{1}+ -1x_{2}+ z ≤ -5**1x**_{1}≤ 1**1x**_{2}≤ 1**x**_{1},x_{2}≥ 0

Like I said earlier, if **z ≥ 0** then the original LP is feasible. If not, then the LP is infeasible. For the other constraints we could add additional variables to do the same (e.g. z_{1}, z_{2}, …)

## Determining if an LP is Unbounded

A linear program is said to be **unbounded** if its objective function can be made arbitrarily large for maximization or small for minimization. How can we tell if an LP is unbounded?

We can use the Dual LP!

The Dual LP gives us an upper bound on the objective function of the Primal LP.

**c**^{T}x ≤ b^{T}y

This is known as the **weak duality theorem**. Some facts from the theorem:

- If the Primal LP is
**unbounded**, the Dual LP is**infeasible** - If the Dual LP is
**unbounded**, the Primal LP is**infeasible** - If the Dual LP is
**infeasible**, the Primal LP is either**unbounded***or***infeasible**

We can use these facts to determine if our Primal LP is **unbounded** or not.

- First check and see if the Primal LP is
**infeasible**using the*z*variable approach described above. - If it is
**feasible**then find the Dual LP and check to see if it is**feasible**or not using the*z*variable technique. - If the Dual LP is
**infeasible**and we found our Primal LP to be**feasible**then we know the Primal LP must be**unbounded**. If the Dual LP is**feasible**then our Primal LP is**bounded**.

### Strong Duality Theorem

Primal LP is **feasible** and **bounded** *iff* Dual LP is **feasible** and **bounded**

If there is an optimal point for the Primal then there is an optimal point for the Dual.