|
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 15 years or so. On the conceptual side, emphasis
will be put 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 course will cover interior point
methods for semidefinite programming but emphasis will
be put 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: - ACM 113 (First
course in optimization), ACM 104 (Linear algebra), ACM
116 (Applied probability) or consent of instructor.
Syllabus:
- Review of basic concepts in optimization:
convexity, duality theory, structured optimization
programs; linear programming (LP), second-order cone
programming (SOCP).
- Semidefinite programming (SDP): linear matrix
inequalities, duality in cone programming, log-barrier
and primal-dual interior point methods for SDPs,
applications to combinatorics (relaxation of
combinatorially hard problems), structural design,
robust optimization and machine learning.
- Smooth convex optimization: optimal
first-order methods (Nesterov's algorithm),
complexity analysis.
- Nonsmooth convex optimization: smooth
approximations of nonsmooth functions, prox-functions,
Nesterov's algorithm.
- Mirror-descent algorithms (MDA).
- Applications 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 Stephen Boyd and Lieven Vandenberghe, Cambridge
University Press.
Handouts:
All handouts will be posted online.
Teaching assistants and office hours:
We may or may not have a TA depending on class enrollment.
Grading:
The grade will be determined by 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.
|