Computing and Optimization

Fall 2023, Princeton University (undergraduate course)

(This is the Fall 2023 version of this course. You can also access the Fall 2021, 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
• MATLAB Tutorial
• Download CVX (or CVXPY if you are a Python user)
• 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 Demo
  [cvx_examples.m] (MATLAB), [cvxpy_examples.ipynb] (Python)
   
• 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: Optimizing Cub Club, perfect numbers, and a review of linear algebra and multivariate calculus.
  [pdf]
   
• Homework 2: Image compression and remembering John Conway, local and global minima, positive semidefinite matrices, copositive matrices.
  [pdf], [conway.jpg]
   
• Homework 3:  Radiation treatment planning, hands off my paintings, convex analysis.
  [pdf], [wall_with_paintings.jpg]
  MATLAB specific data files: [treatment_planning_data.m], [Circledraw.m]
  Python specific data files: [treatment_planning_data.py], [Atumor.csv], [Aother.csv] 
   
• Practice Midterms:
  [Fall17], [Fall18], [Fall19], [Fall20], [Fall21]
   
• Midterm:
  [pdf]
   
• Homework 4: Support vector machines, predicting the outcome of an election, Newton fractals.
  [pdf], [HWSVM], [Hillary_vs_Bernie]
   
• Homework 5: New gym for Princeton, orbit of the Earth and daily temperature in NYC, Lyapunov functions.
  [pdf], [princetoncampus.jpeg], [Circledraw.m], [plotgrid.m], [plotgrid.py], [TemperatureNewYork.csv]
   
• Homework 6: Theory-application split in a course, minimum fuel optimal control, computing square roots.
  [pdf]
   
• Homework 7: Nearest correlation matrix, existence of rational solutions to LP and SDP.
  [pdf]
   
• Homework 8: End-of-semester party at AAA's, Doodle and scheduling, SDP relaxations for nonconvex polynomial optimization, NP-completeness.
  [pdf], [Party_people_in_the_house_tonight.mat], [Doodle_matrix.mat]
   
• Practice Final Exams (data files on Canvas):
  [Fall17], [Fall18], [Fall19], [Fall20], [Fall21]
   
• Final Exam:
  [pdf]