ORIE 6300 Mathematical Programming I
Instructor Information
instructor: Damek Davis
office hours: T 2:404:15PM and by appointment
office: Rhodes Hall 218
email: dsd95 at cornell.edu
teaching assistant: Benjamin Grimmer
office hours: TR 10AM11AM
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 firstorder 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 wellstructured nonconvex problems (smoothness, composite structure, and regularity conditions).
Nonsmooth calculus: Compute firstorder 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)
FirstOrder 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 InteriorPoint 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 inclass 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)
Lecture Notes from Previous Instructors
