CS5321 Numerical Optimization

Class: M7 M8 R6 at EECS 129 (Spring 2010)

Instructor: Che-Rung Lee

Office hours: Wednesday 10:00-12:00

TA: 馮冠中

Reference books

1. Applied Optimization with Matlab Programming, 2nd Ed, P. Venkataraman (Class page) (Companion site)
2. Numerical optimization, Jorge Nocedal and Stephen J. Wright (http://www.mcs.anl.gov/otc/Guide)
3. Afternotes on Numerical Analysis, G.W. Stewart link
4. Mathematical Optimization, MO
5. Linear and Nonlinear Programming, Stephen G. Nash and Ariela Sofer (1996, 2005)
6. Numerical Methods for Unconstrained Optimization and Nonlinear Equations, J. Dennis and R. Schnabel
7. Iterative Methods for Optimization by C. T. Kelley Matlab code

External links: Many useful notes/references can be found in the following links

• Convex Optimization Theory by Dimitri P. Bertsekas.
• Matlab introduction by Prof. Jang.
• Class webpage by Dianne P. O'Leary
• Convex optimization, semidefinie programming by Anthony So.
• Linear programming by W.W.Lin
• SVM, Large-scale Nonlinear Optimization by C.J. Lin.
• Last year's webpage

Prerequisites: Caculus and Linear Algebra

Announcement

• 2010/6/1:Homework 8. Due June 21.
• 2010/5/27:Project midterm report. due June 7.
• 2010/5/27:No office hours on 6/2.
• 2010/5/24:Homework 7. Due June 7.
• 2010/5/10:Project proposal due May 14.
• 2010/5/10:Homework 6. Due May 24.
• 2010/4/25:Homework 5. Due May 10.
• 2010/4/8: Homework 4 has been posed. Due April 26.
• 2010/4/15 and 2010/4/22: NO class
• 2010/3/29: Midterm on April 19, at EECS 129 (15:20-17:20)
  Close book, close note, but you can bring one A4 memo, double sided.
• 2010/3/27: Makeup class on April 10, at EECS431. (9:00am-12:00pm).
• 2010/3/25: Homework 3 has been posed. Due April 12.
• 2010/3/9: Homework 2 has been posed. Due March 25.
• 2010/3/1: Homework 1 has been posed. Due March 11.
• 2010/2/23: Matlab tutiral link is posed.

Lecture:

Schedule	Topic	Reference
2/22	Introduction/Example	introduction
Unit 1. One-Dimensional Problem
2/25	Basic optimization algorithm	MO 2.1 and 2.2
3/1	Newton's method/Secant method	Stewart's afternote Lec01,Lec02 Dennis and Schnabel 2.1-2.5
3/4	Interpolation method	Stewart's afternote Lec04,Lec18
Unit 2. Unconstrained Optimization Problem
3/8	Review of multivariable calculus	An interesting website
3/11	Steepest descent method	N&W chap 3 MO 2.4
3/15	Newton's method	N&W chap 3 MO 2.5 Stewart's afternote Lec12
3/18	Modified Newton's method	N&W chap 3 Modified Cholesky Algorithms: A Catalog with New Approaches by Fang, Haw-ren and O'Leary, Dianne P.
3/22,3/25	Line search method	N&W chap 3
3/29,4/8	Quasi-Newton method
4/10,4/12	Makeup class: Conjugate gradient method/Truncated Newton method	An Introduction to the Conjugate Gradient Method Without the Agonizing Pain by Jonathan Richard Shewchuk.
4/12	Code for the line search algorithm.	link, slide
4/19	Midterm
Unit 3. Linear Programming
4/26	Linear programming problem definition.	Linear Programming: A Concise Introduction by Thomas S. Ferguson 線性規劃(Linear Programming) by 方述誠
4/29	Duality and complementrtity condition.
5/3, 5/6	The simplex method.
Unit 4. Constrained Optimization Problem
5/10	The KKT conditions	N&W chap 12
5/13	The second order condition	N&W chap 12 Computing null space by Khan Academy
5/17	Duality	N&W chap 12
5/20, 5/24	Quadratic programming (Active set method)	N&W chap 15 A QP Page
5/27,5/31	Gradient projection method	N&W chap 15
5/31	Sequential quadratic programming (SQP)	N&W chap 15 Sequential Quadratic Programming by Paul T. Boggs , Jon W. Tolle
6/3	Penalty and augmented Largrangian methods	N&W chap 15
6/7, 6/10	Interior point method.	N&W chap 15 Interior Methods for Nonlinear Optimization by Anders Forsgren, Philip E. Gill, and Margaret H. Wright
6/14, 6/17	Filter method	N&W chap 15 Nonlinear programming without a penalty function by Roger Fletcher and Sven Leyffer On the Global Convergence of a Filter-SQP Algorithm by Roger Fletcher, Sven Leyffer, and Philippe L. Toint (2006 SIAM Awards Lagrange Prize)
6/21	Final

Course requirements

• Attendance (10%)
• Homework (40%)
  • Homework 1. Due March 11.
  • Homework 2. Due March 25. Partial soultion.
  • Homework 3. Due April 12. Partial soultion.
  • Homework 4. Due April 26. Partial soultion.
  • Homework 5. Due May 10. Partial soultion.
  • Homework 6. Due May 24. Partial soultion.
  • Homework 7. Due June 7.
  • Homework 8. Due June 21.
• Midterm (20%)
  • April 19 at EECS 129 (15:20-17:20). Close book, close note, but allow one A4 memo, double sided.
  • Partial soultion.
• Final/Project (30%)

Last update: 2010/5/23