3 of 27

Linear algebra/geometry review

A “halfspace” is a set of the following form:�

An affine subspace is a set of the following form:�

4 of 27

Linear algebra/geometry review

“Convex polytope” (generalization of polygon to n-dimensions)

Definition: A convex polytope is a set of the form

��where and .

Note: a convex polytope is the intersection of a bunch of halfspaces

5 of 27

Linear algebra/geometry review

“Convex polytope” (generalization of polygon to n-dimensions)

Equivalent definition: A convex polytope is a set of the form

��for some and .

the inequality is entry-wise

Why equivalent?

6 of 27

Linear programming

Standard form

This last constraint is without loss of generality: one can always convert to an LP of this form starting from one where entries of can be negative

7 of 27

Max flow as a linear program

8 of 27

Max flow as a linear program

9 of 27

Today

Optimal values of LPs
The simplex method

10 of 27

The value of expressing problems as LPs

Due to the prevalence of LPs, especially in business and operations research, many optimizations and libraries are known
We know LPs can be solved in polynomial time

Makes writing down a problem as an LP a good first step

Writing a problem as a linear program, can sometimes make a solution apparent
LP “duality” (which we won’t cover) can give a different perspective on the problem

11 of 27

Minimization LPs

Recall that we can easily turn a maximization LP into a minimization LP:

12 of 27

An example problem

You’re planning meals for the week.

There are different foods, e.g. rice, broccoli, beans, eggs,..

Each food has:

A cost per serving
A certain amount of protein, carbs, fats, vitamins, minerals,.. (say nutrients total)
And you must meet some nutritional requirements, say at least:

50g of protein
30g of fat
2000 calories
etc.

You want the cheapest combination of foods that satisfies all nutritional requirements

13 of 27

An example problem

We can cast the problem as an LP:

subject to

for each

Number of servings of food

Cost of food

Amount of nutrient in food

Minimum amount of nutrient needed

14 of 27

Another example: shortest path as an LP

Claim: The length of the shortest path is the solution to the following “flow-like” LP.

Proof (sketch):

A path of length corresponds to a flow of value (put flow 1 on every edge in the path). So, shortest path LP minimum.

Any flow is the sum of flows along paths . These flow paths can have non-integer value, but, since total flow is 1, the flow can be thought of as a probability distribution over paths! ��

Input: Directed graph and vertices

Output: (Length) of shortest path

Sum of flow on every edge (not just outgoing from )

Flow 1 must come out of

15 of 27

Another example: shortest path as an LP

Claim: The length of the shortest path is the solution to the following “flow-like” LP.

Proof (sketch):

A path of length corresponds to a flow of value (put flow 1 on every edge in the path). So, shortest path LP minimum.

Any flow is the sum of flows along paths . These flow paths can have non-integer value, but, since total flow is 1, the flow can be thought of as a probability distribution over paths! �The minimum value is always achieved by sending all flow along the best (i.e. minimal) individual path in this distribution. �

Input: Directed graph and vertices

Output: (Length) of shortest path

Sum of flow on every edge (not just outgoing from )

Flow 1 must come out of

16 of 27

Another example: shortest path as an LP

Claim: The length of the shortest path is the solution to the following “flow-like” LP.

Proof (sketch):

A path of length corresponds to a flow of value (put flow 1 on every edge in the path). So, shortest path LP minimum.

Input: Directed graph and vertices

Output: (Length) of shortest path

Sum of flow on every edge (not just outgoing from )

Flow 1 must come out of

17 of 27

Where are the optimums of LPs?

Theorem: A local optimum of an LP (if it exists) is a global optimum.

Proof: Recall we are maximizing subject to and is convex polytope. Assume is a local optimum but not a global optimum:

Then for some as is not a global optimum.
Consider the segment . This is exactly the set of points for .
Note that .
So is not a local optimum. Contradiction.

Optimum within some ball around it.

i.e. any point on this segment does better than . We always improve by putting more weight on .

18 of 27

Vertices of a convex polytope

Definition: A vertex of a convex polytope is any point such that is not the midpoint of any line segment for .

Lemma: Let be the vertices of a convex polytope . Then, every point equals for and (i.e. every point in is a “convex combination” of its vertices).

This is an intuitive but powerful fact! We won’t cover the proof in class though..

19 of 27

Vertices of a convex polytope

Theorem: If the optimum of an LP is finite, then the optimum must be achieved at some vertex.

Proof: Let be the vertices of the feasible region . Then, by the previous lemma, every point equals for and .

By linearity of the objective function,

, where

holds since

since

20 of 27

Vertices of a convex polytope

Theorem: If the optimum of an LP is finite, then the optimum must be achieved at some vertex.

Proof: Let be the vertices of the feasible region . Then, by the previous lemma, every point equals for and .

By linearity of the objective function,

, where

So one of the vertices must do better than .

21 of 27

The simplex method

How does one solve LPs?

We’ll look at an algorithm called the simplex method. It will be unique amongst the algorithms we study in this course:

The simplex method runs remarkably fast in practice and is super useful
However, it can run in exponential time in the worst case even when there exist other polynomial time algorithms for the problem

Later on, we will take a high-level glance at an algorithm for solving LPs that is known to run in polynomial time.

22 of 27

The simplex method