Publish on 11th November 2019
Category: Birds
0

Lecture 18 Linear Program Algorithms

Dual LP

Strong Duality: The two LP has the same optimal value.

The dual of dual LP is the primal LP.

Primal and Dual

Optimal Solution:x = (4, 3, 0)

Optimal Solution:y = (2.5, 0, 0.5)

Observation: If a primal constraint is not tight, then the dual variable is 0.

LP algorithms

Given a linear program, how do we find its optimal solution?Many different algorithmsSimplexEllipsoidInterior Point

Simplex Algorithm

Recall: geometric interpretationBasic Feasible Solution: A vertex in the polytope.Algebraic interpretation: Solution of n tight constraints.Claim: There is always an optimal basic feasible solution.

Simplex Algorithm [Dantzig1947]

Idea: Start from a basic feasible solution, follow an edge in the polytope.Algorithmically: follow an edge swap a constraint.Many ways to decide which constraint to swap.

Running time of Simplex algorithm

Each move takes polynomial time, but how many moves do we need?In the worst case can require 2nmoves.But in practice simplex is often very fast!Still used in many LP solvers.

Ellipsoid algorithm

First idea: finding a feasible solution finding optimal solution.

x

y

Finding a feasible solution

Running time of ellipsoid

Polynomial in the number of variables and constraints.Actual running time is a bit slow, often used for low dimensional problems.

Interior Point algorithms

Idea: Build barrier functions for constraints.Barrier: Reach infinity at boundary, but small when far from boundary.

x

y

Interior Point algorithms

Idea: First find the optimal solutionfor objective + all barrier functions.Gradually decrease the barrier functions to make the point closer to the actual optimal.

x

y

Running time for Interior point

Also polynomial in number of variables and constraints.Can be implemented efficiently in practice.Many recent developments in both theory and practice, becoming the method of choice in many LP solvers.

0

Embed

Upload

Lecture 10 Hashing - cs.duke.edu