Courses:

Algebraic Techniques and Semidefinite Optimization >> Content Detail



Syllabus



Syllabus

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



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:


ACTIVITIESPERCENTAGES
Research Project50%
Homework25%
Scribe Notes25%



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 #TOPICSKEY DATES
1Introduction

Review of Convexity and Linear Programming
2PSD Matrices

Semidefinite Programming
3Binary Optimization

Bounds: Goemans-Williamson and Nesterov

Linearly Constrained Problems
4Review: Groups, Rings, Fields

Polynomials and Ideals
5Univariate Polynomials

Root Bounds and Sturm Sequences

Counting Real Roots

Nonnegativity

Sum of Squares

Positive Semidefinite Matrices
Homework 1 out
6Resultants

Discriminants

Applications

The set of Nonnegative Polynomials
7Hyperbolic Polynomials

SDP Representability
Homework 1 due
8SDP Representability

Convex Sets in R2

Hyperbolicity and the Lax Conjecture

Relating SDP-representable Sets and Hyperbolic Polynomials

Characterization
9Binomial Equations

Newton Polytopes

The Bézout and BKK Bounds

Application: Nash Equilibria
10Nonegativity and Sums of Squares

Sums of Squares and Semidefinite Programming

Applications and Extensions

Multivariate Polynomials

Duality and Density
11SOS Applications

Moments

Bridging the Gap
12Recovering a Measure from its Moments

A Probabilistic Interpretation

Duality and Complementary Slackness

Multivariate Case

Density Results
13Polynomial Ideals

Algebraic Varieties

Quotient Rings

Monomial Orderings
Homework 2 out
14Monomial Orderings

Gröbner Bases

Applications and Examples

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

Hilbert Series
16Generalizing the Hermite Matrix

Parametric Versions

SOS on Quotients
17Infeasibility of Real Polynomial Equations

Certificates

The Zero-dimensional Case

Optimization
18Quantifier Elimination

Tarski-Seidenberg

Cylindrical Algebraic Decomposition (CAD)
19Certificates

Psatz Revisited

Copositive Matrices and Pólya's Theorem

Positive Polynomials
20Positive Polynomials

Schmüdgen's Theorem
21Groups and their Representations

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

 








© 2010-2021 OpenCollege.com, All Rights Reserved.
Open College is a service mark of AmeriCareers LLC.