Linear and Convex Optimization

CS 257, Fall 2020

Instructor: Bo Jiang

TA: Yichen Zhu (朱一晨), Yunzhuo Liu (刘运卓)


When: Mon 10:00-11:40 am (16 weeks)
Where: Lower Hall 411 (下院411)
Office Hours: by appointment, Software Building 1102-2


Overview

This is an introductory course on convex and linear optimization. Topics include basics of mathematical optimization, convex sets and functions, convex and linear optimization problems, basic algorithms for convex optimization, optimality conditions for unconstrained and constrained optimizations, Lagrange duality.

Requirements: Coursework will include

  • Homework assignments every 1-2 weeks, 50% of course grade.
  • A final exam, 50% of course grade.

Grading policy:

  • NO late homework submission will be accepted.

Honor code:

  • You are encouraged to discuss homework assignments with each other, but write up solutions on your own! Sharing or copying a solution will result in a zero score for the relevant assignment for both parties.
  • If a significant part of your solution is due to someone else or from other sources (books, forums, etc), you should acknowledge the source! Failure to do so will result in a zero score for the relevant assignment.

References

  • [BV] Convex Optimization, by Boyd and Vandenberghe, available free here
  • [CZ] An Introduction to Optimization, by Chong and Zak, 电子工业出版社（翻译版）
  • [B] Nonlinear Programming, by Bertsekas, 3rd Edition, 清华大学出版社（英文影印版）
  • [NW] Numerical Optimization, by Nocedal and Wright, 科学出版社
  • [LY] Linear and Nonlinear Programming, by Luenberger and Ye, 3rd Edition, 世界图书出版公司（英文影印版）

Homeworks

  1. Homework 1. Released 9/14, due 9/21.
  2. Homework 2. Released 9/21, due 9/28.
  3. Homework 3. Released 9/29, due 10/12.
  4. Homework 4. Released 10/12, due 10/19.
  5. Homework 5. Released 10/19, due 10/26.
  6. Homework 6. Released 10/28, due 11/11.
  7. Homework 7. Released 11/2, due 11/9.
  8. Homework 8. Released 11/9, due 11/16.
  9. Homework 9. Released 11/16, due 11/23.
  10. Homework 10. Released 11/23, due 11/30.
  11. Homework 11. Released 11/30, due 12/7.
  12. Homework 12. Released 12/7, due 12/14.
  13. Homework 13. Released 12/14, due 12/23.

Lecture Schedule

The schedule may change as the semester progresses.

Week Date Lecture Topics Readings Assignments
1 9/7 basics of mathematical optimization, examples, global and local minima
  • Slides
  • [BV] 1.1-1.4, A.1-A.4
2 9/14 first- and second-order conditions for unconstrained problems
  • HW 1 out
    		•
    3 9/21 convex sets
  • HW 1 due
  • HW 2 out
    		•
    4 9/28 convex functions
  • HW 2 due
  • HW 3 out
    		•
    5 10/5 NO CLASS (rescheduled to 10/10)
    10/10 more convex functions
    6 10/12 convexity-preserving operations, convex optimization problems
    • Slides
    • [BV] 3.2, 4.1 4.2.1-4.2.4, 4.3-4.3.1
  • HW 3 due
  • HW 4 out
    		•
    7 10/19 convex optimization problems
    • Slides
    • [BV] 4.4-4.4.1, 4.5-4.5.3
  • HW 4 due
  • HW 5 out
    		•
    8 10/26 gradient descent
  • HW 5 due
  • HW 6 out
    		•
    9 11/2 analysis of gradient descent, strong convexity, condition number
  • HW 6 due
  • HW 7 out
    		•
    10 11/9 line search, Newton's method
  • HW 7 due
  • HW 8 out
    • 11 11/16 analysis of Newton's method, damped Newton's method, equality constrained problems
  • HW 8 due
  • HW 9 out
    		•
    12 11/23 Lagrange multipliers method, Newton's method for equality constrained problems
    • Slides
    • [BV] 10.1-10.1.2, 10.2
  • HW 9 due
  • HW 10 out
    		•
    13 11/30 general equality constrained problems, inequality constrained problems and KKT conditions
  • HW 10 due
  • HW 11 out
    		•
    14 12/7 more KKT conditions, Lagrange dual problems
  • HW 11 due
  • HW 12 out
    		•
    15 12/14 weak and strong duality, Slater's condition, duality and KKT conditions
  • HW 12 due
  • HW 13 out
    		•
    16 12/21 review