Nonlinear Optimization I 553.761
TTh 4:30pm - 5:45pm, ONLINE VIA ZOOM
Zoom link : Check Blackboard for passcode protected Zoom link.
Instructor : Amitabh Basu
Office Hours : Wednesday 6:30 -- 8:00pm, or email for appointment. Office Hours will be via Zoom. See Blackboard for a passcode protected Zoom link to my virtual office.
Email : basu [dot] amitabh [at] jhu [dot] edu
Teaching Assistant : Dai-Ni Hsieh, Ao Sun and Hongyi Jiang will be the TAs for our class.
Dai-Ni's email is dnhsieh [at] jhu [dot] edu.
Ao's email is asun17 [at] jhu [dot] edu.
Hongyi's email is hjiang32 [at] jhu [dot] edu.
Dai-Ni's office hours will be on Fridays 2:00 -- 3:00pm. See Blackboard for a passcode protected Zoom link to Dai-Ni's office hours.
Ao's office hours will be on Thursdays 8:00 -- 9:00pm. See Blackboard for a passcode protected Zoom link to Ao's office hours.
Hongyi will not have office hours.
Notes/Texts : I will use lecture slides prepared by Daniel P. Robinson for the course. They will be periodically posted here.
Introduction. Slides without "Notes".
Background and basics. Slides without "Notes". Annotations from Sept 1. Annotations from Sept 3. MATLAB demo file
Optimality conditions. Slides without "Notes". Annotations from Sept 3.
Newton's method. Slides without "Notes". Annotations from Sept 8. MATLAB demo file
Convexity. Slides without "Notes". Annotations from Sept 10.
Line Search Methods. Slides without "Notes". Annotations from Sept 15. Annotations from Sept 17. Annotations from Sept 22. Annotations from Sept 24.
In the figure on Slide 59, the "beta" should be an "eta". I am unable to modify the figure because it was made with old software. So I am alerting everyone here.
Conjugate Gradient. Whiteboard from Sept 29. Whiteboard from Oct 1.
Trust Region Methods. Slides without "Notes". Annotations from Oct 6. Annotations from Oct 8.
Least Squares. Slides without "Notes". Whiteboard from Oct 15. Whiteboard from Oct 20.
Smooth Convex Optimization. Whiteboard from Oct 27. Whiteboard from Oct 29.
Nonsmooth Convex Optimization: Section 4.1 from Notes on Convexity. Whiteboard from Nov 3.
Stochastic Gradient Descent. Whiteboard from Nov 3. Whiteboard from Nov 5. Whiteboard from Nov 10. Whiteboard from Nov 12 (Random coordinate minimization).
Coordinate Minimization. Slides without "Notes". Annotations from Nov 17.
Second Order Methods. Slides without "Notes". Annotations from Nov 19. Annotations from Dec 1. Annotations from Dec 3.
Linear Programming. Annotations from Dec 3.
Other useful textbooks and resources
- J. Nocedal and S. Wright, Numerical Optimization, Second Edition, Springer, (2006)
- A. R. Conn, N.I.M Gould, and Ph. L. Toint, Trust Region Methods, SIAM, Philadelphia, PA, (2000)
- R. Fletcher, Practical Methods of Optimization, 2nd Edition, Wiley, Chichester and New York, (1987)
- D. P. Bertsekas, Nonlinear Programming, Second Edition, Athena Scientific, Belmont, MA, (1999)
- A. Ruszcynski, Nonlinear Optimization, Princeton University Press, Princeton, NJ (2006)
- Y. Nesterov, Introductory Lectures on Convex Optimization: A Basic Course, Kluwer Academic Publishers, Norwell, MA, (2004)
Basic Numerical Analysis:
- S. D. Conte and C. de Boor, Elementary Numerical Analysis: an algorithmic approach, International Series in Pure and Applied Mathematics, McGraw-Hill Book Company, (1972).
Basic Real Analysis:
- Section 1 of these notes cover all the relevant real analysis needed for the course. The notes give a (very) concise summary of the relevant definitions and theorems we will need, with no proofs. I recommend the following text for proofs.
- Walter Rudin, Principles of Mathematical Analysis, McGraw-Hill New York, (1964).
Basic Linear Algebra:
- Gilbert Strang's video lectures.
- R. A. Horn and C. R. Johnson, Matrix Analysis, Cambridge University Press, (2012).
- Kenneth Hoffman and Ray Kunze, Linear Algebra, Prentice Hall, (1971).
Syllabus : The syllabus with list of topics to be covered is available HERE.
This course considers algorithms for solving various important nonlinear optimization problems and, in parallel, develops the supporting theory. Primary focus will be on unconstrained optimization. Topics will include: necessary and sufficient optimality conditions; gradient, Newton, and quasi-Newton based line-search, and trust-region methods; linear and nonlinear least squares problems; linear and nonlinear conjugate gradient methods; smooth unconstrained convex optimization; stochastic gradient descent. Selected special topics from: coordinate minimization, second-order methods, linear programming.
EXAM AND GRADING INFORMATION
There will be one take home Midterm and one take home Final exam. In addition, I will regularly (approx. every two week) post homework assigments here. Seriously attempting ALL the homework problems is imperative for your success in the class, and they will give an indication of the kind of problems on the tests.
- HW I.
Please hand in your solutions by the beginning of class on Thursday, September 17, 2020.
Midterm and Final Exam
- The Midterm will be made available
here on Blackboard before 12 noon, Friday, October 9, 2020 and will be due at the beginning of class on Tuesday, October 13, 2020. The syllabus for the midterm will be everything that was covered from the beginning of the semester to the lecture on Thursday, October 8, 2020.
- The Final Exam will be put up on Blackboard by 5pm on Thursday, December 10, 2020. You will have until 5pm on Thursday, December 17, 2020 to turn it in.
The syllabus for the final is all the material covered during the course of the semester.
- Your final grade will be based on the following weightage :
Homework - 35%
Midterm - 30%
Final - 35%
- Blackboard will be used to post the HW and exam grades. You should be able to access your grades there.