Computing and Optimization

Fall 2014, Princeton University (undergraduate course)

This is the Fall 2014 version of this course. See the current version.

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 1: Let's play two games! (Optimization, P and NP.)
  [pdf], [ppt]
   
• 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.
  [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: Discrete optimization at IBM Research, William Pierson Field Lecture, Dr. Sanjeeb Dash (IBM Research).
  [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: Brush up on linear algebra, multivariate calculus, and MATLAB.
  [pdf]
  
   
• Homework 2: Image compression and SVD, optimality conditions, convex sets.
  [pdf], [albert.jpg]
  
   
• Homework 3: Convex analysis and convex optimization.
  [pdf]
  
   
• Homework 4: Support vector machines (SVMs).
  [pdf], [data file]
  
   
• Homework 5: New gym and movie theater for Princeton + Newton fractals.
  [pdf], [Circledraw.m], [plotgrid.m]
  
   
• Homework 6: Leontief economy + conjugate gradients + radiation treatment planning.
  [pdf], [treatment_planning_data.m] 
  
   
• Homework 7: Optimal control + linear programming.
  [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]