/Convex-Optimization-Course

Repository for my convex optimization course.

Course: Convex Optimization

Convex Optimization

Course Information

Instructor: Niao He

Course Description

This course is focused on learning to recognize, understand, analyze, and solve unconstrained and constrained convex optimization problems arising in engineering. The course shall focus on the fundamental convexity theory and the algorithmic approaches for (nondifferentiable) convex problems.

Prerequisite

Students are expected to have strong knowledge of linear algebra, real analysis, and multivariate calculus.

Textbook

No textbook is required, but you can refer to my past lecture notes: IE521-cvxopt-lecturenotes-sp17.pdf

Reference books

Some of the course material is covered in for following books:

  1. Boyd & Vandenberghe. Convex Optimization. Cambridge University Press. 2003
  2. Ben-Tal & Nemirovski. Lectures on Optimization III, SIAM. 2013
  3. Bertsekas, Nedich, & Ozdaglar. Convex Analysis and Optimization. Athena Scientific. 2003
  4. Hiriant-Urruty & Lemarechal. Fundamentals of Convex Analysis. Springer. 2001
  5. Ben-Tal & Nemirovski. Lectures on Modern Convex Optimization, SIAM. 2011
  6. Nesterov. Introductory Lectures on Convex Optimization: A Basic Course. Kluwer-Academic. 2003

Topical Outlines

  • Part I: Fundamentals of Convex Analysis (4 weeks): convex sets, convex functions, convex programs, geometry of convexity, Lagrangian duality, optimality condition, and polynomial solvability of convex programming, etc.

  • Part II: Modern Convex Optimization (4 weeks): linear program, second order conic program, semidefinite program, interior point method, etc.

  • Part III: Algorithms for Non-differential Constrained Convex Programs (4 weeks): subgradient method, cutting plane method, bundle method, etc.

  • Part IV: Selective Topics (2 weeks)

Class Schedule

Lecture Date Topic Content Resources
0 January 14 Introduction Introduction to the Course;
1 January 16 Convex Set Topology Review; Convex Sets; Topological Properties of Convex Sets; Carathodory's Representation Theorem [Slides]
2 January 23 Convex Geometry Radons Theorem; Helleys Theorem and Applications; Separation Theorems [Slides]
3 January 28 Separation Theorems Separation Hyperplane Theorem; Strong Separation Hyperplane Theorem; Farkas Lemma; Duality of Linear Programming [Slides]
4 February 4 Convex Functions Convex Functions [Slides]
5 February 6 Convex Functions II Characterizations of Convex Functions; Continuity of Convex Functions; Closed Convex Functions [Slides]
6 February 11 Subgradient and Subdifferential Subgradient; Directional Derivative and Subdifferential Set; Calculus of Subgradient [Slides]
7 February 13 Convex Conjugate Conjugate Function; Conjugate Theory; Minima of Convex Functions [Slides]
8 February 18 Convex Programs and Duality Convex Programs; Convex Theorem on Alternatives; Lagrange Duality [Slides]
9 February 20 Optimality Conditions KKT Conditions; Saddle Point Perspective; Minimax Theorems [Slides]
10 February 25 Solving Convex Programs Accuracy Measure, Oracles, Complexity; Cutting Plane Methods; Center of Gravity Algorithm [Slides]
11 February 27 Polynomial Solvability of Convex Programs Complexity vs Convergence; Center of Gravity; Ellipsoid Method [Slides]
12 March 4 Conic Programming Generalized Inequality; Conic Programs: LP, SOCP, SDP; Applications: norm minimization, sparse group lasso, robust linear program [Slides]
13 March 6 Conic Duality Dual Cone; Conic Duality; SOCP Duality; SDP Duality and Applications [Slides]
14 March 11 SDP Relaxation and Applications SDP for Eigenvalue Optimization; SDP for Max Cut Problem; SDP for Nonconvex QCQP; SDP for Stability of Dynamical Systems [Slides]
15 March 13 CVX Tutorial CVX Tutorial; MATLAB Demonstration [Slides]
16 April 1 Interior Point Method Part I Path Following Scheme; Self-concordant Functions; [Slides]
17 April 5 Interior Point Method Part II Classical Newton Method and Analysis; Newton Method for Self-concordant Functions; Damped Newton Method and Global Convergence [Slides]
18 April 10 Interior Point Method Part III Self-concordant Barriers; Restate Path Following Scheme [Slides]
19 April 15 Interior Point Method Part IV Self-concordant Barriers for LP, SOCP, SDP; Complexity of Interior Point Method; Primal-Dual Path Following Scheme; [Slides]
20 April 17 Subgradient Method Subgradient Method; Choices of Stepsize; Convergence Analysis; [Slides]
21 April 22 Bundle Methods Kelleys Method; Level Set Method; [Slides]
22 April 24 Constrained Subgradient Methods Problems with Functional Constraints; Constrained Level Method [Slides]
23 April 29 Dual Methods Augmented Lagrangian; ADMM [Slides]

License