Overview

This course focuses on recent developments in optimization, specifically on the use of convex optimization to address problems involving polynomial equations and inequalities. The course covers approaches for finding both exact and approximate solutions to such problems. We will discuss the use of duality and algebraic methods to find feasible points and certificates of infeasibility, and the solution of polynomial optimization problems using semidefinite programming. The course covers theoretical foundations as well as algorithms and their complexity. Prerequisites: EE364A or equivalent course on convex optimization.

Lecture notes

  • Introduction (pdf)
  • Convexity (pdf)
  • Maxcut (pdf)
  • Algebra and Duality (pdf)
  • Algebra Geometry Dictionary (pdf)
  • Nullstellensatz (pdf)
  • Groebner bases (pdf)
  • Groebner bases 2 (pdf)
  • Elimination (pdf)
  • Sum of squares (pdf)
  • Lifting and moments (pdf)
  • Positivstellensatz (pdf)
  • Semialgebraic lifting (pdf)
  • Sparse polynomials (pdf)
  • Fourier-Motzkin (pdf)
  • Fourier-Motzkin 2 (pdf)
  • Resultants (pdf)

Homework

  • hw1, due at review session on 10/18
  • BPT 2.10, 2.21, 2.24, 2.28
  • CLO 1.2.1, 1.2.15, 1.4.2, 1.4.3, 1.4.8
  • hw2, due at review session on 11/6.
  • CLO 2.2.2, 2.3.1, 2.4.3, 2.5.1, 2.6.5, 2.7.2, 2.8.1
  • hw3, due at review session on 12/4.
  • BPT 3.16, 3.17, 3.29, 3.52, 3.53, 3.73, 3.89, 3.173, 3.185

Contact

Calendar

  • Sep 25. First class
  • Nov 19-23. Thanksgiving recess
  • Dec 6. Last class