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 |