|
Description: The main goal
of this course is to expose students to modern and
fundamental developments in convex optimization, a
subject which has experienced tremendous growth in the
last 20 years or so. This course builds on EE 364 and
explores two distinct areas. The first concerns cone
programming and especially semidefinite programming
whose rich geometric theory and expressive power makes
it suitable for a wide spectrum of important
optimization problems arising in engineering and applied
science. The second concerns novel and efficient
first-order methods, e.g. Nesterov's method, for smooth
and nonsmooth convex optimization which are suitable for
large-scale problems.
This is an advanced topics course, which will hopefully bring
students near the frontier of current research.
Students are expected to complete a (short) research
project to receive credit.
Prerequisite: EE 364 (Convex
optimization), Math 104 (Linear algebra), Stats 217 or
equivalent (First course in stochastic processes) or
consent of instructor.
Syllabus:
- Conic programming: linear programming (LP),
second-order cone programming (SOCP), semidefinite
programming (SDP), linear matrix inequalities, conic
duality, conic duality theorem.
- Interior point methods: barrier functions,
primal-dual path following methods for LP, SOCP and
SDP.
- Applications of semidefinite programming:
control and system theory, polynomial optimization,
combinatorial and nonconvex optimization, machine
learning.
- The
proximal operator and its properties.
- Proximal gradient methods for smooth and
non-smooth convex optimization, complexity analysis.
- Optimal first-order methods (Nesterov's method and its variants), complexity analysis.
- Nonsmooth convex optimization: conjugate
functions, Moreau's regularization, smooth
approximations of nonsmooth functions by conjugation.
-
Augmented Lagrangian methods and alternating direction
method of multipliers (ADMM).
- Proximal minimization and mirror-descent
algorithms (MDA).
-
Example problems in statistics, signal and image
processing, control theory...
Textbooks:
We will
not require a textbook. The references below contain many of the
topics we shall cover. In particular, the book by Ben-Tal and
Nemirovskii is an excellent companion for the first part of the
course.
- Lectures on Modern Convex Optimization: Analysis,
Algorithms, and Engineering Applications by A. Ben-Tal and
A. Nemirovski, MPS-SIAM Series on Optimization.
- Introductory Lectures on Convex Optimization: A Basic Course by
Y. Nesterov, Kluwer Academic Publisher.
- Convex Optimization by S. Boyd and L. Vandenberghe, Cambridge
University Press.
- Nonlinear Programming by D. Bertsekas, Athena Scientific.
- Convex Analysis and Optimization by D. Bertsekas, A. Nedic, and
A. Ozdaglar Convex Analysis, Athena Scientific.
- Optimization Models by G. Calafiore and L. El Ghaoui, Cambridge
Univ. Press.
Handouts:
All handouts will be posted online.
Teaching assistants and office hours:
- Ernest Ryu () Office hours T 1-2, 380-U Building 380.
- Weijie Su () Office hours M 1-2 and W 1-2, 238 Sequoia Hall.
Grading:
We may have a few homework projects (to be determined
later). The grade will be determined by these problem sets (if
any) and a final project that students will have the freedom
to select from a list according to their own
interest. Students can also define their own project after
communicating with the instructor.
|