6.972 Algebraic Techniques and Semidefinite Optimization (H)

L TR2:30-4, Room 36-155
Professor Pablo Parrilo, parrilo@csail.mit.edu, Room 32-D726
Prereq.: see below
3-0-9

This subject qualifies as a Communication, Control, and Signal Processing Engineering Concentration subject.

This research-oriented course will focus on algebraic and computational techniques for optimization problems involving polynomial equations and inequalities, with particular emphasis in the connections with semidefinite optimization.

The course will develop in a parallel fashion algebraic and numerical approaches to polynomial systems, with a view towards methods that simultaneously incorporate both elements. We will study both the complex and real cases, with an emphasis in techniques of general applicability, stressing convexity-based ideas, complexity results, and efficient implementations. Although we will use examples from several engineering areas, particular emphasis will be given to those arising from systems and control applications.

A nonexhaustive list of topics to be covered in this course include:

- Semidefinite programming

- Groebner bases

- Resultants and discriminants

- Newton polytopes and polyhedral homotopies

- Eigenvalue methods for zero dimensional systems

- Quantifier elimination, Tarski-Seidenberg

- Semidefinite relaxations for combinatorial problems

- Hyperbolic polynomials

- Sum of squares techniques

- Symmetry reduction methods (e.g., in Markov chains)

Besides general mathematical maturity, The minimal suggested requirements for the course are the following: linear algebra (e.g., 18.06 / 18.700), a background course on linear optimization or convex analysis (e.g., 6.251 or 6.255, 6.253), basic probability (6.041/431). Familiarity with the basic elements of modern algebra (e.g., groups, rings, fields) is encouraged. Knowledge of the essentials of dynamical systems and control (e.g., 6.241) is recommended, but not required.