princetonlogo
Bartolomeo Stellato

ORF522: Linear and Nonlinear Optimization

Previous years: 2020 2021 2022 2024 2025

Description

This course introduces analytical and computational tools for linear, convex, nonconvex, and stochastic optimization. Topics include linear optimization modeling, duality, the simplex method, degeneracy, sensitivity analysis. Nonlinear optimality conditions, KKT conditions, first order and operator splitting methods for large-scale convex optimization, nonconvex optimization algorithms, and stochastic optimization. A broad spectrum of applications in engineering, finance and statistics is presented.

Learning objectives

This course introduces analytical and computational tools for mathematical optimization.
Upon successful completion of this course you should be able to:

  • Model decision-making problems across different disciplines as mathematical optimization problems.

  • Apply the most appropriate optimization tools when faced with a concrete problem.

  • Implement optimization algorithms and prove their convergence.

Office hours

Office hours start in the second week of classes (week of September 7).

Instructor

Name: Bartolomeo Stellato
Office hours: Sherrerd 107
Time: Tue 1:30pm – 2:30pm EST
Email: bstellato@princeton.edu

To attend the instructor office hours, book via the calendar link available on canvas.

Assistants in instruction

Name: Daniel Deza
Office hours: Sherrerd 107
Time: Thu 1:30pm – 2:30pm EST
Email: dd7022@princeton.edu

Name: Zhongtian He
Office hours: Sherrerd 107
Time: Wed 2:00pm – 3:00pm EST
Email: zh3617@princeton.edu

Name: Rafael Moschopoulos (UCA)
Office hours: Sherrerd 107
Time: Fri 4:00pm – 5:30pm EST
Email: gm3460@princeton.edu

Schedule

All lectures will take place on Tuesdays and Thursdays 10:40am - 12:00pm in Friend Center 004.

Linear optimization

# Date Topic HW References
1 09/03 Introduction
2 09/08 Linear optimization [Ch 1, LO]
3 09/10 Geometry and polyhedra [Ch 2, LO]
4 09/15 Simplex method I [Ch 3, LO]
5 09/17 Simplex method II 1 Out [Ch 3, LO]
6 09/22 Linear algebra and simplex implementation [Ch 3, LO] [Ch 13, NO] [Ch 8, LP]
7 09/24 Duality I [Ch 4, LO] [Ch 5, LP]
8 09/29 Duality II [Ch 4, LO] [Ch 11, LP] [Ch 5, LO]

Large-scale convex optimization

# Date Topic HW References
9 10/01 Introduction 2 Out [Ch 2 to 4, CO] [Ch1 LSMO] [Ch A and B, FCA]
10 10/06 Optimality conditions [Ch 2 and 12, NO] [Ch 4 and 5, CO]
11 10/08 Gradient descent [Ch 1 and 2, ILCO] [Ch 9, CO] [Ch 5, FMO]
12 10/13 Subgradients [Ch 1 LSMO] [Ch 3 and 8, FMO] [ee364b] [Ch 3, ILCO]
10/15 Midterm I (in person)
13 10/27 Subgradient method and proximal algorithms [Ch 3 and 6, FMO] [PA]
14 10/29 Operator theory I 3 Out [Ch 4, FMO] [PA] [LSMO]
15 11/03 Operator theory II [Ch 4, FMO] [PA] [LSMO]
16 11/05 Operator splitting algorithms [PA] [LSMO]
17 11/10 Alternating Direction Method of Multipliers [PA] [LSMO] [ADMM]
18 11/12 Acceleration schemes 4 Out [Ch 1, FMO] [Ch 2, ILCO] [Ch 3, COAC]
19 11/17 Computer-aided analysis of first-order methods Tutorials, pepit toolbox
11/19 Midterm II (in person)

Nonconvex and stochastic optimization

# Date Topic HW References
20 11/24 Sequential convex programming [Ch 4 and 17, NO] [ee364b]
21 12/01 Branch and bound algorithms [ee364b] [MINLO]
22 12/03 Optimization under uncertainty 5 Out [RO, Ch 1 and 2] [TARO] [ee364b]
12/17 Final (in person, 9:00am to 12:00pm)

Material

The code 💻 used in the lectures is available on the github companion repo.

The lecture notes are available from the course website and intended to be self contained. The following books and monographs are useful as reference texts.
They are either free or digitally available via Princeton University library:

  • [LP] R. J. Vanderbei: Linear Programming: Foundations & Extensions (available on SpringerLink)

  • [LO] D. Bertsimas, J. Tsitsiklis: Introduction to Linear Optimization (available Princeton Controlled Digital Lending)

  • [NO] J. Nocedal, S. J. Wright: Numerical Optimization (available on SpringerLink)

  • [CO] S. Boyd, L. Vandenberghe: Convex Optimization (available for free)

  • [FMO] A. Beck: First-order methods in optimization (available on SIAM)

  • [LSMO] E. K. Ryu and W. Yin: Large-Scale Convex Optimization via Monotone Operators (available for free)

  • [FCA] J. B. Hiriart-Hrruty, C. Lemarechal: Fundamentals of Convex Analysis (available on SpringerLink)

  • [ILCO] Y. Nesterov: Introductory Lectures to Convex Optimization (available on SpringerLink)

  • [e364b] S. Boyd: Convex Optimization II Lecture Notes (available online)

  • [PA] N. Parikh, S. Boyd: Proximal Algorithms (available for free)

  • [ADMM] S. Boyd, N. Parikh, B. Peleato, J. Eckstein: Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers (available for free)

  • [COAC] S. Bubeck: Convex Optimization: Algorithms and Complexity (available for free)

  • [MINLO] P. Belotti, C. Kirches, S. Leyffer, J. Linderoth, J. Luedtke, A. Mahajan: Mixed-integer nonlinear optimization (available online)

  • [RO] A. Ben-Tal, L. El Ghaoui, A. Nemirovski: Robust optimization (available online)

  • [TARO] D. Bertsimas, D. B. Brown, C. Caramanis Theory and Applications of Robust Optimization (available online)

  • [ISA] M. Campi, S. Garatti Introduction to the Scenario Approach (available online)

In this course we strictly follow the crimes against matrices laws!

Prerequisites

  • Good knowledge of linear algebra and calculus. For a refresher, we recommend reading Appendices A and C of the S. Boyd and L. Vandenberghe Convex Optimization (available online).
  • Familiarity with Python.

Software

Students will use the Python-based modeling software CVXPY (cvxpy.org) to solve optimization problems arising in several applications in operations research, finance, machine learning and engineering.

The homeworks will be using jupyter notebooks running in the jupyterlab environment. You can get it running with all required packages in two ways:

  • Cloud setup: follow the instructions in the companion repo to run a complete environment on github codespaces.
  • Local installation: follow the instructions in this repository to install the environment locally via docker.

Grading

The final grade is based on three in-person written exams. No coding is required in the exams.

  • 30% Midterm I. 80 minutes in-class exam on 10/15.
  • 30% Midterm II. 80 minutes in-class exam on 11/19.
  • 40% Final. In-person exam on Thursday 12/17, 9:00am to 12:00pm.

Homeworks. This year homeworks are not graded. We will release them, together with their solutions, as the semester progresses. They are the main practice material for the exams, and we strongly encourage you to work through them on your own before looking at the solutions.

Questions and discussions

Students are encouraged to discuss and ask questions on Ed (link accessible via canvas).
Please make sure to specify if questions are about General information of the course, about the Lectures, about the Homeworks, or about the Exams by assigning them to the corresponding category.

Honor code and generative AI

All work in this course must uphold the University’s commitment to academic integrity. This includes the Honor Code (for written examinations, tests, and quizzes) and guidelines for the submission of original work on all other assignments. More guidance can be found in Rights, Rules, and Responsibilities as well as the handbook Academic Integrity at Princeton.

AI tools are not permitted during either midterm or the final examination. Outside exams, using them is optional and encouraged when they support your learning. The homeworks are ungraded practice for the in-person exams. Work on each problem independently first, then use AI to ask for a hint, test an argument, or clarify a concept. Do not delegate the mathematical thinking you are trying to learn.

Three especially useful modes are to ask the AI to act as a tutor that gives one hint or question at a time, to reverse the roles and teach the concept to an AI that acts as a novice, and, after your attempt, to compare your work with the released solution one gap at a time. Our guide to using AI for learning explains how to install the ai-socratic-tutor, ai-novice, and ai-solution-study skills and includes examples of each.

AI outputs can be plausible and wrong, especially in proofs, counterexamples, signs, and assumptions. You remain responsible for checking every step against the lecture notes and references. A good final test is to close the chat and explain the concept or solve the problem again on your own. AI is an additional study tool, not a replacement for course staff, office hours, Ed, or discussions with classmates.

Attendance

Students are expected to attend each scheduled class on time and ready to participate fully. An excused absence will only be granted in the case of a religious observance, an ODS-approved accommodation, or a serious illness or an exceptional circumstance verified by your residential college.