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

Other recommended books:

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

## Matlab tutorials

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