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, componentwise $\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$ plus size of number
• $m \times n$ matrix similar: $mn$ plus sizeof 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.
• 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)
• 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 \le 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.

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)