|
|
MIT Electrical Engineering and Computer Science
Spring 2002 Catalogue Supplement |
L MW2:30-4, Room 36-155
Professor Dimitri Bertsekas, Room 35-210, 3-7267
Prereq.: a course in linear algebra and real analysis
3-0-9
CONVEX ANALYSIS AND OPTIMIZATION H-LEVEL (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 convexity, Lagrange multipliers, and duality. They include a detailed coverage of the theory of convex sets and functions, Lagrange multiplier theory, Lagrange and Fenchel duality, and Lagrangean relaxation and nondifferentiable optimization.
Mathematical background: Review of linear algebra and analysis.
Convex analysis: Convex sets and functions, relative interior, directions of recession, separating hyperplane theorems, applications to convex optimization and saddle point problems, polyhedral convexity, subgradients, nonsmooth analysis.
Lagrange multiplier theory: Enhanced Fritz-John theory, Lagrange multiplier theorems, pseudonormality, constraint qualifications, sensitivity, exact penalty functions.
Lagrange duality theory: Geometric view of duality, weak duality, strong duality theorems.
Fenchel duality theory: Convex conjugacy and duality, primal and dual function duality, exact penalty functions.
Lagrangian relaxation and large-scale decomposition: Solution of network, discrete, and combinatorial problems via duality and nondifferentiable optimization.
Nondifferentiable optimization and subgradient methods: Classical subgradient and cutting plane methods, serial and parallel incremental subgradient methods, space dilation methods, bundle methods. Application in Lagrangian relaxation.
Textbook: A fairly complete set of lecture notes.
Instructor: Prof. D. P. Bertsekas, 35-210, X3-7267, dimitrib@mit.edu. http://web.mit.edu/dimitrib/www/home.html