CPSC 406: Computational optimization

Course time and location

Tuesdays and Thursdays 11:00 AM-12:30 PM

Hugh Dempster Pavilion Room 110

Also see

Teaching staff

Office hours well be held in the DEMCO room in the Xwing of the ICICS building (near the Poke restaurant)

Textbook

Introduction to Nonlinear Optimization: Theory, Algorithms, and Applications with MATLAB, Amir Beck (SIAM, 2014). This book is available online through the UBC Library.

Course requirements

One of CPSC 302, CPSC 303, or MATH 307.

Policies

  • No makeup exam for the midterm of final. If you missed the midterm exam you must document a justification.
  • Midterm exam grade will not be counted if it is lower than your final exam grade.
  • To pass the course you must do the assigned coursework, write the midterm and final exams, pass the final exam, and obtain an overall pass average according to the grading scheme.
  • The instructors reserve the right to modify the grading scheme at any time.

Past offerings and other resources

Winter Term 2 2018 (Instructor: Prof. Michael Friedlander)

Some material is also borrowed from UCLA's 236A Linear Programming

Lectures

01 Intro

02 Vectors and Matrices Recommended readings: 1.1, 1.2, 1.3,

03 Unconstrained Optimization Recommended readings: 1.5, 2.1, 2.2,, 7.1, 7.2, 7.3, 8.4 (cvx)

04 Quadratic functions Recommended readings: 1.4, 2.3, 2.4,2.5

05 Least Squares Recommended readings: 3.1,3.2

06 Nonlinear least squares Recommended readings: 3.3, 3.4, 3.5, 3.6, 4.5

07 Convex sets and functions: Recommended readings: Chapter 6

08 Gradient descent Recommended readings: 4.1, 4.2, 4.3,

09 Newton's method Recommended readings: 5.1, 5.2, 5.3

10 Not Quite Newton (skipped)

(ordering is shuffled below)

12 Linear programming applications

13 Geometry of linear polytope (same slides as last year)

14 Simplex method

11 Projected gradient descent Recommended readings: 8.1,8.2, 8.3, 9.1, 9.2, 9.3. Proof of convergence: here

15 Duality

16 Interior point methods

Bonus lecture: A quick survey of online optimization

That's all, folks!