Low-Dimensional Linear Programming
Presentation by: Marc Lebovitz
Classical LP: Simplex Algorithm
Pick vertex in feasible region.
Vertex is constrained by H2 and H4.
Relax one constraint of vertex (H4 here).
We are left with d-1 constraints active.
Move along H2 in the direction which maximizes the inner
product with the
Stop when hit another constraint.
Repeat steps 2-4: Relax a constraint and move along direction
increases the inner product with the objective function.
Halt when movement no longer increases the inner product
algorithm moves from vertex to vertex along the boundary of the
feasible region. It stops when it reaches the extreme
vertex with respect to the