Linear Programming
Introduction
Problem description:
- motivate by min-cost flow
- bit of history
- everything is LP
- NP and coNP. P breakthrough.
- general form:
- variables
- constraints: linear equalities and inequalities
- $x$ feasible if satisfies all constraints
- LP feasible if some feasible $x$
- $x$ optimal if optimizes objective over feasible $x$
- LP is unbounded if have feasible $x$ of arbitrary good objective value
lemma: every LP is infeasible, has opt, or is unbounded
- (by compactness of $R^n$ and fact that polytopes are closed sets).
Problem formulation:
- canonical form: $\max c^Tx, Ax \le b$
- note $c$ is a row vector but I won't always write $c^T$
- matrix representation, component-wise $\le$
- rows $a_i$ of $A$ are constraints
- $c$ is objective
- any LP has transformation to canonical:
- max/min objectives same
- move vars to left, consts to right
- negate to flip $\le$ for $\ge$
- replace $=$ by two $\le$ and $\ge$ constraints
- standard form: $\min c^Tx, Ax=b, x\ge 0$
- slack variables
- splitting positive and negative parts $x \rightarrow x^+-x^-$
- $Ax \ge b$ often nicer for theory; $Ax=b$ good for implementations.
Some steps towards efficient solution:
- What does answer look like?
- Can it be represented effectively?
- Easy to verify it is correct?
- Is there a small proof of no answer?
- Can answer, nonanswer be found efficiently?
Linear Equalities
How solve? First review systems of linear equalities.
- $Ax=b$. when have solution?
- baby case: $A$ is squre matrix with unique solution.
- demonstrate solution by giving $x$
- easy to verify correct!
- construct using, eg, Gaussian elimination.
- Suppose there's a answer. Can we write it down?
- discuss polynomiality, integer arithmetic later
- equivalent statements:
- $A$ invertible
- $A^T$ invertible
- det$(A)\ne 0$
- $A$ has linearly independent rows
- $A$ has linearly independent columns
- $Ax=b$ has unique solution for every $b$
- $Ax=b$ has unique solution for some $b$.
To talk formally about polynomial size/time, need to talk about size of problems.
- integer $n$ has size $\log n$
- rational $p/q$ has size size$(p)$+size$(q)$
- size(product) is sum(sizes).
- dimension $n$ vector has size $n$ times size of number
- $m \times n$ matrix similar: $mn$ times size of numbers
- size (matrix product) at most sum of matrix sizes
- our goal: polynomial time in size of input, measured this way
Claim: if $A$ is $n \times n$ matrix, then $\det(A)$ is poly in size of $A$
- more precisely, twice the size
- proof by writing determinant as sum of permutation products. \[ det(A)=\sum_{\pi:n\rightarrow n} \textrm{sign}(\pi)\prod_{i=1}^{n} A_{i\pi(i)} \]
- each product has size $n$ times size of numbers
- $n!$ products
- so size at most size of ($n!$ times product) $\le n\log n+n\cdot$size(largest entry).
Corollary:
- inverse of matrix is poly size (write in terms of cofactors---Cramer's rule). For any $i$, \[ x_i^*=\frac{det(A_i)}{det(A)}, \] where $A_i$ is the matrix $A$ with the $i$-th column substituted with $b$.
- solution to $Ax=b$ is poly size (by inversion)
- can use this to argue Gaussian eliminiation produces poly size answer
- not obvious, since multiplying two integers can yield a double-size integer and we do polynomially many multiplies in GE
- but can argue if work in units of $1/det(A)$ that all stays integer
What if $A$ isn't square? Can we find an answer?
- Note we are asking if columns of A span $b$
- Find a maximal set of linearly independent columns
- These span $b$ if $A$ does.
- Extend to a basis by adding (independent) columns
- Now previous analysis applies
- Unique $x$
- It had better zero out all the added columns
So can check answer in polynomial time.
Can we show there isn't an answer?
- $Ax=b$ has a witness for true: give $x$.
- How about a proof that there is no solution?
- “Failure of algorithm to work” is a hard witness to check
- note that “$Ax=b$” means columns of $A$ span $b$.
- in general, set of points $\set{Ax \mid x \in \Re^n} $ is a subspace
- 2d case
- $\set{Ax}$ is a line through origin
- $A$ is vector in direction of line
- point $b$ not on line
- i.e., part of it (projection) is perpendicular to line
- claim: no solution iff for some $y$, $yA=0$ but $yb \ne 0$.
- proof: if $Ax=b$, then $yA=0$ means $yb=yAx=0$.
- if no $Ax = b$, means columns of $A$ don't span $b$
- set of points $\set{Ax}$ is subspace not containing $b$
- find part of $b$ perpendicular to subspace, call it $y$
- then $yb \ne 0$, but $yA=0$,
- standard form LP asks for linear combo too, but requires that all coefficients of combo be nonnegative!
- wait, we showed existence, but is $y$ polynomial size?
- note $yb \ne 0 $ has solution means $yb=1$ has solution
- so solve $y \cdot \binom{A}{b} = \binom{0}{1}$
- we proved this matrix problem has polynomial number of bits solution
- and can find by e.g. Gaussian elimination
Summary:
- in polytime, can find solution
- and provide easy polytime checkable solution
- and in polytime can determine insoluble
- and give easy polytime checkable “nonsolution”
Geometry
Polytopes
- canonical form: $Ax \ge b$ is an intersection of (finitely many) halfspaces, a (convex) polytope
- standard form: $Ax=b$ is an intersection of hyperplanes (thus a subspace), then $x \ge 0$ intersects in some halfspace. Also a polytope, but not full dimensional.
- polytope is bounded if fits inside some box.
- (some call this polyhedron. Others invert definitions.
- either formulation defines a convex set:
- if $x, y \in P$, so is $\lambda x+(1-\lambda)y$ for $\lambda \in 0,1$.
- that is, line from $x$ to $y$ stays in $P$.
- halfspaces define convex sets. Converse also true!
- let $C$ be any convex set, $z \notin C$.
- then there is some $a,b$ such that $ax \ge b$ for $x \in C$, but $az < b$.
- proof by picture. also true in higher dimensions (don't bother proving)
- deduce: every convex set is the intersection of the halfspaces containing it.
Basic Feasible Solutions
Again, let's start by thinking about structure of optimal solution.
- Can optimum be in “middle” of polytope?
- Not really: if can move in all directions, can move to improve opt.
Where can optimum be? At “corners.”
- “vertex” is point that is not a convex combination of two others
- “extreme point” is point that is unique optimum in some direction
Basic solutions:
- A constraint $ax \le b$ or $ax=b$ is tight or active if $ax=b$
- for $n$-dim LP, point is basic if (i) all equality constraints are tight and (ii) $n$ linearly independent constraints are tight.
- in other words, $x$ is at intersection of boundaries of $n$ linearly independent constraints
- note $x$ is therefore the unique intersection of these boundaries.
- a basic feasible solution is a solution that is basic and satisfies all constraints.
In fact, vertex, extreme point, bfs are equivalent.
- Proof left somewhat to reader.
Any standard form lp $\min cx,\ Ax=b,\ x\ge 0$ with opt has one at a BFS.
- Suppose opt $x$ is not at BFS
- Then less than $n$ tight constraints
- So at least one degree of freedom
- i.e, there is a (linear) subspace on which all those constraints are tight.
- In particular, some line through $x$ for which all these constraints are tight.
- Write as $x+\epsilon d$ for some vector direction $d$
- Since $x$ is feasible and other constraints not tight, $x+\epsilon d$ is feasible for small enough $\epsilon$.
- Consider moving along line. Objective value is $cx+\epsilon cd$.
- So for either positive or negative $\epsilon$, objective is nonincreasing, i.e. doesn't get worse.
- Since started at opt, must be no change at all---i.e., $cd=0$.
- So can move in either direction.
- In at least one direction, some $x_i$ is decreasing.
- Keep going till new constraint becomes tight (some $x_i=0$).
- Argument can be repeated until $n$ tight constraints, i.e. bfs
- Conclude: every standard form LP with an optimum has one at a bfs.
- canonical form has oddities: e.g. $\min 0x+1y \mid y \le 1$.
- but any bounded, feasible LP has BFS optimum
- generalize idea of moving without worsening objective until new constraint becomes tight.
Corollaries:
- Actually showed, if $x$ feasible, exists BFS with no worse objective.
- Note that in canconical form, might not have opt at BFS ($\min y$ over $(x,y)$ such that $0 \le x \le 1$).
- But this only happens if LP is unbounded
- In particular, if opt is unique, it is a bfs.
- More generally, for our proof above to “break”, the line we made through opt can't hit any constraint
- so feasible set contains an entire line
- so if polytope is feasible and “half bounded”, there is an opt
- standard form is half-bounded since positive orthant is.
Question:
- arbitary unbounded LP with optimum transforms to standard LP with optimum
- but standard LP with OPT has one at BFS
- where did the BFS come from that wasn't in original LP?
- consider $\min 0x+1y \mid y \ge 1$.
- $x$ is unbounded so no BFS
- conversion create $x^+$ and $x^-$, writes $x=x^+-x^-$ with $x^+,x^- \ge 0$
- this turns the point $x^+=x^-=0$, i.e. $x=0$, into a vertex!
Vertices and Extreme Points
Two other characterizations of corner.Vertex:
- “vertex” is point that is not a convex combination of two others
- BFS if-and-only-if vertex:
- if point is convex combo (not vertex), consider line through it
- all points on it feasible
- so don't have $n$ tight constraints
- conversely, if less than $n$ tight constraints, they define feasible subspace containing line through point
- so point is convex combo of points on line.
Extreme Point
- “extreme point” is point that is unique optimum in some direction
- Extreme point implies BFS
- if cannot move to any other opt, must have $n$ tight constraints.
- Conversely, BFS is extreme point
- BFS means feasible and total of $n$ tight constraints
- let $T$ be set of $x_i \ge 0$ constraints that are tight
- take objective $\sum_{i \in T} x_i$
- consider any other feasible point
- It's loose on some $i \in T$
- so objective value $>0$
- so not optimal
- Thus, BFS is unique opt for this objective, i.e. extreme point
- This proof assumes standard form, but easily generalizes.
Shows output is polynomial size:
- Let $A'$ and correspoinding $b'$ be $n$ tight constraints (rows) at opt
- Then opt is (unique) solution to $A'x=b'$
- We saw that such an inverse is represented in polynomial size in input
- (So, at least weakly polynomial algorithms seem possible)
Yields first algorithm for LP: try all bfs.
- How many are there?
- just choose $n$ tight constraints out of $m$, check feasibility and objective
- Upper bound $\binom{m}{n}$
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.
- decision version of LP: is there a solution with opt$>k$?
- this is in NP, since can exhibit a solution (we showed poly size output)
- is it in coNP? Ie, can we prove there is no solution with opt$>k$? (this would give an optimality test)