S&DS 631: Computation and Optimization. Spring 2020.

The syllabus for the course is here.

This page lists everything else you need to know for the course.  If you don't see it here, check the syllabus before asking.

Time: Tuseday & Thursday, 1:00-2:15

Where: WTS 48

Dan's office hours: Fridays 2:00 - 3:00, by Zoom.

TA: Tracey (Xinyi) Zhong: office hours Monday 2:45-3:45, room 225 of DL, 10HLH

The following is the list of recommended readings, notes, and homeworks for each lecture.  Those for future dates are speculative.

For background, I recommend Solomon, Chapter 1.  You should have seen most of this before.  But, I will cover material from 1.4.3 in some class in more detail.  

Many readings come from the following resources, which are freely available online (although some will require access from inside Yale or the VPN). 

Jan 14: Introduction

Jan 16: Automatic Differentiation

Jan 21: Norms, accuracy, and solving linear equations by gradient descent.

Jan 23: Condition numbers.

Jan 28: Solving linear equations by LU factorization.  Pivoting

Jan 30: More pivoting (partial), and Positive Definite Matrices.

Feb 4: The Randomized Kaczmarz method of solving linear equations, and condition numbers under perturbation.

Feb 6: Singular values and vectors.

Feb 11-20: Linear Programming

My approach to linear programming is a little unusual.  First, I like to treat it as a geometrically rather than algebraically.  Second, I like to describe it in the polar form rather than the standard.  I can not find any nice treatments of the polar form.  So, I suggest multiple sources, and hope that one resonates with you.

Feb 11: Linear Programming and Convex Sets

Feb 13: Linear Programming: the simplex method and duality, in the Polar

Feb 18: Linear Programming: strong duality, feasibility, Farkas' Lemma.

Feb 20: Linear Programming: fast first-order methods, and overview of what's known

Feb 25: Introduction to Convex Programming.  Convex Functions

Feb 27: Gradient descent for convex functions.

March 2:

March 24 & 26: Lagrange multipliers and the KKT conditions for optimality.

March 31: Polynomial time algorithms for convex programming.

April 2: Introduction to NP.

April 7: MaxCut and some NP-hard problems.


April 9: Exact Cover -> Sparse solutions to linear equations, and solving most linear equations, k-Color, NMF, and low-rank matrix completion.

April 14: Sparse (exact) solutions to linear systems: Orthogonal Matching Pursuit

April 16: Sparse (approximate) solutions to linear systems: LASSO

April 21: Approximating MaxCut

April 23: Matrix completion by nuclear norm minimization, and other stuff I want to say in the last class.


May 6: Final Exam  -- CANCELLED