CS 726: Nonlinear Optimization I - Fall 2009 (Also ISyE, Stat, Math)

Schedule

  Lecture:     8:50 - 9:40 MWF, 1263 CS
               Start at 8:40 from Sep 9 to Oct 9
  Mailing list: compsci726-1-f09@lists.wisc.edu 
  Course URL: http://www.cs.wisc.edu/~cs726-1 

Instructor: Michael C. Ferris

  Office:       4381 CS
  Telephone:    262-4281
  E-mail:       ferris@cs.wisc.edu
                I will respond to the class mailing list, including
		your original message in most cases.
  Office Hours: 10:00 - 11:00 Mondays, 1:00 - 2:00 Wednesdays
  Class cancelled: October 12, 2009; October 23, 2009; November 18, 2009; December 2, 2009
 

Teaching Assistants:

Keith Langston

  E-mail:       langston@cs.wisc.edu
  Office:       5384 CS
  Office Hours: 4:00 - 5:00 Tuesdays, 3:00-4:00 Thursdays
 

Zhiting Xu

  E-mail:       zhiting@cs.wisc.edu
  Office:       3393 CS
  Office Hours: 1:00-2:00 Thursdays
 

General Course Information (http://www.cs.wisc.edu/~ferris/cs726.html)

Course Outline

Theory and algorithms for nonlinear optimization, focusing on unconstrained optimization. Line-search and trust-region methods; quasi-Newton methods; conjugate-gradient and limited-memory methods for large-scale problems; derivative-free optimization; algorithms for least-squares problems and nonlinear equations; gradient projection algorithms for bound-constrained problems; and simple penalty methods for nonlinearly constrained optimization.

• Continuous optimization paradigms
• Representative applications
• Mathematical background, including convex sets and functions
• Unconstrained optimization: Theory and algorithms
  • Optimality conditions
  • Gradient methods and Newton's method
  • Line search methods
  • Trust region methods
  • Quasi-Newton methods
• Derivative-Free optimization
  • Model-based methods
  • Pattern-search methods
• Large-scale unconstrained optimization:
  • Conjugate gradient methods (linear and nonlinear)
  • Limited-memory quasi-Newton methods
• Least-squares problems
  • Linear least squares: direct (normal equations and QR) and iterative methods (conjugate gradient applied to normal equations)
  • Nonlinear least squares: Gauss-Newton, Levenberg-Marquardt
• Nonlinear equations
  • Newton's method
  • Merit functions and line searches
• Optimization with bound constraints:
  • Projections and gradient projection algorithms
  • Enhancements of gradient projection using second-order information and quasi-Newton techniques.
• Constrained nonlinear programming algorithms
  • Constraint elimination
  • Penalty methods

  Required Text

  • I will use a set of notes specially prepared for this course. They will cover the first part of the Nocedal and Wright book.
  • Numerical Optimization, J. Nocedal and S.J. Wright, Springer Series in Operations Research, Springer-Verlag, New York, 2006 (2nd edition).

  Other References:

  • Nonlinear Optimization, Andrzej Ruszczynski, Princeton University Press, NJ 2006.
  • Nonlinear Programming, 2nd Edition, Dimitri Bertsekas, Athena Scientific, Belmont, MA 1999.
  • Practical Methods of Optimization, 2nd Edition, R. Fletcher, Wiley, 1987.
  • Practical Optimization, P. Gill, W. Murray and M. Wright, Academic Press, 1981.
  • Nonlinear Programming Theory and Algorithms , M. S. Bazaraa, H. D. Sherali and C. M. Shetty, Second Edition, Wiley, New York 1993.
  • The MATLAB PRIMER (Third Edition): An introduction to the basic commands and utilities that you may need in Matlab.

  Assignments and examinations

  • 1 Assignment per week approximately. Homework due at beginning of class one week after assigned unless otherwise noted.
  • Examinations are closed book, with the exception that 1 handwritten sheet (standard size paper) can be brought in to the examination.
  • No Midterm Examination
  • Final Examination - Tuesday, December 22 at 12:25 pm - 2:25 pm in xxxx.
  • Prereq: Familiarity with basic analysis (e.g. Math 521) and either Math 443 or 320, or consent of instructor

  Grading

  • Grades for the class will be available at Learn@UW. You will need to log-on, move to the course page, and use the "Grades" tab at the top of the page.
  • Approximately: 70% Homework, 30% Final
  • You may discuss the assignments with your classmates. However, you may not share any code, copy solution from another person, or carry out an assignment together. Discussion should only involve verbal communication. All assignments need to be written up entirely separately.

    Submitting someone else's work as your own is academic misconduct. Such cheating and plagiarism will be dealt with in accordance with University procedures (see the Academic Misconduct Guide for Students) .

  Handouts:

  • Eigenvalues, Singular Values, PSD, Strong Convexity, Lipschitz Continuity class handout 1.
  • anneal.m (Basic Simulated Annealing Code).
  • direct.m (DIRECT: divided rectangle code for optimization on a box).

  Programming Assignments and Homeworks

  All assignments need to be written up entirely separately. You may discuss the problems informally with others in the class, but the discussions must not include code or explicit solutions to any of the problems.
  • Most homeworks will be handed in either in hard copy or using the drop box facility of Learn@UW. The drop box menu is found in the top menu bar once you have logged into the system.
  • Homework 1 (due September 16); hard copy
  • Homework 2 (due September 25); hard copy
  • Homework 3 (due October 2) . Files mentioned in assignment are hwk3.m, obja.m, objb.m, objc.m, objd.m
  • Homework 4 (due October 16) . Files mentioned in assignment are hwk4.m, StepSize.m, mchol.m, geotest.m, obje.m
  • Homework 5 (due October 26) . Files mentioned in assignment are: hwk5.m, objampl.m, rosenbr.nl, brownal.nl, watson.nl, geodesic.nl, cragglvy.nl, woods.nl, allhwk5.zip Note that the zip archive contains all the files above and their corresponding "mod" files.
  • Homework 6 (due November 6) . Files mentioned in assignment are: hwk6.m, TNewton.m, objg.m Some other files that might be a bit more challenging for your code are given in geodesic4000.nl, vardim.nl, nondquar.nl.
  • Homework 7 (due November 13)
  • Homework 8 (due November 23, at class time) Files mentioned in assignment are: hwk8.m, objnls.m, resida.m, residb.m, residc.m, residd.m, penalty1.mod, penalty1.nl, penalty2.mod, penalty2.nl
  • Homework 9 (due Dec 4)

  ---

  CS Department Computing Information

  • Instructional Facilities
  • Hours
  • Locations
  • CS 1000 contains unix startup information and is available online.

  Miscellaneous

  • Archive of Class Mailing List. You will need to enter your cs account login and password to access this archive.
  • Computer Systems Laboratory FAQ
  • Instructional Facilities
  • Account Activation
  • Instructional Account Policies
  • Forwarding Email
  • Optimization at the University of Wisconsin
  • Courses related to 726
  • Linear Programming FAQ
  • NEOS Optimization Guide (Linear Programming)

  ---

  This page was updated August 6, 2009.

  ---