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

Enrollment in this course will be limited. If you are considering taking this course, follow the directions below

Who this course is for

This course is designed for graduate students in Statistics & Data Science who need to know about optimization and the essentials of numerical algorithm design and analysis. My intent is to help them design algorithms for Machine Learning and Data Analysis in their own research. The course could also be useful for graduate students in programs in Economics, SOM, and the sciences. It may also be suitable for some undergraduates. The prerequisites are knowledge of linear algebra, multivariate calculus, and probability.

Students who have taken Optimization Techniques (S&DS 430 / ENAS 530 / EENG 437 / ECON 413) probably won’t get much out of this course. Students who have the time to take many courses are encouraged to instead take a combination of Algorithm Design (CPSC 365/366), Numerical Computation (CPSC 440), Applied Numerical Methods I (ENAS 440), Topics in Numerical Computation (CPSC 640), and some more advanced courses in optimization.

This course will eventually serve as an introduction to more advanced courses in optimization. It contains a lot of material that appears in the current (Fall 2019) version of Optimization Techniques. The next time Optimization Techniques is taught (probably in 2021-2022), it will assume this course as a prerequisite.

Topics to be covered.

Please note that this list of topics does not precisely agree with those advertised on Yale Course Search. And, this is the first time this course is being offered. This means that it is an experiment. I might find that I need to adjust the list of topics as we go.

Measuring the running times of algorithms

Lower Bounds and NP Completeness

Systems of Linear Equations

The singular value decomposition

Linear Programming

Convex Programming

Advanced Topics

Note that all of these treatments will be introductory, and we will not get to the most recent developments.

Work for the course

This course will feature regular homework, a midterm, and a final.

The final will be at the standard time: Wedneday, May 6, at 2pm. The midterm take place in class on Tuesday, March 3.


All readings for the course will come from materials that are freely available online (although some will require access from inside Yale or the VPN). Our main references will be

Some other material will come from papers and the lectures notes of the instructor.

Instructions for enrolling

First, add the course in Canvas. Then fill out the enrollment survey. Decisions about who is admitted to the course will be made before the first lecture.