Computing and Optimization

Fall 2017, Princeton University (undergraduate course)

This is the Fall 2017 version of this course. For the current version, Fall 2016 version, Fall 2015 version, or Fall 2014 version, see their respective pages.

Useful links

• Blackboard
• Piazza (used only for Q&A - you should sign in to Piazza via Blackboard)
• Download MATLAB
• Download CVX

Lectures

The lecture notes below summarize most of what I cover on the blackboard during class. 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], [ppt]
  
   
• 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 (optional lecture)
  [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: Optimization Perspectives on Robot Learning, Perception, and Control, Dr. Vikas Sindhwani (Google Brain).
  [pdf] 
  
   
• Lecture 16: Limits of computation + course recap.
  [pdf] 
  
   

Problem sets and exams

Solutions are posted on Blackboard. Exams are also posted on Blackboard.

• Homework 1: Optimize for happiness, perfect numbers, and a review of linear algebra, multivariate calculus, and MATLAB.
  [pdf]
  
   
• Homework 2: Image compression and SVD, local and global minima, positive semidefinite matrices, copositive matrices and convex sets.
  [pdf], [maryam.jpg]
  
   
• Homework 3: Convex functions, regression under different penalties, minimizers of convex problems, distance between convex sets.
  [pdf] 
   
• Homework 4: Support vector machines, Hillary or Bernie, Radiation treatment planning, Newton fractals.
  [pdf], [HWSVM], [Hillary_vs_Bernie], [treatment_planning_data]
  
   
• Practice Midterm 
  [pdf], [pdf] 
  
   
• Midterm 
  [pdf] 
  
   
• Homework 5: Orbit of the Earth and daily temperature in NYC, New gym for Princeton, Leontief economy, Lyapunov functions.
  [pdf], [Circledraw.m], [plotgrid.m], [princetoncampus.png], [TemperatureNewYork.mat]
   
• Homework 6: Uniqueness of optimal solutions in LP, theory/application split in a course.
  [pdf] 
  
   
• Homework 7: Existence of rational solutions to LPs and SDPs, weak duality in LP and SDP.
  [pdf]
  
   
• Homework 8: End-of-semester party at AAA's + Doodle and scheduling + SDP relaxations + NP-completeness.
  [pdf], [Party_people_in_the_house_tonight.mat], [Doodle_matrix.mat] 
  
   
• Practice Final
  [pdf], [pdf], [pdf]
  
   
• Final exam
  [pdf]