ORIE 6300 Mathematical Programming I

Instructor Information

instructor: Damek Davis
office hours: T 2:40-4:15PM and by appointment
office: Rhodes Hall 218
email: dsd95 at cornell.edu

teaching assistant: Benjamin Grimmer
office hours: TR 10AM-11AM
office: Rhodes Hall 295
email: bdg79 at cornell.edu

course discussion site: https://www.piazza.com/cornell/fall2019/orie6300

Email Policy

Do not expect immediate responses to emailed questions. I will try to respond to all emailed questions within 48 hours. If you feel your question may be of general interest to the class, post it on piazza.

Meeting Times and Location

lecture time: Tuesday and Thursday 1:25PM–2:40PM
lecture location: Statler Hall 351

recitation time: Wednesday 2:55PM–4:25PM
recitation location: Hollister Hall 306

Course Description

Optimization is a broad mathematical discipline that has achieved widespread use in many applied sciences, including operations research, machine learning, signal processing, and statistics. Beginning with classical roots in the calculus of variations, the subject has flourished: from the celebrated simplex method in linear programming to the mature theories of duality and algorithmic complexity in convex optimization, it has now enjoyed over 60 years of theoretical and computational advances. Key to these advances were the development of nonsmooth calculus and the recognition of its role in first-order optimality conditions. Based on duality, nonsmooth calculus, and the techniques of numerical linear algebra, the subject now enjoys an extensive algorithmic toolbox, containing practical and provably “efficient” numerical methods. The purpose of this class is to give you a firm working knowledge of the techniques and results of modern optimization by developing the following set of core skills:

Structure and special cases: recognize and exploit convexity and its special cases (linear and conic programming); recognize well-structured nonconvex problems (smoothness, composite structure, and regularity conditions).

Duality: learn to “take a dual;” recognize when “strong duality” holds; exploit duality in algorithms.

Nonsmooth calculus: Compute first-order necessary optimality conditions with nonsmooth calculus (subdifferentials, normal cones, and the chain rule); compute sensitivity of optimization problems with respect to perturbations of input data (value functions and Lagrange multipliers). 
Algorithms: Learn a toolbox of algorithms (simplex, interior point, and first order methods); choose appropriate algorithms by understanding tradeoffs induced by problem structure; characterize algorithmic complexity; numerically implement algorithms.

Prerequisites

A firm grasp of linear algebra, basic analysis, point set topology, and a lot of motivation are the main prerequisites for the course. You will be expected to write many proofs throughout the semester.

Textbook

This course does not have a required textbook. Instead, I will post course notes under the “Notes” section below.

In addition to the course notes, I may draw on the following resources.

Resources

Convex Analysis (Rockafellar)

Convex Optimization (Boyd and Vandenberghe)

Variational Analysis (Rockafellar)

Lectures on Convex Optimization (Nesterov)

Introduction to Linear Optimization (Bertsimas and Tsitsiklis)

First-Order Methods in Optimization (Beck)

Convex Analysis and Nonlinear Optimization (Borwein and Lewis)

Course notes: Convex Analysis and Optimization (Drusvyatskiy)

Lieven Vandenberghe's notes for EE236A at UCLA

Understanding and Using Linear Programming (Matousek and Gärtner)

A Mathematical View of Interior-Point Methods in Convex Optimization (Renegar)

Convex Analysis and Monotone Operator Theory in Hilbert Spaces (Bauschke and Combettes)

Introduction to Nonlinear Optimization: Theory, Algorithms, and Applications with MATLAB (Beck)

More resources will be added as the course progresses.

Requirements and Grading

You will complete weekly problems sets, an in-class final exam, and (possibly) a take home final. The majority of your grade will be based on homework assignments, while the in class final will be worth approximately 25% of your grade. Your grade will also be based (to a much lesser extent) on participation in lecture/recitation/piazza and filling out the course evaluation.

Most importantly:

All homework assignments must be written in LaTex.

If the assignments are not written clearly and coherently, they will be returned back to you and you will receive a zero on the assignment.

Collaboration

Cornell’s Code of Academic Integrity can be found at cuinfo.cornell.edu/Academic/AIC.html.

You may work together on problem sets, but you must write up your own solutions AND acknowledge those with whom you discussed the problem. You must also cite any resources which helped you obtain your solutions. Exam problems should not be discussed with other students.

Notes

Lectures

Course Notes (Updated Nov 18)

Recitations

Recitations (Updated Nov 15)

CVX Demo (Updated Oct 31)

Homework Problems

All Assignments in One File [tex file] (Updated Nov 15)