Algebraic Techniques and Semidefinite Optimization

Lecture Notes

The lecture notes provided below are preliminary and an ongoing work.

LEC #

TOPICS

LECTURE NOTES

1

Introduction

Review of Convexity and Linear Programming

(PDF)

2

PSD Matrices

Semidefinite Programming

(PDF)

3

Binary Optimization

Bounds: Goemans-Williamson and Nesterov

Linearly Constrained Problems

(PDF)

4

Review: Groups, Rings, Fields

Polynomials and Ideals

(PDF)

5

Univariate Polynomials

Root Bounds and Sturm Sequences

Counting Real Roots

Nonnegativity

Sum of Squares

Positive Semidefinite Matrices

(PDF)

6

Resultants

Discriminants

Applications

The set of Nonnegative Polynomials

(PDF)

7

Hyperbolic Polynomials

SDP Representability

(PDF)

8

SDP Representability

Convex Sets in R2

Hyperbolicity and the Lax Conjecture

Relating SDP-representable Sets and Hyperbolic Polynomials

Characterization

(PDF)

9

Binomial Equations

Newton Polytopes

The Bézout and BKK Bounds

Application: Nash Equilibria

(PDF)

10

Nonegativity and Sums of Squares

Sums of Squares and Semidefinite Programming

Applications and Extensions

Multivariate Polynomials

Duality and Density

(PDF)

11

SOS Applications

Moments

Bridging the Gap

(PDF)

12

Recovering a Measure from its Moments

A Probabilistic Interpretation

Duality and Complementary Slackness

Multivariate Case

Density Results

(PDF)

13

Polynomial Ideals

Algebraic Varieties

Quotient Rings

Monomial Orderings

(PDF)

14

Monomial Orderings

Gröbner Bases

Applications and Examples

Zero-dimensional Ideals

(PDF)

15

Zero-dimensional Ideals

Hilbert Series

(PDF)

16

Generalizing the Hermite Matrix

Parametric Versions

SOS on Quotients

(PDF)

17

Infeasibility of Real Polynomial Equations

Certificates

The Zero-dimensional Case

Optimization

(PDF)

18

Quantifier Elimination

Tarski-Seidenberg

Cylindrical Algebraic Decomposition (CAD)

(PDF)

19

Certificates

Psatz Revisited

Copositive Matrices and Pólya's Theorem

Positive Polynomials

(PDF)

20

Positive Polynomials

Schmüdgen's Theorem

(PDF)

21

Groups and their Representations

Algebra Decomposition

(PDF)

22

Sums of Squares Programs and Polynomial Inequalities

(PDF)

 

Assignments

Homework 1 (PDF)

Homework 2 (PDF)

Homework 3 (PDF)