This course provides a rigorous up-to-date treatment of topics in
Continuous Optimization (Nonlinear Programming). This includes a
hands-on approach with exposure to existing software packages.
Instructor:
Professor Henry Wolkowicz,
MC 6065, ext. 5589, henry@orion.math.uwaterloo.ca
Office Hours:
-
Henry Wolkowicz, MC6065: M 12:30-1:30, R 3-4
Lectures:
Text:
References:
Additional References:
-
Practical Optimization,
P.E. Gill, W. Murray, M.H. Wright.
-
Numerical Methods for Unconstrained Optimization and
Nonlinear Equations, J.E. Dennis and R.B. Schnabel
-
Nonlinear Programming: theory and algorithms, M.S. Bazaraa, C.M. Shetty, Sherali
-
Linear and Nonlinear Programming, D.G. Luenberger, Second Edition
-
Nonlinear Programming, Peressini, Sullivan, Uhl
-
Practical Methods of Optimization, R. Fletcher
-
Mathematical Programming Methods, G, Zoutendijk
-
Nonlinear Programming, G.P. McCormick
-
Mathematical programming : theory and algorithms,
M. Minoux (QA402.5.M5613)
-
Optimization by Vector Space Methods, D.G. Luenberger
-
Convex Analysis, R.T. Rockafellar
-
Theory of Extremal Problems, A.D. Ioffe and V.M. Tihomirov
Home Page, C&O 466/666,
http://orion.math.uwaterloo.ca/~hwolkowi/henry/teaching/w98/666.w98/readme.html
Term Work:
will consist of homework problems
.
(See attached schedule of assignments.)
Final Exam:
A 3-hour exam, scheduled by the registrar.
(Please see the detailed course outline for topics covered during the
semester.)
Marking Scheme:
-
Homework............ 50%
-
Final Exam.......... 50%
- Major Topics
- Sub-topics
- Resources
for the different topics are included.
(These are included for your
interest. You are not responsible for these topics for the exams or
assignments. However, they are useful aids.)
-
Unconstrained Optimization ( Chapter 1, except for Section 1.9.)
-
Optimality Conditions
first and second order; proofs; convex case
-
Gradient Methods - Convergence
Steepest Descent; stepsize rules; rates of convergence; Armijo rule with
proof; concepts of sufficient decrease and gradient related; behaviour
on quadratic functions
-
Newton's Method and Variations
(outline of Conjugate Gradient, Quasi-Newton, and Trust Region Methods);
details of proof of convergence, with rates, for Newton's method;
steepest descent convergence on quadratics
-
Least Squares Problems
-
Optimization Over a Convex Set (Chapter 2, except for Sections 2.4 and
2.5.)
-
Optimality Conditions
-
Feasible Directions Methods
-
Lagrange Multiplier Theory (Chapter 3, except for Section 3.4.)
-
Necessary Conditions for Equality Constraints
-
Sufficient Conditions and Sensitivity Analysis
-
Inequality Constraints
-
Lagrange Multiplier Algorithms ( Chapter 4, except for parts of
Sections 4.2 and 4.3.)
-
Barrier and Interior Point Methods
-
Penalty and Augmented Lagrangian Methods
The Quadratic Penalty Function Method
-
Exact Penalty Methods - Sequential Quadratic Programming
-
Lagrangian Methods
-
Duality and Convex Programming (Chapter 5, the first three sections and
a selection from Section 5.4.)
-
The Dual Problem
Lagrange Multipliers, The Weak Duality Theorem
-
Strong Duality
-
Duality Methods (Chapter 6)
-
Nondifferentiable Optimization Methods
-
Lagrangian Relaxation
-
Nonlinear Programming Software
-
Homework #1 (Unconstrained Optimization)
Due: Thursday January 22
Reading
- Bertsekas, topics in Chapter 1 and Appendices A and B
Problems
- Bertsekas, pp16, 1.1.8 (Steiner's Problem)
- Bertsekas, 1.2.12
- Bertsekas, 1.3.5
- Bertsekas, 1.8.3
solutions Assignment 1, thanks to John MacPhail.
-
Homework #2 (Optimization Over a Convex Set)
Due: Tuesday February 10
Reading
- Bertsekas, topics in Chapter 2
Problems
- Bertsekas, 1.4.7 (Trust Regions)
- Bertsekas, 2.2.7 (Simplicial Decomposition)
- Bertsekas, 2.3.1 (Scaled Gradient Projection)
-
Homework #3 (Lagrange Multiplier Theory)
Due: Tuesday February 24
Reading
- Bertsekas, topics in Chapter 3
Problems
- Bertsekas, Pgs 187-188, 2.1.10 and 2.1.11(2nd order optimality)
- Bertsekas, Pg 245, 2.6.1 (affine scaling)
- Bertsekas, Pgs 270-271, 3.1.4 and 3.1.5 (Lagrange multipliers)
-
Homework #4 (Lagrange Multiplier Algorithms)
Due: Tuesday March 10
Reading
- Bertsekas, topics in Chapter 4
Problems
- Bertsekas, Page 327, 4.1.1.
- Bertsekas, Page 328, 4.1.6.
- Bertsekas, Page 359, 4.2.6.
- Bertsekas, Page 361, 4.2.9.
-
Homework #5
Due: Thursday April 2
Reading
- Bertsekas, topics in Chapters 5 and 6
Problems