Roughly, we will cover the following topics (some of them may be skipped depending on the time available).
Linear Programming: basics, Simplex algorithm, and duality
Applications of Linear Programming: regression, classification and other engineering applications
Integer Linear Programming: basics, branch-and-bound, cutting-plane methods
Combinatorial Optimization: basics of approximation algorithms
Network-flow problems
Interior-point methods
Conic Programming
We will use the following main textbook for Linear Programming:
Linear Programming: Foundations and Extensions, RJ Vanderbei
Subject to changes over the course of the semester
| ID | Date | Topics Covered |
|---|---|---|
| 1 | We 1/18 | Introduction to optimization and Linear Programming |
| 2 | Mo 1/23 | Modeling optimization problems with examples |
| 3 | We 1/25 | The Simplex algorithm I: intro |
| 4 | Mo 1/30 | The Simplex algorithm II: algorithm, initialization |
| 5 | We 2/01 | The Simplex algorithm III: geometry, degeneracy |
| 6 | Mo 2/06 | The Simplex algorithm IV: degeneracy (cont'd), complexity |
| 7 | We 2/08 | Duality I: intro, weak duality |
| 8 | Mo 2/13 | Duality II: strong duality |
| 9 | We 2/15 | Duality III: complementary slackness and sensitivity |
| 10 | Mo 2/20 | The Simplex algorithm V: matrix notation |
| 11 | We 2/22 | Geometry of Linear Programs I: convex sets and polyhedra |
| 12 | Mo 2/27 | Geometry of Linear Programs II: operations on polyhedra |
| 13 | We 3/01 | Applications I: norms, regression, classification |
| 14 | Mo 3/06 | Applications II: finance |
| 15 | We 3/08 | Applications III: control theory |
| 16 | Mo 3/13 | Applications IV: games + revision for Exam #1 |
| 17 | We 3/15 | Exam #1 |
| 18 | Mo 3/20 | Integer Linear Programming I: intro, modeling |
| 19 | We 3/22 | Integer Linear Programming II: branch-and-bound algorithm |
| / | Mo 3/27 | Spring break |
| / | We 3/29 | Spring break |
| 20 | Mo 4/03 | Integer Linear Programming III: cutting-plane algorithm |
| 21 | We 4/05 | Integer Linear Programming IV: applications |
| 22 | Mo 4/10 | Network-flow problems I: intro |
| 23 | We 4/12 | Network-flow problems II: network Simplex algorithm |
| 24 | Mo 4/17 | Network-flow problems III: max-flow min-cut theorem |
| 25 | We 4/19 | Interior-point methods I: intro |
| 26 | Mo 4/24 | Interior-point methods II: primal-dual path-following method |
| 27 | We 4/26 | Interior-point methods III: Newton's method |
| 28 | Mo 5/01 | Interior-point methods IV: convergence analysis |
| 29 | We 5/03 | Exam #2 |
Problem sets will be given to you as problems that you will need to solve. These could be conceptual problems that ask you to work through some detail of a proof or formulate an optimization problem, but it could also be practical problems accompanied by a programming component. For instance, we could ask you to formulate a portfolio optimization problem to invest in a set of stocks. You may be asked to formulate the problem, describe the solution, and we may give you a dataset and ask you to implement your solution over the given dataset.
Organization: Assignments and deadlines will be posted on canvas.
To be flexible, we will omit one problem set with the lowest scores from consideration while computing the overall grade.
The course includes a important component of programming. We will do demonstrations of optimization programs during the class, and assignments will involve implementing small pieces of code to solve practical problems.
We recommend the use of Julia or Python.
The course work will consist in (a) problem sets (see above); (b) spot exams; and (c) final project.
We expect to post 6 problem sets.
We will have 2 spot exams spread out through the semester. They will test material that you have learned and go on for one hour each.
The first spot exam will take place on Wednesday March 15, 2023.
The second spot exam will take place on Wednesday May 3, 2023.
The questions will be theory and application of tools seen in the class. They will be written exams. The duration is 1 hour for each. Bring sheets of paper and writing material. They will take place in person in the usual classroom ECCS 1B28. If for some major reason you cannot attend in person, let me know as soon as possible.
It will involve working in teams of two students who will understand a topic related to Linear, Integer, or Convex Optimization. The topic can be theory, algorithms and/or applications, as long as it goes beyond what has been covered in class.
The project will be presented in a 15-minute presentation during the last classes of the semester.
Final grades will be calculated using the cumulative scores with the appropriate weights.