AMSC 607 / CMSC 764 Advanced Numerical Optimization

Fall 2006


Dianne P. O'Leary

oleary@cs.umd.edu

When and Where: TuTh......11:00am-12:15pm (CSI 3120) (CSI is the Computer Science Classroom building, attached to A.V. Williams and behind the Wind Tunnel.)

Office Hours: Tuesday 8:45-9:15, Thursday 8:00-9:15, Friday 9-10, and by appointment, in AVW 3271.

New: End of semester information:

  • New: Course grades
  • Office hours:
  • I'll keep regular office hours through Friday, December 15.
  • I'll keep office hours 1-2 on Tuesday December 19, in case you have questions or want to pick up your last homework.
  • If you want to see me later in that week, we can make an appointment.
  • If you want to pick up any of your papers after that, stop by. I won't discard them until May.
  • Grades:
  • I hope to finish grading by noon on December 19.
  • I will send comments on your project via email.
  • When you receive that email, check this website for course grades.
  • Related courses:
  • Andre Tits' course next semester: ENEE769F Advanced Topics in Controls: Convex Optimization
  • Ricardo Nochetto's course next semester: AMSC 612 Numerical Methods for PDEs
  • My course next Fall: AMSC 600/CMSC 760, Advanced Numerical Linear Algebra (sparse matrix computations)

    • Teaching Assistant: Geping Liu (geping@math.umd.edu)
    Office hours Tuesday and Thursday 3:00-5:00, AVW 3457.

    Textbooks:

  • Sections III and IV of Linear and Nonlinear Programming by Stephen G. Nash and Ariela Sofer, McGraw-Hill.
    ISBN-007-046065-5 or ISBN: 0071145370. (The book is currently under revision.) You can look for a used copy on the internet if you prefer.
  • "Lecture Notes on Interior Point Polynomial Time Methods in Convex Programming" by Arkadi Nemirovski, Spring 2004.

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

    • Grading: Homework plus a project. No in-class quizzes or exams.

  • Course Information and Syllabus
  • Background information: Notes on error analysis: postscript
  • UMCP Code of Academic Integrity
  • Survival Guide for Optimization
  • Optimization at Maryland
  • Information about computer accounts. I have requested accounts on GRACE for each of you. For your assignments, you may use GRACE or any other machine with Matlab access.
  • Information from the last time the course was offered.

    • Lecture notes:

  • Introduction
  • Unconstrained Optimization, Part 1 Basics and Newton's Method
  • Unconstrained Optimization, Part 2 Alternatives to Newton's Method
  • Constrained Optimization, Part 1 Basics
  • Constrained Optimization, Part 2 Feasible Direction Methods
  • Constrained Optimization, Part 3 Barrier and Penalty Methods
  • Constrained Optimization, Part 4 Interior Point Methods for Linear Programming
  • Constrained Optimization, Part 5 Interior Point Methods for Nonlinear Programming
  • Lecture slides for Interior Point Polynomial Time Methods in Convex Programming by Arkadi Nemirovski
  • New: Notes for Unit 4: Special Topics
  • Part 1 Nonlinear Least Squares and Data Fitting pdf
  • Part 2 Large Scale Problems pdf
    Matlab code to demonstrate matrix reorderings
  • Part 3 Global Optimization pdf

    • Homework:

  • Homework 1:
  • The homework, due September 28 at 2pm (late penalty begins at 2:01) Note that the pdf problem number is 10.17, not 10.16.
  • cvsrch.m
  • cstep.m
  • Frequently asked questions about the homework
  • Comments about the solution
  • Sample programs, by Geping Liu The 3-d graphs, not required for the assignment, are quite interesting. They run fine on his machine but crash on mine.
  • Homework 2:
  • The homework, due October 17, 2pm.
  • Frequently asked questions about the homework
  • Partial answers, Problems 1, 2, 5, 6, 7
  • Partial answers, Problems 3, 4
  • feasibleDircMin.m by Geping Liu (Corrected 10-30-06)
  • Homework 3:
  • The homework, due November 2, 2pm.
  • Frequently asked questions about the homework
  • The test problem (This .mat file is good for Matlab 7.x, but not version 6.x.) Let me know by October 29 if this doesn't work for you.
  • Geping Liu's solution
  • New: Homework 4:
  • The homework, due December 14, noon.
  • Olena Shevchenko (Department of Mathematics and Statistics, University of Maryland at Baltimore County)
    Title: Some Aspects of the Theory of Long-Step Interior Point Methods beyond Symmetric Cone Programming
    slides
  • Information about the term project, due December 14, noon. New: If your project uses a software package written by someone else, please include a file named README that tells me what files you wrote and what files you modified.

    SDP Resources