Syllabus

A list of topics covered in the course is presented in the calendar.

Course Meeting Times

Lectures: 2 sessions / week, 1.5 hours / session

Prerequisites

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.251J or 6.255 / 15.093, 6.253), Basic Probability (e.g., 6.041 / 6.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.

Bibliography

We will use a variety of book chapters and current papers. Some of these are listed in the readings section.

Grading

The final grade will be calculated based on the following weights:

ACTIVITIES PERCENTAGES
Research Project 50%
Homework 25%
Scribe Notes 25%

Homework

Problem sets will be handed out in an approximately biweekly basis and will be due one week later, at the beginning of the lecture on their respective due dates. We expect you to turn in all completed problem sets on time. Late homework will not be accepted, unless there is a prior arrangement with the instructor.

Scribe Work

Each student will also be responsible for editing and/or writing lecture notes from two lectures.

Collaboration Policy

We encourage working together whenever possible: in the tutorials, on the problem sets, and during general discussion of the material and assignments. Keep in mind, however, that the problem set solutions you hand in should reflect your own understanding of the class material. It is not acceptable to copy a solution that somebody else has written.

Calendar

LEC # TOPICS KEY DATES
1 Introduction

Review of Convexity and Linear Programming
 
2 PSD Matrices

Semidefinite Programming
 
3 Binary Optimization

Bounds: Goemans-Williamson and Nesterov

Linearly Constrained Problems
 
4 Review: Groups, Rings, Fields

Polynomials and Ideals
 
5 Univariate Polynomials

Root Bounds and Sturm Sequences

Counting Real Roots

Nonnegativity

Sum of Squares

Positive Semidefinite Matrices
Homework 1 out
6 Resultants

Discriminants

Applications

The set of Nonnegative Polynomials
 
7 Hyperbolic Polynomials

SDP Representability
Homework 1 due
8 SDP Representability

Convex Sets in R2

Hyperbolicity and the Lax Conjecture

Relating SDP-representable Sets and Hyperbolic Polynomials

Characterization
 
9 Binomial Equations

Newton Polytopes

The Bézout and BKK Bounds

Application: Nash Equilibria
 
10 Nonegativity and Sums of Squares

Sums of Squares and Semidefinite Programming

Applications and Extensions

Multivariate Polynomials

Duality and Density
 
11 SOS Applications

Moments

Bridging the Gap
 
12 Recovering a Measure from its Moments

A Probabilistic Interpretation

Duality and Complementary Slackness

Multivariate Case

Density Results
 
13 Polynomial Ideals

Algebraic Varieties

Quotient Rings

Monomial Orderings
Homework 2 out
14 Monomial Orderings

Gröbner Bases

Applications and Examples

Zero-dimensional Ideals
Homework 2 due
15 Zero-dimensional Ideals

Hilbert Series
 
16 Generalizing the Hermite Matrix

Parametric Versions

SOS on Quotients
 
17 Infeasibility of Real Polynomial Equations

Certificates

The Zero-dimensional Case

Optimization
 
18 Quantifier Elimination

Tarski-Seidenberg

Cylindrical Algebraic Decomposition (CAD)
 
19 Certificates

Psatz Revisited

Copositive Matrices and Pólya's Theorem

Positive Polynomials
 
20 Positive Polynomials

Schmüdgen's Theorem
 
21 Groups and their Representations

Algebra Decomposition
Homework 3 out
22 Sums of Squares Programs and Polynomial Inequalities Homework 3 due three days after Lec #22