Instructor | Kuan Yang |
---|---|

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

Location | Upper Hall 213 (上院 213) |

Teaching assistant(s) | Canzhe Zhao (赵灿哲) & Jiaxin Song (宋家鑫) |

Office hours | `Thursday (even)` `19:00 - 21:00` at Room 1319, School of Software |

`12/12`

Homework 8 announced, deadline: Dec. 23.`12/01`

Homework 7 announced, deadline: Dec. 9.`11/22`

Homework 6 announced, deadline: Nov. 29.`11/02`

Homework 5 announced, deadline: Nov. 11.`10/25`

Homework 4 announced, deadline: Nov. 2.`10/14`

Homework 3 announced, deadline: Oct. 25.`09/30`

Homework 2 announced, deadline: Oct. 14.`09/21`

Homework 1 announced, deadline: Oct. 7.

*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.(中文翻译版：最优化导论（第四版），电子工业出版社)

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

Equality constrained problem

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

Inequality constrained problem

- KKT condition and Lagrange dual
- Projected gradient descent

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

1 | 09/15 (Thurs.) | Introduction to the course | Lecture 01 / notes | |

2 | 09/19 (Mon.) | Analysis in vector spaces (I): compact sets, continuity, differential | Lecture 02 / notes | HW1 |

3 | 09/26 (Mon.) | Analysis in vector spaces (II): Hessian, definite matrices | Lecture 03 / notes | |

09/29 (Thurs.) | Geometry: affine and convex sets, convex hull, polytope, simplex | Lecture 04 / notes | HW2 | |

5 | 10/10 (Mon.) | Separating hyperplane theorem, supporting hyperplane theorem | Lecture 05 / notes | |

10/13 (Thurs.) | Convex functions, midpoint convexity | Lecture 06 / notes | HW3 | |

6 | 10/17 (Mon.) | First and second order conditions, convexity-preserving operations | Lecture 07 / notes | |

7 | 10/24 (Mon.) | Definition of convex optimization problems, linear programming | Lecture 08 / notes | HW4 |

10/27 (Thurs.) | Fundamental theorem of linear programming, simplex method | Lecture 09 / notes | ||

8 | 10/31 (Mon.) | LP duality and applications | Lecture 10 / notes | HW5 |

9 | 11/07 (Mon.) | Unconstrained optimization, introduction to gradient descent | Lecture 11 / notes | |

11/10 (Thurs.) | Convergence of gradient descent, smoothness and convergence rate | Lecture 12 / notes | ||

10 | 11/14 (Mon.) | Strong convexity, exact line search | Lecture 13 / notes | |

11 | 11/21 (Mon.) | Backtracking line search, Armijo's condition, Newton's method | Lecture 14 / notes | HW6 |

11/24 (Thurs.) | Newton's method (cont'd), Proximal gradient descent, LASSO, sub-gradients | Lecture 15 / notes | ||

12 | 11/28 (Mon.) | Equality constrained optimization, Lagrange multiplier method | Lecture 16 / notes | HW7 |

13 | 12/05 (Mon.) | Lagrange multiplier (cont'd), implicit function theorem, tangent space, second-order condition | Lecture 17 / notes | |

12/08 (Thurs.) | KKT system, Newton's method | Lecture 18 / notes | ||

14 | 12/12 (Mon.) | Inequality constraints, KKT condition | Lecture 19 / notes | HW8 |

15 | 12/19 (Mon.) | Lagrangian function and dual, strong duality, Slater's condition | Lecture 20 / notes | |

12/22 (Thurs.) | Slater's condition (cont'd), Projected gradient descent | Lecture 21 / notes | HW9 | |

16 | 12/26 (Mon.) | Review and summary | Course summary |