MATH 519/619 Optimization (Spring quarter 2005)

Instructor

Miguel Á. Carreira-Perpiñán
Assistant professor
Dept. of Computer Science & Electrical Engineering
OGI School of Science & Engineering / OHSU
miguel-[at]-cse.ogi.edu; 503-7481455
Office: Bronson Creek Building 150J

Office hours: by appointment (call or e-mail, including [MATH519] in the subject).

Classes: Tuesdays and Thursdays 5:30-6:50pm in classroom 560, Jack Murdock Building (number 6 in the map).

Course web page: http://www.cse.ogi.edu/~miguel/teaching/math519.html

Course description

Optimization problems arise in multiple areas of science, engineering and business. This course introduces numerical methods for continuous optimization, focusing on practical methods. The course will cover derivative-based methods for constrained and unconstrained multivariate optimization, including line-search and trust-region strategies; conjugate-gradient, Newton and quasi-Newton methods; linear programming (simplex and interior-point methods); quadratic programming; penalty, barrier and augmented Lagrangian methods; and sequential quadratic programming. The primary programming tool for this course is Matlab.

Prerequisites: undergraduate courses in linear algebra and multivariate calculus. Basic concepts will be briefly reviewed during the course.

Textbook

Required textbook (get the errata):

• Jorge Nocedal and Stephen J. Wright: Numerical Optimization. Springer-Verlag, 1999.

Other recommended books:

• R. Fletcher: Practical Methods of Optimization. Wiley, 1987.
• David G. Luenberger: Introduction to Linear and Nonlinear Programming, 2nd ed. Addison Wesley, 1984.
• Stephen Boyd and Lieven Vandenberghe: Convex Optimization. Cambridge University Press, 2004. Available online.
• W. H. Press, S. A. Teukolsky, W. T. Vetterling and B. P. Flannery: Numerical Recipes in C: The Art of Scientific Computing, 2nd ed., chapter 10. Cambridge University Press, 1992. Available online.

All are on reserve in the OGI Library.

Syllabus

• Introduction (ch. 1: all)
• Unconstrained optimization
  • Mathematical criteria (ch. 2: all; skip R-rates of convergence)
  • Line search methods (ch. 3: pp. 35-55; skip proofs in sec. 3.3)
  • Trust-region methods (ch. 4: pp. 65-69, 77-79)
  • Conjugate gradient methods (ch. 5: pp. 101-117, 120-122; skim 112-117)
  • Practical Newton methods (ch. 6: skim pp. 135-142)
  • Quasi-Newton methods (ch. 8: pp. 193-200)
  • Nonlinear least-squares problems (ch. 10: pp. 251-264; skip proofs)
  • Nonlinear equations (ch. 11: skim it)
• Constrained optimization
  • Mathematical criteria (ch. 12: pp. 315-331, 342-348).
  • Linear programming: the simplex method (ch. 13: pp. 364-378 and 391-392; skip proofs in sec. 13.2)
  • Linear programming: interior-point methods (ch. 14: pp. 395-402, skim 402-411)
  • Fundamentals of algorithms for nonlinear constrained optimization (ch. 15: all)
  • Quadratic programming (ch. 16: 441-447, 453-459, 462, 464-467, 476-484)
  • Penalty, barrier and augmented Lagrangian methods (ch. 17: all; skip proofs; skim pp. 521-523)
  • Sequential quadratic programming (ch. 18: pp. 529-534)

Handouts and assignments

• Some Matlab code to plot contours of functions, etc.
• The notes to accompany the texbook. Please bring the corresponding part to each class.
• Homework #1 (covering chapters 1-4 from the book) is due April 14 at the end of the class; solutions #1
• Homework #2 (covering chapters 5, 6, 8, 10 from the book) is due April 28 at the end of the class; solutions #2
• Project #1 (reviewing a paper) is due May 5 at the end of the class
• Homework #3 (covering chapters 12-15 from the book) is due May 19 at the end of the class; solutions #3
• Homework #4 (covering chapters 16-18 from the book) is due June 2 at the beginning of the class; solutions #4
• Project #2 (implementing the quadratic-penalty method for constrained optimization problems) is due June 13

Course grading

One third each of these:

• Homework: exercises (mainly from the textbook) of two types, pencil-and-paper and Matlab programming. For programming exercises, email me a .tar.gz or .zip file containing your code (which should include succinct comments) and a README file that explains how your results can be reproduced. For example, the README file can be a commented Matlab script that sets up the data and calls your code.
• Two projects (I will accept suggestions for these):
  • Programming an optimization method for some problem
  • Reviewing a research paper related to optimization
• Exam: in-class, consisting of problems and conceptual questions

Optimization links

• Demos:
  • Several optimization methods
  • Lagrange multipliers in 2D with one equality constraint
• NEOS Guide: information about most areas of optimization
• Optimization Online: a repository of eprints about optimization
• Matlab Optimization Toolbox. You can see some demos by running Matlab from an OGI PC and typing demo toolbox optimization in the command window. But note that you will be writing your own code, rather than using the Toolbox.
• Tutorials and books
• Matrix identities (handy formulas for matrix derivatives, inverses, etc.):
  • Matrix calculus from Mike Brookes' Matrix Reference Manual
  • Matrix cookbook

Matlab tutorials

If you have never used Matlab, there are many online tutorials, for example:

• University of Florida
• University of New Hampshire
• US Naval Academy
• Or Google matlab tutorial

OHSU | OGI | Dept. of CSEE | Adaptive Systems Group | MACP's Home Page