Courses:

Algebraic Techniques and Semidefinite Optimization >> Content Detail



Lecture Notes



Lecture Notes

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


LEC #TOPICSLECTURE NOTES
1Introduction

Review of Convexity and Linear Programming
(PDF)
2PSD Matrices

Semidefinite Programming
(PDF)
3Binary Optimization

Bounds: Goemans-Williamson and Nesterov

Linearly Constrained Problems
(PDF)
4Review: Groups, Rings, Fields

Polynomials and Ideals
(PDF)
5Univariate Polynomials

Root Bounds and Sturm Sequences

Counting Real Roots

Nonnegativity

Sum of Squares

Positive Semidefinite Matrices
(PDF)
6Resultants

Discriminants

Applications

The set of Nonnegative Polynomials
(PDF)
7Hyperbolic Polynomials

SDP Representability
(PDF)
8SDP Representability

Convex Sets in R2

Hyperbolicity and the Lax Conjecture

Relating SDP-representable Sets and Hyperbolic Polynomials

Characterization
(PDF)
9Binomial Equations

Newton Polytopes

The Bézout and BKK Bounds

Application: Nash Equilibria
(PDF)
10Nonegativity and Sums of Squares

Sums of Squares and Semidefinite Programming

Applications and Extensions

Multivariate Polynomials

Duality and Density
(PDF)
11SOS Applications

Moments

Bridging the Gap
(PDF)
12Recovering a Measure from its Moments

A Probabilistic Interpretation

Duality and Complementary Slackness

Multivariate Case

Density Results
(PDF)
13Polynomial Ideals

Algebraic Varieties

Quotient Rings

Monomial Orderings
(PDF)
14Monomial Orderings

Gröbner Bases

Applications and Examples

Zero-dimensional Ideals
(PDF)
15Zero-dimensional Ideals

Hilbert Series
(PDF)
16Generalizing the Hermite Matrix

Parametric Versions

SOS on Quotients
(PDF)
17Infeasibility of Real Polynomial Equations

Certificates

The Zero-dimensional Case

Optimization
(PDF)
18Quantifier Elimination

Tarski-Seidenberg

Cylindrical Algebraic Decomposition (CAD)
(PDF)
19Certificates

Psatz Revisited

Copositive Matrices and Pólya's Theorem

Positive Polynomials
(PDF)
20Positive Polynomials

Schmüdgen's Theorem
(PDF)
21Groups and their Representations

Algebra Decomposition
(PDF)
22Sums of Squares Programs and Polynomial Inequalities(PDF)

 








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