Linear Programming

The problem of maximizing a linear function over a convex polyhedron, also known as Operations Research, Optimization Theory, or Convex Optimization Theory. It can be solved using the Simplex Method (Wood and Dantzig 1949, Dantzig 1949) which runs along Edges of the visualization solid to find the best answer.

In 1979, L. G. Khachian found a ${\mathcal O}(x^5)$ Polynomial-time Algorithm. A much more efficient Polynomial-time Algorithm was found by Karmarkar (1984). This method goes through the middle of the solid and then transforms and warps, and offers many advantages over the simplex method.

See also Criss-Cross Method, Ellipsoidal Calculus, Kuhn-Tucker Theorem, Lagrange Multiplier, Vertex Enumeration

References

Linear Programming

Bellman, R. and Kalaba, R. Dynamic Programming and Modern Control Theory. New York: Academic Press, 1965.

Dantzig, G. B. ``Programming of Interdependent Activities. II. Mathematical Model.'' Econometrica 17, 200-211, 1949.

Dantzig, G. B. Linear Programming and Extensions. Princeton, NJ: Princeton University Press, 1963.

Greenberg, H. J. ``Mathematical Programming Glossary.''
http://www-math.cudenver.edu/~hgreenbe/glossary/glossary.html.

Karloff, H. Linear Programming. Boston, MA: Birkhäuser, 1991.

Karmarkar, N. ``A New Polynomial-Time Algorithm for Linear Programming.'' Combinatorica 4, 373-395, 1984.

Pappas, T. ``Projective Geometry & Linear Programming.'' The Joy of Mathematics. San Carlos, CA: Wide World Publ./Tetra, pp. 216-217, 1989.

Press, W. H.; Flannery, B. P.; Teukolsky, S. A.; and Vetterling, W. T. ``Linear Programming and the Simplex Method.'' §10.8 in Numerical Recipes in FORTRAN: The Art of Scientific Computing, 2nd ed. Cambridge, England: Cambridge University Press, pp. 423-436, 1992.

Sultan, A. Linear Programming: An Introduction with Applications. San Diego, CA: Academic Press, 1993.

Tokhomirov, V. M. ``The Evolution of Methods of Convex Optimization.'' Amer. Math. Monthly 103, 65-71, 1996.

Wood, M. K. and Dantzig, G. B. ``Programming of Interdependent Activities. I. General Discussion.'' Econometrica 17, 193-199, 1949.

Yudin, D. B. and Nemirovsky, A. S. Problem Complexity and Method Efficiency in Optimization. New York: Wiley, 1983.