COMP SCI 726: Nonlinear Optimization I (Spring 2020)

Class is also listed as ISYE 726/MATH 726/STAT 726.

Instructor: Jelena Diakonikolas

Office: CS 4369

Email: jelena at cs dot wisc dot edu

Office hours: Monday after class (4-6pm), or by appointment

Teaching Assistant: Cheuk Yin (Eric) Lin

Office: CS 4376

Email: clin353 at wisc dot edu

Office hours: Wednesday 4-6pm, or by appointment

Grader: Abhirav Gholba

Email: abhirav dot gholba at wisc dot edu

Class Schedule

Update (please read!): Due to the ongoing COVID-19 outbreak, starting March 23, 2020, the lectures will be held remotely using BB Collaborate Ultra. Links to all sessions are posted on Canvas.

The class is scheduled Mon-Wed-Fri 2.30-3.45pm (75 min) and meets in CS 1257 (note the updated room number!). The planned number of classes is 28 (2 classes/week on average). The exact schedule will be posted here and may change; please keep checking this website for the most up-to-date information.

We may have additional 1-2 lectures to cover more advanced topics that are optional and will not be part of the final examination or homework assignments (to be discussed in class and decided based on interest).

(Tentative) Schedule:

• Week 1: Wed (1/22/20), no class on Fri
• Week 2: Mon (1/27/20), Wed (1/29/20), no class on Fri
• Week 3: Mon (2/3/20), Wed (2/5/20), Fri (2/7/20)
• Week 4: Mon (2/10/20), Wed (2/12/20), Fri (2/14/20)
• Week 5: Mon (2/17/20), Wed (2/19/20), Fri (2/21/20)
• Week 6: Mon (2/24/20), no classes on Wed and Fri
• Week 7: Mon (3/2/20), Wed (3/4/20), Fri (3/6/20)
• Week 8: Mon (3/9/20), midterm on Wed and no class on Fri
• Week 9: no classes: Spring break
• Week 10: Mon (3/23/20), Wed (3/25/20), no class on Fri
• Week 11: Mon (3/30/20), Wed (4/1/20), no class on Fri
• Week 12: Mon (4/6/20), Wed (4/8/20), no class on Fri
• Week 13: Mon (4/13/20), Wed (4/15/20), no class on Fri
• Week 14: Mon (4/20/20), Wed (4/22/20), Fri (4/24/20)

General Course Information

Prerequisites

Most of the class is theoretical and assumes mathematical maturity: you need to be comfortable with reading, understanding, and writing proofs. Basic background in linear algebra, real analysis, and probability is expected.

Some of the homework problems will require coding in Matlab, in part using the cvx package. Alternatively, you may opt for using Python, but we provide no support for this.

Textbook

J. Nocedal and S. J. Wright, Numerical Optimization, Second Edition, Springer, 2006.

Other resources

Some of the material that is not covered by the textbook will be covered by lecture notes, posted on Canvas.

Additional books and resources that you may find useful:

• Y. Nesterov, Lectures on Convex Optimization, Springer, 2018.
• A. Beck, First-order Methods in Optimization. Vol. 25. SIAM, 2017.
• S. Boyd, L. Vandenberghe, Convex Optimization, Cambridge University Press, 2004.
• H. Bauschke, P. Combettes, Convex Analysis and Monotone Operator Theory in Hilbert Spaces, Springer, 2017.
• D. P. Bertsekas, with A. Nedic and A. Ozdaglar, Convex Analysis and Optimization, Athena Scientific, 2003.
• Dmitriy Drusvyatskiy's course notes on convex analysis and optimization, 2019.

Course Outline

This is a tentative list of topics that will be covered in class. Most of the topics listed here will be covered, and some other topics may be added.

• Introduction: general continuous optimization background; convex sets; convex functions; convergence rates.
• Background on smooth unconstrained optimization: Taylor theorem and optimality conditions.
• First-order methods: gradient descent for convex and nonconvex optimization, line search methods, projected gradient descent, Nesterov acceleration for convex optimization, conjugate gradients, conditional gradients (Frank-Wolfe methods).
• Higher-order methods: Newton method, trust-region Newton and cubic regularization, quasi-Newton methods, limited-memory quasi-Newton.
• Stochastic optimization: basic methods and convergence, variance reduction.
• Coordinate descent methods: coordinate gradient descent and acceleration.
• Least squares and nonlinear equations: linear & nonlinear least squares.
• Derivative-free methods.

Course Load/Assessment

This is a graduate-level class that teaches fundamentals of nonlinear optimization, and, as such, will have a high load, requiring strong commitment to mastering the material. Your focus should not be on the grade -- it should be on learning. The instructor's point of view is that if you go through class without feeling challenged at all, then you are working below your potential. However, if the class becomes overwhelming and is causing you distress, you are encouraged to come talk to us, and we will look into possible accommodations.

All grades will be posted on Canvas. The information provided here is tentative and is subject to change.

Homework: There will be 6 homework assignments, accounting for ~30% of the grade. You may discuss problems with other students, but you need to declare it on your homework submission. Any discussion can be verbal only: you are required to work out and write the solutions on your own. Submitting someone else's work as your own constitutes academic misconduct. Academic honesty is taken very seriously in this class, and any breach of it will be treated according to the University Policy.

Homework assignments and solutions will be posted on Canvas.

Midterm: Scheduled for 3/11/2020 2.30-4.30PM in Rooms CS 1257 and CS 1263. Accounts for ~30% of the grade.

Final: Scheduled for 5/4/2020 2.45-4.45pm, room TBD. Accounts for ~40% of the grade.

Academic Policies

Academic Integrity

By enrolling in this course, each student assumes the responsibilities of an active participant in UW-Madison’s community of scholars in which everyone’s academic work and behavior are held to the highest academic integrity standards. Academic misconduct compromises the integrity of the university. Cheating, fabrication, plagiarism, unauthorized collaboration, and helping others commit these acts are examples of academic misconduct, which can result in disciplinary action. This includes but is not limited to failure on the assignment/course, disciplinary probation, or suspension. Substantial or repeated cases of misconduct will be forwarded to the Office of Student Conduct & Community Standards for additional review. [link]

Disability Accomodation

The University of Wisconsin-Madison supports the right of all enrolled students to a full and equal educational opportunity. The Americans with Disabilities Act (ADA), Wisconsin State Statute (36.12), and UW-Madison policy (Faculty Document 1071) require that students with disabilities be reasonably accommodated in instruction and campus life. Reasonable accommodations for students with disabilities is a shared faculty and student responsibility. Students are expected to inform faculty [me] of their need for instructional accommodations by the end of the third week of the semester, or as soon as possible after a disability has been incurred or recognized. Faculty [I], will work either directly with the student [you] or in coordination with the McBurney Center to identify and provide reasonable instructional accommodations. Disability information, including instructional accommodations as part of a student's educational record, is confidential and protected under FERPA. [link]

Institutional Statement on Diversity

Diversity is a source of strength, creativity, and innovation for UW-Madison. We value the contributions of each person and respect the profound ways their identity, culture, background, experience, status, abilities, and opinion enrich the university community. We commit ourselves to the pursuit of excellence in teaching, research, outreach, and diversity as inextricably linked goals.

The University of Wisconsin-Madison fulfills its public mission by creating a welcoming and inclusive community for people from every background – people who as students, faculty, and staff serve Wisconsin and the world. [link]