CSE 190 - Discrete and Continuous Optimization

Syllabus

  1. Linear algebra algorithms
  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