CSE260 Optimization (Spring semester 2008)

Instructor

Miguel Á. Carreira-Perpiñán
Assistant professor
Electrical Engineering and Computer Science
School of Engineering
University of California, Merced
mcarreira-perpinan-[at]-ucmerced.edu; 209-2284545
Office: 284, Science & Engineering Building

Office hours: by appointment (call or email, including [CSE260] in the subject).

TA: ???, ???-[at]-ucmerced.edu (SE290).

Lectures: Thursdays 9:30am-12:20pm (Linux Lab, SE138)

Lab class: Wednesdays 11:30am-2:20pm (Linux Lab, SE138)

Course web page: http://faculty.ucmerced.edu/mcarreira-perpinan/CSE260

Course description

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

Prerequisites: MATH 23, MATH 24, MATH 141 or equivalent (undergraduate courses in linear algebra and multivariate calculus). Basic concepts will be briefly reviewed during the course.

Textbook

Required textbook (get the errata and additional errata):

• Jorge Nocedal and Stephen J. Wright: Numerical Optimization, second ed. Springer-Verlag, 2006.

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.

If you want to refresh your knowledge of linear algebra and multivariate calculus, the following are helpful (any edition or similar book is fine):

• Seymour Lipschutz: Schaum's Outline of Linear Algebra. McGraw-Hill.
• Murray Spiegel: Schaum's Outline of Vector Analysis. McGraw-Hill.
• Frank Ayres: Schaum's Outline of Matrices. McGraw-Hill.
• Richard Bronson: Schaum's Outline of Matrix Operations. McGraw-Hill.
• Erwin Kreyszig: Advanced Engineering Mathematics. Wiley.
• Gilbert Strang: Introduction to Linear Algebra. Wellesley-Cambridge Press.
• Gilbert Strang: Linear Algebra and Its Applications. Brooks Cole.

Syllabus and required textbook reading

Before each class, you should have read the corresponding part of the textbook and the notes. I will teach the material in the order below (which is more or less the order in the book).

• Introduction (ch. 1: all) and math review (appendix A: skim it)
• Unconstrained optimization:
  • Fundamentals of unconstrained optimization (ch. 2: all)
  • Line search methods (ch. 3: pp. 30-49; skip proofs in sec. 3.3)
  • Trust-region methods (ch. 4: pp. 66-71)
  • Conjugate gradient methods (ch. 5: pp. 101-124)
  • Quasi-Newton methods (ch. 6: pp. 135-150)
  • Large-scale unconstrained optimization (ch. 7: pp. 164-170, 176-190)
  • Calculating derivatives (ch. 8: pp. 193-210)
  • Derivative-free optimization (ch. 9: pp. 220-225, 229-242)
  • Least-squares problems (ch. 10: pp. 245-259, 261-264; skip proofs)
  • Nonlinear equations (ch. 11: 270-276, 285-287, 296-302; skip proofs and skim the rest of the chapter)
• Constrained optimization:
  • Theory of constrained optimization (ch. 12: pp. 304-321, 330-337, 341-349)
  • Linear programming: the simplex method (ch. 13: pp. 355-372, 385-389; skip proofs in sec. 13.2)
  • Linear programming: interior-point methods (ch. 14: pp. 392-401, 407-411)
  • Fundamentals of algorithms for nonlinear constrained optimization (ch. 15: 421-437)
  • Quadratic programming (ch. 16: 448-454, 463-470, alg. 16.3, 475-477, 480-492)
  • Penalty and augmented Lagrangian methods (ch. 17: all)
  • Sequential quadratic programming (ch. 18: pp. 529-535)
  • Interior-point methods for nonlinear programming (ch. 19: pp. 563-577, 583-586)

Handouts and assignments

• Some Matlab code to plot contours of functions, etc.
• The notes and math review to accompany the textbook. Bring the corresponding part to each class.
• Homework (to do on your own, not graded):
  • Homework #1 (covering chapters 1-4 from the book); solutions #1 (available from Feb. 19)
  • Homework #2 (covering chapters 5, 6, 8, 10 from the book); solutions #2 (available from Mar. 3)
  • Homework #2a (covering chapters 7, 9, 11 from the book); solutions #2a (available from Mar. 20)
  • Homework #3 (covering chapters 12-15 from the book); solutions #3 (available from Apr. 21)
  • Homework #4 (covering chapters 16-18 from the book); solutions #4 (available from May 1)
• Projects (to be submitted and graded):
  • Project #1 (implementing unconstrained optimization methods) due March 31, in groups of 1 or 2 students
  • Project #2 (reviewing a paper) due March 14, individual (no groups)
  • Project #3 (implementing a constrained optimization method) due May 14, in groups of 1 or 2 students

Course grading

The course grading will be based on three projects and a final exam, as follows:

• Project 1 (15%): implementing a method for unconstrained optimization problems
• Project 2 (10%): reviewing a research paper related to optimization (I will accept suggestions for these)
• Project 3 (25%): implementing a method for constrained optimization problems
• Midterm exam (25%): in-class, closed-book, consisting of problems and conceptual questions
• Final exam (25%): as the midterm

While I encourage you to discuss your work with other students, the projects and the exam must be the result of your own work without collaboration.

I will also give homework exercises (mainly from the textbook) of two types, pencil-and-paper and Matlab programming. I will not ask you to solve them, i.e., they will not count towards your grade. I will give the solutions and solve some of the exercises in class. However, I strongly recommend that you try to solve all the exercises on your own.

Optimization links

• Demos:
  • Several optimization methods (UIUC)
  • Several numerical and optimization methods (Indian Institute of Science)
  • Lagrange multipliers in 2D with one equality constraint
• Matlab Optimization Toolbox. You may find useful to compare the textbook and the user's guide. You can see some demos by running Matlab and typing demo toolbox optimization in the command window. But note that you will be writing your own code, rather than using the Toolbox.
• NEOS Guide: information about most areas of optimization
• Optimization Online: a repository of eprints about optimization
• Mathematical Programming Glossary
• 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

Other links

• LaTeX documentation
• XEmacs (reference card).

UC Merced | EECS | MACP's Home Page