Neumann projektív geometrián alapuló, és Karmarkar projektív skálázású belsőpontos módszere
Abstract
John von Neumann was one of the most significant mathematicians of the 20th century, who built a bridge between pure and applied sciences. He had a tremendous impact on the development of mathematics, physics, economics, and computer science. He made outstanding contributions to the field of linear programming, which became fundamental in mathematical and economic planning. One of von Neumann's pioneering achievements was a method based on projective geometry, designed to solve the gravity center problem, which later became widely known through Karmarkar's algorithm. This algorithm was a precursor to the interior-point methods in linear programming. The article discusses these algorithms.
References
Iványi, A. (2005): Informatikai algoritmusok II, pp. 1-768. Budapest: ELTE Eötvös Kiadó.
Dantzig, G. B.-Thapa, M. N. (2006): Linear Programming 2. New York: Springer Science & Business Media.
Dantzig, G. B. (1991): Converting a Converging Algorithm into a Polynomial Bounded Algorithm, pp. 1-9. https://doi.org/10.21236/ADA234961
Dantzig, G. B. (1992): An epsilon-Precise Feasible Solution to a Linear Program with a Con-vexity Constraintc In: 1/epsilon2 Iterations Independent of Problem Size, pp. 1-18.
Epelman, M.-Freund, R. M. (2000): Condition number complexity of an elementary algorithm for computing a reliable solution of a conic linear system. Mathematical Programming, 88., (3.), pp. 451-485. https://doi.org/10.1007/s101070000136 https://doi.org/10.1007/s101070000136
Karmarkar, N. (1984): A new poly-nomial-time algorithm for linear programming. Combinatorica, 4., (4.), pp. 373-395. https://doi.org/10.1007/bf02579150. https://doi.org/10.1007/BF02579150
Schittkowski, K. (1987): More Test Examples for Nonlinear Programming Codes. Springer. https://doi.org/10.1007/978-3-642-61582-5
