|
Description: The main goal
of this seminar-style course is to expose students to
modern and fundamental developments in convex
optimization, a subject which has experienced tremendous
growth in the last 15 years or so. On the conceptual
side, emphasis will be put on conic programming and
especially on 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. On the
algorithmic side -- the main focus -- emphasis is on
novel and efficient first-order methods for smooth and
nonsmooth convex optimization which are suitable for
large-scale problems.
This is an advanced topics course and 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.
Meeting times:
We will meet most weeks only on Monday and Wednesday. I will
occasionally have to skip a lecture because of planned travels
in which case I would like to meet on a few Fridays as well if
this is all right.
Syllabus:
- Conic programming: linear programming (LP),
second-order cone programming (SOCP), semidefinite
programming (SDP), linear matrix inequalities, conic
duality, conic duality theorem.
- Applications of semidefinite programming:
control and system theory, combinatorial and nonconvex
optimization, machine learning.
- Smooth convex optimization: gradient descent,
optimal first-order methods (Nesterov's method and its
variants), complexity analysis.
- Nonsmooth convex optimization: conjugate
functions, smooth approximations of nonsmooth
functions by conjugation, prox-functions, Nesterov's
method for composite functions.
- Proximal minimization and mirror-descent
algorithms (MDA).
-
Augmented Lagrangian methods and alternating direction
method of multipliers (ADMM).
-
Example problems in statistics, signal and image
processing, control theory...
Textbooks:
- 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.
These books are on reserve at the Math/CS library.
Handouts:
All handouts will be posted online.
Teaching assistants and office hours:
We have not been assigned a TA at the moment.
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.
|