CS 52000: Computational Methods In Optimization

Semester: Spring 2016
Time and place: Tuesday and Thursday, 9am-10.15am, Lawson Building B134
Instructor: Jean Honorio, Office hours until March 11: Monday, 2pm-4pm, Lawson Building 2142-J
After March 11, please send me an e-mail for appointments.
TA: Yudong Cao, Office hours: Wednesday, 2pm-4pm, Lawson Building B116-F

This course is an introduction to optimization for graduate students. It covers many of the fundamentals of optimization and is a good course to prepare those who wish to use optimization in their research and those who wish to develop new algorithms and theory.

Learning Objectives

During the course, students will:


Basic knowledge from calculus and linear algebra is required.


Convex Optimization by Boyd and Vandenberghe
Numerical Optimization by Nocedal and Wright


There will be up to five homeworks, one midterm exam, one final exam and one project (dates posted on the schedule). The homeworks are to be done individually. The project can be done either individually or in groups of two students.

For every lecture, you will be expected to read the corresponding book chapter BEFORE the lecture. A quiz will take place at the beginning of some lectures.

For the project, you will write a half-page project plan (around 1-2 weeks before the midterm), a 2-4 page preliminary results report (around 1-2 weeks after the midterm) and a 4-8 page final results report (around 1-2 weeks before the final exam). The project should include: Note that you will have to implement ALL the algorithm from scratch. Using an optimization package is not allowed. I suggest you use Matlab, since you might not have enough time to debug your code if you use other languages such as C/C++. Neither I nor the TA will provide any help regarding programming-related issues.


Homeworks: 25%
Quizzes: 5%
Midterm exam: 20%
Final exam: 20%
Project: 30%

Late policy

Assignments are to be submitted by the due date listed. Each person will be allowed seven days of extensions which can be applied to any combination of assignments during the semester. Use of a partial day will be counted as a full day. Extensions cannot be used after the final day of classes. Please, use the extension days wisely!

Assignments will NOT BE accepted if they are more than five days late.

Academic Honesty

Please read the departmental academic integrity policy here. This will be followed unless we provide written documentation of exceptions. We encourage you to interact amongst yourselves: you may discuss and obtain help with basic concepts covered in lectures and homework specification (but not solution). However, unless otherwise noted, work turned in should reflect your own efforts and knowledge. Sharing or copying solutions is unacceptable and could result in failure. You are expected to take reasonable precautions to prevent others from using your work.

Additional course policies

Please read the general course policies here.


We will cover chapters 1,2,3,4,5,9,10,11 in Convex Optimization by Boyd and Vandenberghe (B&V). We will also cover chapters 4,6,9 in Numerical Optimization by Nocedal and Wright (N&W). If time permits, we will cover recent material from conferences and journals.

Date Topic (Tentative) Notes
Tue, Jan 12 B&V Chapter 1: introduction Homework 0 (password-protected): due on Jan 14 at beginning of class
Thu, Jan 14 B&V Chapter 2: convex sets Homework 0 due
Tue, Jan 19     (lecture continues)
B&V Chapter 3: convex functions
Quiz 1
Homework 0 solution (password-protected)
Notes about the Cauchy-Schwarz inequality [1] [2]
Thu, Jan 21     (lecture continues) Identities on matrix calculus
Tue, Jan 26
Thu, Jan 28 B&V Chapter 4: convex optimization problems Homework 1: due on Feb 2 at beginning of class
Tue, Feb 2     (lecture continues) Homework 1 due
Thu, Feb 4     (lecture continues)
Tue, Feb 9 B&V Chapter 5: duality Homework 1 solution (password-protected)
Thu, Feb 11     (lecture continues) Homework 2: due on Feb 18 at beginning of class
Tue, Feb 16     (lecture continues)
Thu, Feb 18 B&V Chapter 9: unconstrained optimization Homework 2 due
Tue, Feb 23 Homework 3: due on Mar 1 at beginning of class
Thu, Feb 25 Subgradient methods, convergence analysis Homework 2 solution (password-protected)
Tue, Mar 1 Homework 3 due (moved to Mar 3)
Thu, Mar 3 B&V Chapter 10: equality constrained optimization Homework 3 due
Tue, Mar 8 B&V Chapter 11: interior-point methods Homework 3 solution (password-protected)
Thu, Mar 10     (lecture continues) Project plan due (see Assignments for details)
Tue, Mar 22 MIDTERM 9am-10.15am at Lawson Building B134
Thu, Mar 24     (midterm solution)
Tue, Mar 29 Stochastic optimization, convergence analysis
Thu, Mar 31 Matroids and the greedy algorithm
Tue, Apr 5     (lecture continues)
Submodular optimization
Project preliminary report due (see Assignments for details)
Homework 4 (password-protected): due on Apr 14 at 11.59pm
Thu, Apr 7 Greedy algorithms for submodular maximization
Tue, Apr 12
Thu, Apr 14 N&W Chapter 6: quasi-Newton methods Homework 4 due
Tue, Apr 19
Thu, Apr 21
Tue, Apr 26 N&W Chapter 4: trust-region methods Project final report due (see Assignments for details)
Thu, Apr 28
Wed, May 4 FINAL EXAM 10.30am-12.30pm at Lawson Building B134