CPSC 536M:
Convex Analysis and Optimization

Convex optimization is a key tool for analyzing and modeling a range of computational problems that arise in machine learning, signal and image processing, theoretical computer science, operations and logistics, and other fields. It’s also the backbone for other areas of optimization, including algorithms for nonconvex problems. This course aims to provide a self-contained introduction to a few of the many geometric and intuitive ideas in convex analysis and their usefulness for understanding and developing computationally-efficient algorithms for a range of scientific and engineering problems.

Syllabus

This list represents a tentative outline of the topics covered.

Part 1: Convex geometry

• convexity-preserving operations
• derived sets (closure, relative interior, extreme points, faces)
• projection onto convex sets, separation
• conic approximations: tangent and normal cones
• polarity

Part 2: Convex analysis

• epigraphical view
• convexity-preserving operations, infimal convolution, perspective transform, smoothing
• differentiable and nondifferentiable functions
• support functions: correspondence with convex sets; norms and duals; gauges and polars
• dual operations

Part 3: Convex optimization

• problem types: linear and quadratic optimization, conic programming (second-order and semi-definite optimization)
• applications of structured optimization, including compressed sending, matrix completion, and phase retrieval
• Lagrange and conjugate duality
• first-order methods for unconstrained and nonsmooth problems, including proximal gradient, ADMM, Frank-Wolfe, monotone operator splitting
• interior methods for conic problems

Target Audience

This course is intended for students who wish to learn the underpinnings of convex optimization and are considering research in the area. Students looking to gain more practical experience with optimization (e.g., how to use various solvers) may wish to instead consider CPSC 406, which will be taught in Term 2.

Prerequisities

Background in vector calculus, linear algebra, and basic real analysis.

Grading

• Homework assignments. Several homework assignments involving both theoretical and computational exercises.
• Lecture scribe. Every student will transcribe notes for one or more lectures (depending on the class size). These notes will be made available to others in the class.
• Course project. A project will be assigned that will require deriving, implementing, and applying an optimization algorithm to solve a problem numerically. A short report (4-6 pages) will be required and will be evaluated for mathematical correctness, quality of the software implementation, and presentation. This will be due in the last week of term.
• Grade distribution (tentative): 50% homework; 50% class project.

Auditors and Undergraduates

Auditors are welcome. Graduate students who wish to audit, please bring a graduate registration form to the first lecture. Undergraduate students who wish to take the course for credit should fill out an undergraduate registration form.

References

The course isn’t based on any one particular text. These references should be helpful for further reading.

• Bertsekas, D. P., Convex optimization theory. Athena Scientific, 2009
• Boyd, S., and Vandenberghe, L. Convex optimization. Cambridge University Press, 2004
• Hiriart-Urruty, J.-B., and Lemaréchal, C., Fundamentals of convex analysis. Springer, 2012.
• Rockafellar, R. T., Convex analysis. Princeton University Press, 2015
• Rockafellar, R. T., and Wets, R. J-B., Variational analysis. Springer, 2009