## Computing and Optimization

### Fall 2021, Princeton University (undergraduate course)

(This is the Fall 2021 version of this course. You can also access the Fall 2020 , Fall 2019, Fall 2018, Fall 2017, Fall 2016, Fall 2015, Fall 2014 versions .)

#### Useful links

- The course syllabus
- Canvas (for Q&A, sign up to Ed Discussion via Canvas)
- Download MATLAB
- Download CVX
- Acknowledgments

#### Lectures

The notes below summarize most of what I cover during lecture. Please complement them with your own notes.

Some lectures take one class session to cover, some others take two.

- Lecture 1: Let's play two games! (Optimization, P and NP.)

[pdf]

- Lecture 2: What you should remember from linear algebra and multivariate calculus.

[pdf]

- Lecture 3: Unconstrained optimization, least squares, optimality conditions.

[pdf]

- Lecture 4: Convex optimization I.

[pdf]

- Lecture 5: Convex optimization II.

[pdf]

- CVX: Basic examples.

[m]

- Lecture 6: Applications in statistics and machine learning: LASSO + Support vector machines (SVMs)

[pdf]

- Lecture 7: Root finding and line search. Bisection, Newton, and secant methods.

[pdf]

- Lecture 8: Gradient descent methods, analysis of steepest descent, convergence and rates of convergence, Lyapunov functions for proving convergence.

[pdf]

- Lecture 9: Multivariate Newton, quadratic convergence, Armijo stepsize rule, nonlinear least squares and the Gauss-Newton algorithm.

[pdf]

- Lecture 10: Conjugate direction methods, solving linear systems, Leontief economy.

[pdf]

- Lecture 11: Linear programming: applications, geometry, and the simplex algorithm.

[pdf]

- Lecture 12: Duality + robust linear programming.

[pdf]

- Lecture 13: Semidefinite programming + SDP relaxations for nonconvex optimization.

[pdf]

- Lecture 14: A working knowledge of computational complexity theory for an optimizer.

[pdf]

- Lecture 15: Limits of computation + course recap.

[pdf]

#### Problem sets and exams

Solutions are posted on Canvas.

- Homework 1:
- Homework 2:
- Homework 3:
- Homework 4:
- Practice Midterms
- Midterm
- Homework 5:
- Homework 6:
- Homework 7:
- Homework 8:
- Practice Finals
- Final Exam