# 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.

• My lecture notes
• Solving linear equations by GD: Solomon, Chapter 11.1, or LY 8.2 or NW 3.3.  Note these often talk about a PSD matrix M or Q, which is our ATA.
• Reading about forward and backward error: Solomon 2.2, or Higham's Accuracy and Stability of Numerical Algorithms, 1.5.
• First problem set out today.

Jan 23: Condition numbers.

• Suggested reading: Demmel, Applied Numerical Linear Algebra, Sections 2.2.
• Solomon, Section 4.3.2.
• My lecture notes

Jan 28: Solving linear equations by LU factorization.  Pivoting

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

• Reading: Solomon, Chapter 3, or Trefethen & Bau Chapters 22 & 23
• Strassen’s algorithm starts to win in practice around n = 100.

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

• Reading: BV Sections 2.1, 2.2 and 2.5, and 4.3 (not 4.3.1 or 4.3.2)
• My lecture notes

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.

• The results that I will present appear as
• Theorem 1 in Section 8.2 of LY, and
• The analysis in Section 9.3.1 of BV
• my lecture notes

March 2:

• In class Midterm (10% of grade)

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.

• We will use the hardness of MaxCut to prove that the following problems are NP-hard:
• Maximizing a convex function over a convex polytope.
• Finding the maximum norm point in a polytope.
• Approximating the p-norm of a matrix, for p > 2.
• An introduction to maxcut can be found on Wikipedia, and some discussion of our first goal is in this blog post .
• The result for matrix p-norms appears in Section 6 of the paper Approximating Matrix p-norms by Bhaskara and Vijayaraghavan.  (warning: there are a few typos in that section, which I think I have fixed in my notes).
• my lecture notes, and what I wrote in class

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

• I can't find good references for most of this.  The papers I reference are:
• Peeters, "Orthogonal Representations over Finite Fields and the Chromatic Number of Graphs"
• Shitov, "A short proof that NMF is NP-hard" (warning - haven't checked it carefully)
• Vavasis, "On the complexity of nonnegative matrix factorization"
• For more on NMF, I recommend "Computational Limits for Matrix Completion" by Hardt, Meka, Raghavendra, and Weitz.
• my lecture notes,

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