[an error occurred while processing this directive]


Kungl Tekniska högskolan / Optimization and Systems Theory /

[an error occurred while processing this directive]This is a printer-friendly version of http://www.math.kth.se/optsyst/forskning/forskarutbildning/SF3850/info.html

« [an error occurred while processing this directive]Back
 


SF3850 Numerical linear programming, 7.5cr

General information

This graduate course is primarily intended for graduate students in optimization and systems theory, or other graduate students with a good background in optimization.

Summary of contents

The course deals with theory and algorithms for linear programming problems (LP problems).

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.

Prerequisites

Suitable prerequisites are the courses SF2812 Applied linear optimization and DN2251 Applied numerical methods III, or similar knowledge.

Literature

The literature is a textbook, a set of articles and extract from textbooks. Below is a listing of these articles and books, where it is also indicated what parts are of significant importance.
[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.
Students are expected to have access to the textbook [13]. The book can for example be done directly from SIAM or you can access the book online via KTH.

Schedule

Twelve lectures will be given in the autumn of 2016.

First meeting Tuesday September 20, 2016, 13.15-15.00, in Room 3721, Lindstedtsvägen 25.

Examination

The examination is by five sets of homework assignments and an oral final exam.

Examiner

Anders Forsgren, room 3533, Lindstedtsvägen 25, tel. 790 71 27. E-mail: andersf@kth.se.

Optimization and Systems Theory, KTH
Anders Forsgren, andersf@kth.se