Convex Optimization

The primary goal of this course is to provide ideas and analysis for convex optimization problems that arise frequently in many scientific and engineering disciplines. This includes first-order methods for both unconstrained and constrained optimization problems, duality theory and dual-based methods, and possibly some modern methods for large-scale optimization problems. The course also includes assignments on theory and exercises.

General

Code   CSED700H or AIGS700H
Term   Fall 2022
Audience   PG (main) and UG students at POSTECH

Meet

Lectures   Mondays and Wednesdays 9:30am-10:45am (Room 102 in Eng bldg Ⅱ or online via Zoom)
Office hours   Wednesdays 5-6pm (by appointment)
Online   PLMS

Staff

Instructor   Namhoon Lee (namhoonlee@postech.ac.kr)
TA   Jinseok Chung (jinseokchung@postech.ac.kr) and Jaeseung Heo (jsheo12304@postech.ac.kr)

Schedule

Part 1: Fundamentals

Sep 05 (Mon)   Introduction
Sep 07 (Wed)   Mathematical preliminaries
Sep 14 (Wed)   Convex sets and functions

Part 2: Unconstrained optimization

Sep 19 (Mon)   Gradient methods 1
Sep 21 (Wed)   Gradient methods 2 and more
Sep 26 (Mon)   Subgradient methods 1
Sep 28 (Wed)   Subgradient methods 2
Oct 05 (Wed)   Accelerated gradient methods

Part 3: Constrained optimization

Oct 12 (Wed)   Proximal gradient methods
Oct 17 (Mon)   Mirror descent method
Oct 19 (Wed)   Frank-Wolfe method

Oct 24 (Mon)   Midterm exam

Part 4: Duality

Oct 31 (Mon)   Lagrange duality 1
Nov 02 (Wed)   Lagrange duality 2
Nov 07 (Mon)   Fenchel conjugate 1
Nov 09 (Wed)   KKT conditions
Nov 14 (Mon)   Fenchel conjugate 2
Nov 16 (Wed)   Proximal point method

Part 5: Second-order methods

Nov 21 (Mon)   Newton's method
Nov 23 (Wed)   Quasi-Newton's methods

Part 6: Large-scale optimization

Nov 28 (Mon)   Stochastic gradient methods
Nov 30 (Wed)   Distributed optimization
Dec 05 (Mon)   Non-convex optimization
Dec 07 (Wed)   Variance reduction methods

Dec 12 (Mon)   Guest lecture
Dec 14 (Wed)   Review

Dec 19 (Mon)   Final exam

Assignments

T.B.A.

Grading

Quizzes   10%
Assignments   30%
Midterm exam   30%
Final exam   30%

Acknowledgement

This course will frequently borrow materials from multiple sources including but not limited to the following:
(book) Convex Optimization by Stephen Boyd and Lieven Vandenberghe
(book) Convex Optimization: Algorithms and Complexity by Sébastien Bubeck
(book) Numerical Optimization by Jorge Nocedal and Stephen J. Wright
(lecture) Convex Optimization by Ryan Tibshirani
(lecture) Convex Optimization by Stephen Boyd
(lecture) Optimization Methods for Large-Scale Systems by Lieven Vandenberghe
(lecture) Optimization Algorithms by Constantine Caramanis
(lecture) First-Order Optimization Algorithms for Machine Learning by Mark Schmidt