18-799B: Special Topics in Signal Processing: Nonlinear Optimization

Units: 12

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: algorithms. Line-search based algorithms for unconstrained optimization: gradient,quasi-Newton BFGS,Newton. Convergence theory and convergence rates. Algorithms for constrained optimization. The simplex and interior point algorithms for linear programs. Active working set methods for convex quadratic programs. Interior point algorithms for convex programs. Penalty, barrier, augmented Lagrangian and SQP methods for general (nonconvex) programs. Part IV: special topics. Nonsmooth optimization and optimization over manifolds.

Prerequisites: Undergraduate linear algebra, multivariable calculus


Algorithms/Complexity/Programming Languages

Last modified on 2008-12-02

Past semesters:

S15, S14, S13, F12, S12, S11, S10, S09