CPSC 536M:
Convex Analysis and Optimization

Convex Analysis and Optimization

• Schedule: Wed 9:00am-12:00pm
• Venue: MATH 104

Course Overview

Convex optimization serves as a fundamental tool for addressing a wide array of computational problems, including those in machine learning, statistical signal and image processing, and theoretical computer science. This course offers a thorough introduction to key geometric concepts in convex analysis, aimed at equipping students with the knowledge to develop and understand computationally-efficient algorithms applicable to various scientific and engineering domains.

Syllabus Outline

Here is a broad overview of the topics covered.

Part 1: Convex sets

• convexity-preserving operations, generated sets, atomic sets
• projection and separation of sets
• cones, duality, and polarity

Part 2: Convex functions

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

Part 3: Convex Optimization

• problem classes: linear, quadratic, conic programming
• structured optimization applications: compressed sensing, matrix completion
• Lagrange and conjugate duality
• first-order methods for unconstrained and nonsmooth problems: subgradient, proximal gradient, and conditional gradient techniques

Target Audience

This course is intended for students who aim to delve into the theoretical aspects of optimization, especially those considering research in this field. Students more interested in practical optimization (e.g., solver usage) may prefer CPSC 406 (Computational Optimization), offered in Term 2.

Prerequisites

A solid foundation in vector calculus, numerical linear algebra, and real analysis is essential. This course is mathematically rigorous; a superficial background won’t suffice. To assess your readiness, take this online self-assessment on numerical linear algebra.

Grading

• Homeworks, 2 sets: 40%
• Writing assignment: 20%
• Course project: 40%

Auditors and Undergraduates

• Auditors: Graduate students wishing to audit should submit a graduate registration form to the CS front office.
• Undergraduates: Those wanting to enroll for credit must obtain the instructor’s permission and submit an undergraduate registration form.

Suggested References

• 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