ORIE 6300 Mathematical Programming I

Instructor Information

instructor: Damek Davis
office hours: M 2:30PM-3:30PM, W 12PM-1PM, and by appointment
office: Rhodes Hall 218
email: dsd95 at cornell.edu

teaching assistant: Calvin Wylie
office: Rhodes Hall 290
office hours: TR 3-4PM
email: cjw278 at cornell.edu

course discussion site: http://www.piazza.com/cornell/fall2016/orie6300/home

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: Hollister Hall 306

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

Course Description

This course gives a rigorous treatment of the theory and computational techniques of linear programming and its extensions, including formulation, duality theory, algorithms, sensitivity analysis, network flow problems and algorithms, theory of polyhedral convex sets, systems of linear equations and inequalities, Farkas’ lemma, and exploiting special structure in the simplex method and computational implementation. Topics covered will include the ellipsoid method, interior-point methods, and computational complexity issues related to optimization problems.

Topics Covered (filled in as we go along)

Introduction to linear programming, duality (1 week).

Geometry of linear programs (1 week)

Normal Cones, Strong Duality, Value Functions (2 weeks)

Simplex method (3 weeks)

Operator-Splitting Algorithms (2 weeks)

Interior Point Methods (1 week)

Nonlinear Programming (3 weeks)

Prerequisites

Multivariable calculus and linear algebra.

Textbook

There is no required text for this course. Instead, we will write our own set of notes. At the beginning of each lecture I will ask for a volunteer who will scribe that day's lecture. The scribe is then required to email me, within six days, a clearly written set of notes, which I will post to the course website. The notes are to be written in LaTeX. Scribes can access a document of latex macros below.

I will occasionally draw on several books, for example

Dimitris Bertsimas and John N. Tsitsiklis, Introduction to Linear Optimization, Athena Scientific, 1997.

Matousek, Jiri, and Bernd Gärtner. Understanding and using linear programming. Springer Science & Business Media, 2007. (Available on SpringerLink)

More books will likely be added to this list as the course progresses.

I will also occasionally draw on lecture notes from other courses, for example

Lieven Vandenberghe's notes for EE236A at UCLA.

Jim Burke's Notes for M407 at UW Seattle

Requirements and Grading

You will need to complete weekly problems sets, a take-home midterm, and an in-class final exam.

Your grade depends on all of the above components as follows: problem sets (40%), midterm (20%), final (30%), scribing 1-2 lectures (5%), lecture/recitation/piazza participation and filling out course evaluation form (5%).

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.