AMSC 607 / CMSC 764 Advanced Numerical Optimization

Fall 2010


Dianne P. O'Leary

Textbooks:
No required texts. Any of the following books would be a good primary reference. We will make use of on-line resources for more advanced material, although "A Mathematical View of Interior-Point Methods in Convex Optimization" by James Renegar, SIAM Press, 2001 is an excellent reference for this material.

  • Numerical Optimization by Jorge Nocedal and Stephen J. Wright, Springer, 2006.
  • Linear and Nonlinear Optimization by Igor Griva, Stephen G. Nash, and Ariela Sofer, SIAM Press, 2009.
  • Linear and Nonlinear Programming by Stephen G. Nash and Ariela Sofer, McGraw-Hill 1996. This book is an out-of-print older edition of the book above. Inexpensive copies are available used.
  • Practical Methods of Optimization by Roger Fletcher, Wiley, 1987.

    • Purpose: An algorithmic approach to numerical optimization, constrained and unconstrained. Emphasis on practical methods with enough theory to make them work.

    Prerequisite: A course in linear algebra and a course in numerical analysis. (A previous course in optimization is NOT expected.)

    Topics:

  • Unconstrained Optimization (approx. 4 weeks)
  • Characterization of solutions to minimization problems.
  • Selection of appropriate algorithms.
  • Global optimization.
  • Constrained Optimization (approx. 8 weeks)
  • Feasible set methods and projection methods.
  • Construction of interior point methods for problems with linear and nonlinear constraints.
  • 2010 Course Information and Syllabus
  • Survival Guide for Optimization
  • UMCP Code of Academic Integrity
  • Background notes on error analysis
  • GRACE
  • Information about computer accounts. See also the additional pointers at the bottom of notes by Larry Herman. For your assignments, you may use GRACE or any other machine with Matlab access.
  • Accessing Matlab on the GRACE machines, with graphics. Helpful summary of things to know,of things to know, from a student.
  • Sources for Matlab information:
  • Official Matlab documentation
  • Matlab Primer: 39 pages of basic information
  • Timothy A. Davis, Kermit Sigmon, Matlab Primer, CRC Press 2005. A 200 page version of the above reference.
  • D. J. Higham and N. J. Higham, Matlab Guide, SIAM Press 2005.
  • Read the code samples on the website for a textbook that I wrote.
  • Information from the last time the course was offered.

    • Tentative Schedule for Fall 2010:

    The tentative plan is to assign 13 problems worth 20 points each. They will be grouped into 9 homework assignments, and your best 10 problems will count toward your grade. Clarification of the syllabus: You need to make an honest effort at 10 problems, not 13.

    01 Aug 31: 607 Prelim. Sep 2: 607 Unconstr.
    02 Sep 7: 607 Unconstr. HW 1 assigned Sep 9: 607 Unconstr.
    03 Sep 14: 607 Unconstr. HW 2 assigned Sep. 16: 607 Unconstr.
    04 Sep 21: 607 Unconstr. HW 3 assigned Sep 23: 607 Unconstr.
    05 Sep 28: 607 UnConstr. HW 4 assigned Sep 30: 607 Constr.
    06 Oct 5: 607 Constr. HW 5 assigned Oct 7: 607 Constr.
    07 Oct 12: 607 Constr. Term project info. Oct 14: 607 Constr.
    08 Oct 19: 607 Constr. HW 6 assigned Oct 21: 607 Constr.
    09 Oct 26: 607 Constr. HW 7 assigned Oct 28: 607 Constr.
    10 Nov 2: 607 Constr. HW 8 assigned Nov 4: 607 Constr.
    11 Nov 9: 607 Constr. HW 9 assigned Nov 11: Renegar notes
    12 Nov 16: Renegar / Constr. reduction Nov 18: Large scale
    13 Nov 23: Global Optimization Nov 25: Happy Thanksgiving!
    14 Nov 30: Proj. / Global Dec 2: Proj. Presentation
    15 Dec 7: Proj. Presentation Dec 9: Proj. Presentation
    Dec 13: 8-10am: 607 Final Exam.
    Dec 14: 11am: 607 Term project due.

    2010 Lecture notes:

  • Introduction
  • Unconstrained Optimization: Basics 09-20-10: p16: Replace "E-hat" by "E". p17: e_q is the q-th column of the identity matrix, and similarly for e_s.
  • An example of a good linesearch: cvsrch.m and cstep.m
  • plot_quadratics.m demo for "Three Easy Pictures" (sadly lacking documentation)
  • Unconstrained Optimization: Part 2
  • For more detail on linear conjugate gradients:
  • Some notes on conjugate gradients
  • cg1.m
  • Constrained Optimization: Basics
  • Constrained Optimization: Feasible Direction Methods
  • Constrained Optimization: Penalty and Barrier Methods
  • Constrained Optimization: Interior Point Methods
  • Renegar's LP IPM Convergence Analysis
  • Notes on Constraint Reduction in IPMs
  • Large Scale Constrained Optimization
  • Data fitting and least squares problems
  • Global Optimization

    • Information on the 2010 term project

    Homework and Exam:

  • Homework 1 Due Sept 14, before class begins. Hint on Homework 1
  • Homework 2 Due Sept 21, before class begins. The data is in hw2.m Correction: each part is worth 10 points, not 5. The correction is marked in green. You may use the FMG code from the paper, as long as you give the authors full credit in your documentation, and add documentation as specified in the problem.
  • Homework 3 Due Sept 28, before class begins. The constraint p^T p = delta should be an inequality: p^T p less than or equal to delta, since it is a trust region. Therefore, as delta increases, eventually the constraint is irrelevant: the minimizer is the same with or without it. Also note that there is no closed form solution for delta in terms of gamma, or gamma in terms of delta.
  • Homework 4 Due Oct 5, before class begins.
  • Homework 5 Due Oct 12, before class begins. The "KKT conditions" are just the 1st order necessary conditions for optimality, found at the bottom of p. 11 of the lecture notes discussed in class today, with special cases discussed earlier in the notes.
  • Homework 6 Due Oct 26, before class begins. Here is an (undocumented) test problem generator to use once your program works on the small example.

  • Homework 7 Due Nov 2, before class begins. In the hint for problem 10, change the ">" sign to ">=". 11-01-10 In 10a, for the f-hat case it is enough to assume that ax+b>0.
  • Homework 8 Due Nov 9, before class begins. In 11b, the max is over y and z, not just y.
  • Homework 9 Due Nov 16, before class begins. Hint. In 12b or 13b, if you end up with a dual problem instead of a primal, that is ok. You still have definitions of all of the data matrices and vectors.
  • Final exam and Solution

    • CourseEvalUM Fall 2010: "Your participation in the evaluation of courses through CourseEvalUM is a responsibility you hold as a student member of our academic community. Your feedback is confidential and important to the improvement of teaching and learning at the University as well as to the tenure and promotion process. CourseEvalUM will be open for you to complete your evaluations for fall semester courses in December. Please go directly to www.courseevalum.umd.edu to complete your evaluations. By completing all of your evaluations each semester, you will have the privilege of accessing online, at Testudo, the evaluation reports for the thousands of courses for which 70% or more students submitted their evaluations."