6.854 Notes #11

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 constraintsLP 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 optimumgeneralize 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 directionExtreme 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)