Editing John von Neumann (section)

=== Linear programming ===
Building on his results on matrix games and on his model of an expanding economy, von Neumann invented the theory of duality in linear programming when [[George Dantzig]] described his work in a few minutes, and an impatient von Neumann asked him to get to the point. Dantzig then listened dumbfounded while von Neumann provided an hourlong lecture on convex sets, fixed-point theory, and duality, conjecturing the equivalence between matrix games and linear programming.<ref>{{cite book | last=Dantzig | first=G. B. | author-link=George Dantzig | year=1983 | contribution=Reminiscences about the origins of linear programming. | title=Mathematical Programming The State of the Art: Bonn 1982 | editor1-last=Bachem | editor1-first=A. | editor2-last=Grötschel |editor2-first=M. | editor3-last=Korte | editor3-first=B. | location=Berlin, New York | publisher=Springer-Verlag | pages=78–86 | isbn=0387120823 | oclc=9556834}}</ref>

Later, von Neumann suggested a new method of [[linear programming]], using the homogeneous linear system of [[Paul Gordan]] (1873), which was later popularized by [[Karmarkar's algorithm]]. Von Neumann's method used a pivoting algorithm between [[simplex|simplices]], with the pivoting decision determined by a nonnegative [[least squares]] subproblem with a convexity constraint ([[Projection (linear algebra)#Orthogonal projections|projecting]] the zero-vector onto the [[convex hull]] of the active simplex). Von Neumann's algorithm was the first [[interior point method]] of linear programming.<ref name="George B 2003">{{cite book | last1 = Dantzig | first1 = George |author1-link=George Dantzig |last2=Thapa |first2=Mukund N. | title = Linear Programming : 2: Theory and Extensions | publisher = [[Springer Science+Business Media|Springer-Verlag]]| location = New York, NY | year = 2003| isbn = 978-1-4419-3140-5}}</ref>