\documentclass{article} \usepackage{me} \usepackage{amssymb} \usepackage{amsfonts} \setlength{\parindent}{0pt} $\newcommand\vol{{\mbox{vol}}}$

Lecture 14: Algorithms for Solving LPs

LP Solving Algorithms

So far we learned a lot about the structure of LPs. But how do we actually solve them? Can we do it faster than by just enumerating all basic feasible solutions (BFS)?


Ellipsoid Method

Consider the linear program $$ \begin{eqnarray*} &&\min \sum_j x_j \\ \sum_j a_{ij} x_j &\geq &1 \;\;\; \forall i\\ x_j &\geq &0 \;\;\; \forall j \end{eqnarray*} $$ and its dual $$ \begin{eqnarray*} &&\max \sum_i y_i \\ \sum_i a_{ij} y_i &\leq &1\\ x_{i}&\geq &0. \end{eqnarray*} $$ Assume that $A=[a_{ij}]$ is $m\times n$ and has only {\it nonnegative} entries.

In this problem, you'll have to show that a continuous algorithm solves (almost miraculously) the above pair of dual linear programs. We shall define a series of functions whose argument is the “time” and you'll show that some of these functions tend to the optimal solution as time goes to infinity. (For simplicity of notation, we drop the dependence on the time.)

Observe that when $s_k$ is increased, the vectors $t$ and $d$ as well as $D$ change also, implying that the index $k$ changes over time.

Reduce optimization to feasibility checking. (Remind how it is with polytope $P$.)

Lion hunting in the desert.

vertices in standard form/bases:

Summary: $x$ is vertex of $P$ if for some basis $B$,

Simplex method:


Paths length in polytopes

Simplex and Duality

Polynomial Time Bounds

We know a lot about structure. And we've seen how to verify optimality in polynomial time. Now turn to question: can we solve in polynomial time?

Yes, sort of (Khachiyan 1979):

2012 L16 Start


Lion hunting in the desert.

Define an ellipsoid

Outline of algorithm:

Consider sphere case, separating hyperplane $x_1=0$

Formalize shrinking lemma:

So ellipsoid shrinks. Now prove 2 things:

Starting size:

Ending size:

Put together:

Justifying full dimensional:

Infinite precision:


Need to find vertex?

Feasibility vs. Separation vs. Optimization

Notice in ellipsoid, were only using one constraint at a time.

This is very useful in many applications. e.g. network design.

2011 Lecture 13 end
2013 Lecture 17 end

Interior Point

Ellipsoid has problems in practice ($O(n^6)$ for one). So people developed a different approach that has been extremely successful.

What goes wrong with simplex?

Primal-Dual Method

Potential Reduction

Potential function:

Early methods used gradient descent:

More recent, arguably cleaner approach is central path

Characterizing the central path

How discretize?


What is the improvement direction?

Can we solve this?

How far?

Interior point has recently been revolutionizing maxflow.

2012 Lecture 16 end
2013 Lecture 18 end