CS2601: Linear and Convex Optimization

Shanghai Jiao Tong University, Fall 2021


Course Information

InstructorKuan Yang
Lecture timesMonday   18:00 - 19:40  (Week 1 - 16)
Thursday 08:00 - 09:40  (Even weeks)
LocationMiddle Hall 411 (中院 411)
Teaching assistant(s)Guoliang Qiu (邱国良)
Office hoursWednesday 14:00 - 15:00 at Room 1402, School of Software


News and Announcements


Textbook and References


Lecture Schedule

109/13 (Mon.)Introduction to the courseLec.1 manuscript 
(W2 Mon.)
Analysis in vector spaces (I):
compact sets, continuity, differential
Lec.2 manuscriptHW1
209/23 (Thurs.)Analysis in vector spaces (II):
Hessian, definite matrices
Lec.3 manuscript 
309/27 (Mon.)Geometry: affine and convex sets,
convex hull, polytope, simplex
Lec.4 manuscriptHW2
(W4 Thurs.)
Separating hyperplane theorem,
supporting hyperplane theorem
Lec.5 manuscript 
510/11 (Mon.)Convex functions, midpoint convexityLec.6 manuscriptHW3
610/18 (Mon.)First and second order conditions,
convexity-preserving operations
Lec.7 manuscript 
 10/21 (Thurs.)Convexity-preserving operations,
inequalities, optimization problems
Lec.8 manuscriptHW4
710/25 (Mon.)Linear programming, simplex methodLec.9 manuscript 
811/01 (Mon.)Farkas' lemma, duality of LPLec.10 manuscriptHW5
 11/04 (Thurs.)Applications of LP duality,
unconstrained optimization,
introduction to gradient descent
Lec.11 manuscript 
911/08 (Mon.)Convergence of gradient descent,
discrete-time Lyapunov's stability
theorem, -smooth functions,
convergence rate for fixed step size
Lec.12 manuscript 
1011/15 (Mon.)-strongly convex functions,
exponential convergence rate,
exact line search method,
Newton's method for finding roots
Lec.13 manuscript 
 11/18 (Thurs.)Backtracking line search method,
Newton's method for optimization
Lec.14 manuscriptHW6
1111/22 (Mon.)Newton's method (cont'd),
Proximal gradient descent
Lec.15 manuscript 
1211/29 (Mon.)Properties of proximal mapping,
equality constrained optimization,
optimality condition for linear
constraints, submanifolds
Lec.16 manuscript 
 12/02 (Thurs.)Implicit function theorem,
tangent space, differential on
submanifolds, Lagrange multiplier
Lec.17 manuscript 
1312/06 (Mon.)Lagrange multiplier (cont'd),
Second-order condition,
Solving quadratic optimization
Lec.18 manuscriptHW7
1412/13 (Mon.)Newton's method, KKT conditionLec.19 manuscript 
 12/16 (Thurs.)KKT condition (cont'd), Lagrange dualLec.20 manuscriptHW8
1512/20 (Mon.)Weak and strong duality,
Slater's condition for convex problems
Lec.21 manuscript 
1612/27 (Mon.)Projected gradient descent,
introduction to interior-point methods
Lec.22 manuscriptHW9
 12/30 (Thurs.)Review and summaryCourse summary