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?
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”
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.
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!
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.
Quest for nonexponential algorithm: start at an easier place: how decide if a solution 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)