Nonlinear
Optimization (18799 B,PP)
IST-CMU PhD Course
Spring 2018
Contact
Instructor: João Xavier
jxavier (@) isr.ist.utl.pt
http://users.isr.ist.utl.pt/~jxavier
TA: Hung Tuan
hung.seadc (@) gmail.com
The lectures start February 27,
2018. The schedule is: Tuesdays 15h00-16h30 (room F2) and Thursdays
15h00-16h30 (room QA1.3). Grading: Homework 60% (6
homeworks), final exam 40% (24h take-home exam).
Part I: formulation of optimization problems. Convex sets and functions. Recognizing canonical classes of convex programs: linear, quadratic, posynomial, geometric, second-order cone, semidefinite positive. Usage of software packages. Applications in communications, estimation, approximation, control, pattern recognition, graphs, networks, etc.
Part II: conditions for optimality and duality theory. The Karush-Kuhn-Tucker (KKT) conditions for optimality. Geometrical interpretation of KKT conditions. Dual programs, the duality gap and its geometrical interpretation. Applications of duality: provable lower bounds, problem simplification, problem decomposition, convex relaxations of combinatorial problems (e.g. MAXCUT).
Part III: numerical algorithms with an emphasis on large-scale problems (centralized or distributed). Gradient and subgradient methods: mirror descent, fast Nesterov algorithm for smooth and composite cost functions (FISTA), Frank-Wolfe algorithm. Primal-dual methods: alternate direction method of multipliers (ADMM). Proximal methods. Online optimization.
Textbook (main):
Convex Optimization, S. Boyd and L. Vandenberghe, Cambridge University Press.
Additional references: