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:

learn how to pose optimization problems.
learn how to transform those problems into hopefully simpler-to-solve problems.
learn how to solve problems by using different algorithms.
learn how much time such algorithms would need.
we will also cover some recent techniques in optimization with broad applicability.

Prerequisites

Basic knowledge from calculus and linear algebra is required.

Textbooks

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

Assignments

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:

a definition of an optimization problem, possibly relevant to your interests.
a possible transformation of the original problem into a hopefully simpler-to-solve problem (e.g., by duality, minimization with respect to a subset of variables, etc.)
a full implementation of an algorithm (e.g., gradient descent, Newton, interior-point, etc.)
experimental results (e.g., showing the objective function on the Y axis and the number of iterations on the X axis; using different step sizes; comparing different algorithms, etc.)

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.

Grading

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.

Schedule

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 15	SPRING VACATION
Thu, Mar 17	SPRING VACATION
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