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

Linear Programming

Introduction

Problem description:

lemma: every lp is infeasible, has opt, or is unbounded

Problem formulation:

Some steps towards efficient solution:

Linear Equalities

How solve? First review systems of linear equalities.

To talk formally about polynomial size/time, need to talk about size of problems.

Claim: if $A$ is $n \times n$ matrix, then $\det(A)$ is poly in size of $A$

Corollary:

What if $A$ isn't square? Can we find an answer?

So can check answer in polynomial time.

2013 Lecture 13 end

Can we show there isn't an answer?

Summary:

Geometry

Polytopes

Basic Feasible Solutions

Again, let's start by thinking about structure of optimal solution.

Where can optimum be? At “corners.”

Basic solutions:

In fact, vertex, extreme point, bfs are equivalent.

Any standard form lp $\min cx,\ Ax=b,\ x\ge 0$ with opt has one at a BFS.

Corollaries:

Question:

Vertices and Extreme Points

Two other characterizations of corner.

Vertex:

Extreme Point

Shows output is polynomial size:

Yields first algorithm for LP: try all bfs.

OK, this is an exponential method for finding the optimum. Maybe we can do better if we just try to verify the optimum. Let's look for a way to prove that a given solution $x$ is optimal.

2011 Lecture 10 end
2012 Lecture 12 end
Quest for nonexponential algorithm: start at an easier place: how decide if a solution is optimal?