CSE 190 - Discrete and Continuous Optimization

Syllabus

1. Linear algebra algorithms
• Study guide 1: LU factorization
• Study guide 2: Least squares problem
• Eigenvalues and eigenvectors: Notes I (Gilbert and Strang)
• Eigenvalues and eigenvectors: Notes II (Paturi)
• Article on singular value decomposition (Dan Kalman)
• MIT notes on singular value decomposition (Gilbert and Strang)
• Chapter on singular value decomposition from Lay's book (Lay)
• Youtube video that animates basic linear algebra concepts
2. Nonlinear optimization
3. Discrete Optimization
   • What is linear programming?
   • Linear programming formulations
   • Linear programming theory
   • Simplex method
   • Duality
   • Applications

Textbooks

1. Numerical Algorithms: Methods for Computer Vision, Machine Learning, and Graphics, Justin Solomon
2. A free copy the book is available from Justin Solomon's web page at http://people.csail.mit.edu/jsolomon/
3. Understanding and using linear programming, Jiri Matousek and Bernd Gärtner (accessible with UC San Diego credentials)

Problem Sets

1. Solving linear programs by hand
2. Properties of feasible regions
3. Formulating linear programs
4. Linear programs in canonical form
5. Simplex method
6. Duality

Supplementary Reading

1. Algorithms by Dasgupta, Papadimitriou, and Vazirani
2. Understanding machine learning: From theory to algorithms
3. Linear programming solution types
4. Perceptron Classifiers (Charles Elkan)
5. Understanding and using linear programming, Jiri Matousek and Bernd Gärtner (accessible with UC San Diego credentials)
   
6. Approximation algorithms and semidefinite programming, Bernd Gärtner
7. Introduction to linear optimization, Bertsimas, Tsitsiklis, and Tsitsiklis
8. Linear and integer programming, Vince Conitzer
9. Applied mathematical programming, Bradley, Hax, and Magnanti
10. Introduction to optimization: Models and Methods, a course at Harvard University
11. Combinatorial optimization, Cook, Cunningham, Pulleyblank, and Schrijver
12. Combinatorial algorithms: theory and algorithms, Bernhard Korte and Jens Vygen
13. Operations Research Models and Methods, Paul Jensen, Jonathan Bard
14. Linear Programming Lecture Notes by Christopher Griffin
15. Linear and nonlinear programming, David Luenberger and Yinyu Ye, 4th edition, Springer
16. Linear and nonlinear programming, David Luenberger and Yinyu Ye, 3rd edition, Springer