# 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 Newton's methods for nonlinear optimization, real-time optimization and data-driven 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 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

### Instructor

Name: Bartolomeo Stellato

Oﬀice: Zoom Meeting Room

Time: Wed 2:00pm – 4:00pm EST

Email: bstellato@princeton.edu

### Assistant in instruction

Name: Zheng Yu

Oﬀice: Zoom Meeting Room

Time: Fri 2:00pm – 4:00pm EST

Email: zhengy@princeton.edu

## Topics

### Linear optimization

- Linear optimization modelling and applications
- Geometry
- Duality
- Degeneracy
- The simplex method
- Sensitivity analysis
- Interior point methods

### Nonlinear optimization

- Nonlinear optimization modelling and applications
- Optimality conditions
- First-order methods
- Second-order methods

### Extensions

- Sequential convex programming
- Branch and bound algorithms
- Data-driven heuristics and algorithm design
- Real-time optimization

# Schedule

All lectures will be streamed from this Zoom link and recorded with videos available on Canvas.

# | Date | Topic | Slides | Homeworks |
---|---|---|---|---|

1 | 09/01 | Introduction | 01_lecture.pdf 01_lecture_annotated.pdf | |

2 | 09/03 | Linear optimization | 02_lecture.pdf 02_lecture_annotated.pdf | |

3 | 09/08 | Geometry and polyhedra | 03_lecture.pdf 03_lecture_annotated.pdf | 1 Out |

4 | 09/10 | Simplex method I | 04_lecture.pdf 04_lecture_annotated.pdf | |

5 | 09/15 | Simplex method II | 05_lecture.pdf 05_lecture_annotated.pdf | 1 Due |

6 | 09/17 | Linear algebra and simplex implementation | 06_lecture.pdf 06_lecture_annotated.pdf | |

7 | 09/22 | Linear optimization duality I | 07_lecture.pdf 07_lecture_annotated.pdf | 2 Out |

8 | 09/24 | Linear optimization duality II | ||

9 | 09/29 | Sensitivity analysis | 2 Due | |

10 | 10/01 | Barrier method for linear optimization | ||

11 | 10/06 | Primal-dual interior point method for linear optimization | ||

10/08 | Midterm |
|||

12 | 10/15 | Nonlinear optimization | ||

13 | 10/20 | Nonlinear optimality conditions | 3 Out | |

14 | 10/22 | Gradient methods | ||

15 | 10/27 | Proximal algorithms and monotone operators | 3 Due | |

16 | 10/29 | Operator splitting methods | ||

17 | 11/03 | Newton's method | 4 Out | |

18 | 11/05 | Nonconvex optimization | ||

19 | 11/10 | Sequential convex programming | 4 Due | |

20 | 11/12 | Branch-and-bound algorithms | ||

21 | 11/17 | Data-driven algorithms | 5 Out | |

22 | 11/19 | Real-time optimization | ||

23 | 11/25 | Conclusions | 5 Due | |

12/10 | Final |

## Material

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

- R. J. Vanderbei:
*Linear Programming: Foundations & Extensions*(available on SpringerLink) - D. Bertsimas, J. Tsitsiklis:
*Introduction to Linear Optimization*(available Princeton Controlled Digital Lending) - J. Nocedal, S. J. Wright:
*Numerical Optimization*(available on SpringerLink)

## 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.

## Grading

All submissions should take place on Gradescope (accessible from the canvas website).

**25% Homeworks.**5 bi-weekly 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 (pdf-exported jupyter notebook). To export a jupyter notebook as pdf just click on: File → Download as → PDF via LaTeX (.pdf).**25% Midterm.**90 minutes written exam. No coding required.**40% Final.**Take-home 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.
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. Please have your video (with whatever background you prefer to use, there are many Princeton backgrounds here) turned on, except during class breaks, unless you have an unexpected difficulty or have arranged with me otherwise. An excused absence will only be granted in the case of a religious observance, an ODS-approved accommodation, or -- as verified by your residential college -- a serious illness or an exceptional circumstance.

## Software

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