From the 1940s untils about thirty years ago the simplex method, developed by Dantzig, was the only practically used method for solving LP problems. Khachian had in the late 1970s presented the polynomial ellipsoid method, but it had not been successful in practice.
When Karmarkar presented his interior method in 1984, all this changed. This method was polynomial and also claimed to be superior to the simplex method in practice.
Karmarkar's method lead to an "explosion" within the area of linear programming. Gill et. al. soon showed that Karmarkar's method was equivalent to a logarithmic barrier method, and the development of new interior methods was rapid.
This "competition" between the simplex method and interior methods has lead to significant improvement in both types of method over the last decade. The purpose of this course is to reflect this development. Some more advanced aspects of the simplex method are included, e.g., steepest edge, partial pricing, and of the interior-point methods e.g., primal-dual methods, affine-scaling methods, predictor-corrector methods. In particular, we try to understand how the different methods work.
| [1] | V. Chvátal. Linear Programming. W. H. Freeman and Company, New York, 1983. (Chapters 24 and 25). |
| [2] | J. J. Forrest and D. Goldfarb. Steepest-edge simplex algorithms for linear programming. Mathematical Programming, 57:341-374, 1992. |
| [3] | A. Forsgren, An elementary proof of optimality conditions for linear programming. Report TRITA-MAT-2008-OS6, Department of Mathematics, Royal Institute of Technology, 2008. |
| [4] | A. Forsgren, P. E. Gill and M. H. Wright, Interior methods for nonlinear optimization. SIAM Review 44 (2002), 525-597. (Basic ideas.) |
| [5] | P. E. Gill, W. Murray, M. A. Saunders, J. Tomlin, and M. H. Wright. On projected Newton methods for linear programming and an equivalence to Karmarkar's projective method. Mathematical Programming, 36:183-209, 1986. |
| [6] | P. E. Gill, W. Murray, and M. H. Wright. Numerical Linear Algebra and Optimization, volume 1. Addison-Wesley Publishing Company, Redwood City, 1991. (Reference book on linear programming. Not required.) |
| [7] | D. Goldfarb and J. K. Reid. A practicable steepest-edge simplex algorithm. Mathematical Programming, 12:361-371, 1977. |
| [8] | D. Goldfarb and M. J. Todd. Linear programming. In G. L. Nemhauser, A. H. G. Rinnooy Kan, and M. J. Todd, editors, Handbooks in Operations Research and Management Science, volume 1. Optimization, chapter 2, pages 73-170. North Holland, Amsterdam, New York, Oxford and Tokyo, 1989. (Reference article on linear programming. Not required.) |
| [9] | N. Karmarkar. A new polynomial-time algorithm for linear programming. Combinatorica, 4:373-395, 1984. (Basic ideas.) |
| [10] | S. Mehrotra. On finding a vertex solution using interior point methods. Linear Algebra and its Applications, 152:233-253, 1991. (Section 4, basic ideas.) |
| [11] | S. Mehrotra. On the implementation of a primal-dual method. SIAM J. on Optimization, 2:575-601, 1992. (Sections 1 and 2, basic ideas.) |
| [12] | I. Griva, S. G. Nash and A. Sofer, Linear and nonlinear programming, SIAM, 2009. ISBN: 978-0-898716-61-0. (Reference book on linear programming. Not required.) |
| [13] | S. J. Wright. Primal-dual interior-point methods. SIAM, Philadelphia, USA, 1997. ISBN 0-89871-382-X. |
First meeting Tuesday September 20, 2016, 13.15-15.00, in Room 3721, Lindstedtsvägen 25.
   |
[an error occurred while processing this directive]
Optimization and Systems Theory, KTH Anders Forsgren, andersf@kth.se [an error occurred while processing this directive] [an error occurred while processing this directive] 2016-09-28 |