3 Linear programming

The problem

Minimize linear/ affine function over a polyhedron: ie subject to affine/ linear constraint functions.

Canonical form

$\overrightarrow{x}\in R^d$. $min{c}^{T}x:Ax\le b$.

Nonnegative optimization form

$min{c}^T{x}^{\prime }:A{x}^{\prime }\le b$, with $x^{\prime }=\left[\begin{array}{c}{x}^{+}{x}^{-}\end{array}\right]$; new constraints: $x^{\prime }\ge 0$, $x^{+}-x^{-}=0$.

Equality constrained form

Writable as $min{c}^{T}x:Ax=b;$x$\ge 0$, using slack variables.

Constraints and the polyhedron

Every constraint is a halfspace. Intersection of halfspaces is a polyhedron; this is the \textbf{feasable region}.

The solution

Want to find a point in the feasible region making the least angle/ inner product with $f$.

Vertex in feasible region

Consider minimizing $f^{T}x$ over a line segment (a, b): for any point in this segment, you have: $f^T(ta+(1-t)b)\le min\{f^{T}a,f^{T}b\}$; so sufficient to consider end points while trying to minimize $f^{T}x$ over any line segment in the feasible region. By induction, sufficient to consider vertices of the feasible polyhedron.

Pathological cases

$minx$, A is empty; and $min$x$:x\ge 50$: often ruled out by added resource constraints: $x$ allowed to be only so small.

Related problems

Linear fractional program

Minimize linear fractional function over a polyhedron. Actually quasi-convex programming, but reducible to LP. Can rewrite $mint:\frac{a^{T}x+b}{c^{T}x+d}\le t$ using linear constraints.

Similar is the case with generalized linear fractional program:\ $mint:(\underset{i}{max}\frac{a_i^{T}x+b_i}{c_i^{T}x+d_i})\le t$.

1, infty norm approximations

$\underset{x}{min}{\parallel Ax-b\parallel }_{\mathrm{\infty }}\equiv minc:Ax-b\le c1,Ax-b\ge -c1$.

\(\min_x \norm{Ax - b}1 \equiv \min c : Ax - b = t+ + t_-; t_- \leq 0; t_+ \geq 0; 1^{T} t_+ - 1^{T}t_- \leq c\). This tends to yield sparse solutions: consider the functioning of least angles regression to see why.

Similarly, can replace 1, $\mathrm{\infty }$ norm constraints in any LP.

Robust linear programming

Often, there is uncertainty in constraints like $a_i^{T}x\le b_i$.

Deterministic model

x must be feasible $\mathrm{\forall }{a}_i\in S$. If S is an ellipse, this can be handled using SOCP.

Stochastic model

Feasible $x$ must satisfy $Pr(a_i^{T}x\le b_i)\ge t$. If distribution is Gaussian, this can be handled using SOCP.

LP Algorithms

Exhaustive search alg

Find intersection of every set of d hyperplanes (constraints); see if it satisfies other constraints: $O((\genfrac{}{}{0ex}{}{n}{d}))$.

Simplex method

(Dantzig). Theoretically exponential, highly efficient in practice.

Interior point projective method

(Karmarkar) LP solvable in time \ $poly(n,d)$.