`
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`

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.

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.

- 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)

- 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~~; solutions #1**April 14 at the end of the class** - Homework #2 (covering chapters 5, 6, 8, 10 from the book)
~~is due~~; solutions #2**April 28 at the end of the class** - 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~~; solutions #3**May 19 at the end of the class** - Homework #4 (covering chapters 16-18 from the book)
~~is due~~; solutions #4**June 2 at the beginning of the class** - Project #2 (implementing the quadratic-penalty method for constrained optimization problems)
~~is due~~**June 13**

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

- Demos:
- 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.):

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

Miguel A. Carreira-Perpinan Last modified: Sat Sep 3 16:05:45 PDT 2005

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