|
|
MIT Electrical Engineering and Computer Science
Spring 2001 Catalogue Supplement |
MW 1-2:30, Room 36-372
Professor Dimitri Bertsekas, Room 35-210, 3-7267
Prereq.:
3-0-9
This is a research-oriented course that will focus selectively on a number of fundamental analytical and computational issues in (deterministic) optimization. Topics span a broad range from continuous to discrete optimization, but are connected through the recurring theme of Lagrange multipliers and duality. They include Lagrange multiplier theory, Lagrangean relaxation and nondifferentiable optimization, and auction algorithms for network and combinatorial problems.
(1) Mathematical background and convex analysis (5 lectures): Review of linear algebra and analysis. Convex sets and functions, separating hyperplane theorems, subgradients, nonsmooth analysis.
(2) Lagrange multiplier theory (3 lectures): Enhanced Fritz-John theory, Lagrange multiplier theorems, sensitivity.
(3) Duality theory (2 lectures): Geometric view of duality, strong duality theorems.
(4) Lagrangian relaxation and large-scale decomposition (3 lectures): Solution of network, discrete, and combinatorial problems via duality and nondifferentiable optimization.
(5) Nondifferentiable optimization and subgradient methods (5 lectures): Classical subgradient and cutting plane methods, serial and parallel incremental subgradient methods, space dilation methods, bundle methods. Application in Lagrangian relaxation.
(6) Auction algorithms for network and combinatorial optimization (5 lectures): Auction algorithms for assignment, extensions to network optimization (shortest path, max-flow, min-cost flow, convex cost network optimization), extensions to combinatorial auctions (multi-agent resource allocation, e-commerce, scheduling, etc).
Readings: Instructor's notes, journal papers, and two (optional) books:
(a) Nonlinear Programming: 2nd Edition, by Dimitri P. Bertsekas, Athena Scientific, 1999, (ISBN 1-886529-00-0)
(b) Network Optimization: Continuous and Discrete Models, by Dimitri P. Bertsekas, Athena Scientific, 1998, (ISBN 1-886529-02-7)
Instructor: Prof. D. P. Bertsekas, 35-210, X3-7267, dimitrib@mit.edu.