Instructor | Kuan Yang & Bo jiang |
---|---|

Lecture times | `Monday` `16:00 - 17:40` (Week 1 - 16) `Thursday` `10:00 - 11:40` (Odd weeks) |

Location | Upper Hall 103 (上院 103) |

Teaching assistant(s) | Zhidan Li (李至丹) & Jiahao Zhao (赵佳豪) |

Office hours | To be determined |

*Convex Optimization*by Stephen Boyd and Lieven Vandenberghe, Cambridge University Press*An Introduction to Optimization*by Edwin K. P. Chong and Stanislaw H. Żak, Wiley.(中文翻译版：最优化导论（第四版），电子工业出版社)

*Lectures on Convex Optimization*by Yurii Nesterov, Springer.Large-Scale Optimization for Data Science at Princeton

Convex Optimization at CMU

- Review of analysis; optimality condition

- Convex sets and their properties; separating hyperplane theorem
- Convex functions and their properties

- Geometric method and simplex algorithm
- LP duality and its applications

Unconstrained problem

- Descent methods: gradient descent and Newton's method
- Smooth and strongly convex functions
- Exact line search and backtracking line search
- Mirror descent
- Subgradient and proximal gradient descent

Equality constrained problem

- Lagrange's multiplier method
- Newton's method and KKT system

Inequality constrained problem

- KKT condition and Lagrange dual
- Strong duality and Slater's condition
- Projected gradient descent
- Inner point method

Week | Date | Topics | Lecture notes | Homework |
---|---|---|---|---|

1 | 09/11 (Mon.) | Introductory examples | Lecture 01 / pdf | |

09/14 (Thurs.) | Optimality condition, review of analysis | Lecture 02 / pdf | HW1 | |

2 | 09/18 (Mon.) | Convex sets | Lecture 03 / pdf | |

3 | 09/25 (Mon.) | Separating hyperplane | Lecture 04 / pdf | |

09/28 (Thurs.) | Convex functions | Lecture 05 / pdf | ||

5 | 10/09 (Mon.) | Convex functions (cont'd) | Lecture 06 / pdf | |

10/12 (Thurs.) | Linear programming | Lecture 07 / pdf | ||

6 | 10/16 (Mon.) | LP duality and applications | Lecture 08 / pdf | |

7 | 10/23 (Mon.) | Unconstrained optimization, gradient descent method | Lecture 09 / pdf | |

10/26 (Thurs.) | Analysis of gradient descent, smoothness and strong convexity | Lecture 10 / pdf | ||

8 | 10/30 (Mon.) | Newton's method | Lecture 11 / pdf | |

9 | 11/06 (Mon.) | Proximal gradient descent | Lecture 12 / pdf | |

11/09 (Thurs.) | Bregman divergence | Lecture 13 / pdf | ||

10 | 11/13 (Mon.) | Mirror descent | Lecture 14 / pdf | |

11 | 11/20 (Mon.) | Lagrange multiplier method | Lecture 15 / pdf | |

11/23 (Thurs.) | Lagrange multiplier method (cont'd) | Lecture 16 / pdf | ||

12 | 11/27 (Mon.) | Newton's method and KKT system | Lecture 17 / pdf | |

13 | 12/04 (Mon.) | Inner point and barrier methods | Lecture 18 / pdf | |

12/07 (Thurs.) | KKT condition | Lecture 19 / pdf | ||

14 | 12/11 (Mon.) | Projected gradient descent | Lecture 20 / pdf | |

15 | 12/18 (Mon.) | Lagrange dual function and problem | Lecture 21 / pdf | |

12/21 (Thurs.) | Strong duality and Slater's condition | Lecture 22 / pdf | ||

16 | 12/25 (Mon.) | Review and summary | Lecture 23 / pdf |