KTH /
Engineering Science
/
Mathematics
/
Optimization and Systems Theory
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 2013.
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.
|
