ORF522: Linear and Nonlinear Optimization
Description
This course introduces analytical and computational tools for linear and nonlinear optimization.
Topics include linear optimization modeling, duality, the simplex method, degeneracy, sensitivity analysis and interior point methods.
Nonlinear optimality conditions, KKT conditions, first order and operator splitting methods for nonlinear optimization, realtime optimization and datadriven algorithms.
A broad spectrum of applications in engineering, finance and statistics is presented.
Learning objectives
This course introduces analytical and computational tools for linear and nonlinear optimization.
Upon successful completion of this course you should be able to:

Model decisionmaking 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
Instructor
Name: Bartolomeo Stellato
Office: Sherrerd 323
Time: Thu 2:00pm – 4:00pm EST
Email: bstellato@princeton.edu
Assistant in instruction
Name: Irina Wang
Office hours: Sherrerd 003
Time: Mon 1:00pm  3:00pm EST
Email: iywang@princeton.edu
Schedule
All lectures will take place in Friend Center 009
Linear optimization
#  Date  Topic  Slides  HW  References 

1  09/06  Introduction  01_lec.pdf 01_lec_notes.pdf  
2  09/08  Linear optimization  02_lec.pdf 02_lec_notes.pdf  [Ch 1, LO]  
3  09/13  Geometry and polyhedra  03_lec.pdf 03_lec_notes.pdf  [Ch 2, LO]  
4  09/15  Simplex method I  04_lec.pdf 04_lec_notes.pdf  1 Out  [Ch 3, LO] 
5  09/20  Simplex method II  05_lec.pdf 05_lec_notes.pdf  [Ch 3, LO]  
6  09/22  Linear algebra and simplex implementation  06_lec.pdf 06_lec_notes.pdf  1 Due  [Ch 3, LO] [Ch 13, NO] [Ch 8, LP] 
7  09/27  Linear optimization duality I  07_lec.pdf 07_lec_notes.pdf  [Ch 4, LO] [Ch 5, LP]  
8  09/29  Linear optimization duality II  08_lec.pdf 08_lec_notes.pdf  2 Out  [Ch 4, LO] [Ch 11, LP] 
9  10/04  Sensitivity analysis  09_lec.pdf 09_lec_notes.pdf  [Ch 5, LO]  
10  10/06  Interiorpoint methods for linear optimization  10_lec.pdf 10_lec_notes.pdf  2 Due  [Ch 14, NO] [Ch 17 and 18, LP] 
11  10/11  Interiorpoint methods implementation  11_lec.pdf  [Ch 14, NO] [Ch 22, LP]  
10/13  Midterm (only linear optimization) 
Nonlinear optimization
#  Date  Topic  Slides  HW  References 

12  10/25  Introduction to nonlinear optimization  12_lec.pdf 12_lec_notes.pdf  [Ch 2 to 4 and 6, CO] [Ch A and B, FCA]  
13  10/27  Optimality conditions  13_lec.pdf 13_lec_notes.pdf  [Ch 2 and 12, NO] [Ch 4 and 5, CO]  
14  11/01  Gradient descent  14_lec.pdf 14_lec_notes.pdf  [Ch 1 and 2, ICLO] [Ch 9, CO] [Ch 5, FMO]  
15  11/03  Subgradients  15_lec.pdf  3 Out  [Ch 3 and 8, FMO] [ee364b] [Ch 3, ILCO] 
16  11/08  Proximal algorithms  16_lec.pdf  [Ch 3 and 6, FMO] [PA] [PMO]  
17  11/10  Operator theory I  17_lec.pdf  3 Due  [Ch 4, FMO] [PA] [PMO] [LSMO] 
18  11/15  Operator theory II  18_lec.pdf  [Ch 4, FMO] [PA] [PMO] [LSMO]  
19  11/17  Operator splitting algorithms  19_lec.pdf  4 Out  [PMO] [PA] [LSMO] 
20  11/29  Alternating Direction Method of Multipliers  20_lec.pdf  [PMO] [PA] [LSMO] [ADMM]  
21  12/01  Acceleration schemes  21_lec.pdf  4 Due  [Ch 1, FMO] [Ch 2, ILCO] [Ch 3, COAC] 
Extensions
#  Date  Topic  Slides  HW  References 

22  12/06  Sequential convex programming  22_lec.pdf  [Ch 4 and 17, NO] [ee364b]  
23  12/08  Conclusions  23_lec.pdf  5 Out  
12/18  5 Due  
12/20  Final 
Material
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: Firstorder methods in optimization (available on SIAM)
 [FCA] J. B. HiriartHrruty, 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)
 [PMO] E. K. Ryu, S. Boyd: A primer on monotone operators (available for free)
 [LSMO] E. K. Ryu and W. Yin: LargeScale Convex Optimization via Monotone Operators (Draft) (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: Mixedinteger nonlinear optimization (available online)
In this course we strictly follow the crimes against matrices laws!
Code used in the lectures will be available on the github companion repo.
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 Pythonbased modeling software CVXPY (cvxpy.org) to solve optimization problems arising in several applications in operations research, finance, machine learning and engineering.
The assignments will be using jupyter notebooks. We suggest you edit them with Google Colab linked with your Google Drive (recommended way). Alternatively, you can run them locally by installing jupyter lab and the required packages on your machine. Please follow these instructions to complete the setup.
Grading
All submissions should take place on Gradescope (accessible from the canvas website).
 25% Homeworks. 5 biweekly homeworks. Almost all of them will include a computational component. Homeworks are due at 11:59pm EST of the date specified. Requests for extension on homework will not be accepted, unless there is an extremely valid reason. Homeworks must always be submitted as a single pdf file which includes your written exercises (typed or handwritten) and code (pdfexported jupyter notebook). You have three options to export your notebooks:
 On Colab: To export as pdf just click on: File → Print → Save as PDF. If this does not work or your some of your images are cut use the following
 On Colab: To export as pdf run the following commands:
Then you can go to the notebook directory on your drive and export it, for example# Install required packages
!aptget install texlive texlivexetex texlivelatexextra pandoc cmsuper dvipng
!pip install pypandoc
# Mount Google Drive
from google.colab import drive
drive.mount('/content/drive')%cd drive/MyDrive/orf522/homeworks/01_homework/
!jupyter nbconvert to PDF "ORF522_HW1.ipynb"  Local jupyter: To export as pdf just click on: File → Download as → PDF via LaTeX (.pdf).
 25% Midterm. 80 minutes written exam. No coding required.
 40% Final. Takehome final exam with written and computational questions.
 10% Participation. Students are expected to submit one question or note on each lecture on Ed. The note should summarize what you learned in the last lecture, and highlight the concepts that were most confusing or that you would like to review. A note will receive full credit if: it is submitted before the beginning of next lecture, it is related to the content of the lecture, and it is understandable and coherent. You can make the note private (visible only by you and the course staff) or public, as you choose.
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 or about Homeworks by assigning them to the related category.
Collaboration policy

Homeworks. Students are allowed, and even encouraged, to collaborate on homeworks. When submitting your homework, you are required to list the name of the students you worked with. Also, please write the textbooks, notes or websites that were helpful to you.

Midterm and final. No collaborations allowed.
Honor code
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.
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 ODSapproved accommodation, or  as verified by your residential college  a serious illness or an exceptional circumstance.