ORF363 / COS323, F15

Computing and Optimization   Fall 2015, Princeton University (undergraduate course)

(This is the Fall 2015 version of this course. For the most recent version click here.)

Useful links

New: all lecture notes and problems sets of Fall 2015 in one file: [pdf] (currently taken down)

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
    [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: Managing the campaign of Donald Trump, perfect numbers, and a review of linear algebra, multivariate calculus, and MATLAB.
    [pdf]

  • Homework 2: Image compression and SVD, local and global minima, convex sets.
    [pdf], [nash.jpg]

  • Homework 3: Convex functions, regression under different penalties, optimality conditions, distance between convex sets.
    [pdf

  • Homework 4: Support vector machines (SVMs).
    [pdf], [data file]  

  • Practice Midterm (from Fall 2014)
    [pdf

  • Midterm 
    [pdf

  • Homework 5: Radiation treatment planning, Halloween drama, Newton fractals.
    [pdf], [treatment_planning_data.m]   
     
  • Homework 6: New gym and movie theater for Princeton, your own square root solver, rates of convergence, Leontief economy and conjugate gradients.
    [pdf], [Circledraw.m], [plotgrid.m]  

  • Homework 7: Orbit of the Earth and daily temperature in NYC + optimal control + linear programming.
    [pdf], [TemperatureNewYork.mat]  
      

  • 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 (from Fall 2014)
    [pdf]   

  • Final exam
    [pdf