Meetings: Mondays and Wednesdays 4:00pm-5:30pm Math. Sci. Building 3106.
Instructor: Jesús A. De Loera.
email: deloera@math.ucdavis.edu
phone: (530)-554-9702
office: 3228 Mathematical Science building.
office hours: Mondays and Wednesdays 5:30-6:30pm or by appointment.
A sure way to contact me is via email.
Text: I will use my own notes, which will be freely available (I am writing a monograph with the same title as the course). Additional references (put on reserve) are (expensive but worth it):
``Geometric Algorithms and Combinatorial Optimization'' by Gr\"ostchel M, L. Lov\'asz and A. Schrijver
``Optimization over the integers'' by D. Bertsimas and R. Weismantel
Course Description: Optimization is a growing part of applied mathematics and engineering. In this topic one seeks to minimize or maximize a function of integer and real variables, subject to constraints on the variables (i.e. equations or inequalities that need to be satisfied by all solutions). The main goals are to find the main mathematical properties, the development and implementation of algorithms to find optimal values and optimal solutions, and the application of these algorithms to real world problems.
Optimization has traditionally used mostly tools from Analysis and Numerical methods to attack its problems (topics that are covered in other courses like Math 258AB, Math 168), but in the past 10 years a considerable number of researchers have employed tools from ``pure'' mathematics, including commutative algebra, number theory, algebraic geometry, Discrete Geometry, Convex Geometry to attack classical problems in various areas of Optimization. This course is an introduction(=invitation!) to this new methodology of research. Without too many prerequisites (below) we will sample several new techniques.
Prerequisites: Strong solid knowledge of undergraduate level algebra, basic analysis (Math 125ABC), and, most important, the mathematical maturity equivalent of a first year graduate student. Prior knowledge of linear programming (=MATH 168) complexity and algorithms (e.g., ECS 122) is a definite plus but will not be assumed. A prior course is a plus, but it is more important to be seriously interested. Any of the algebraic, complexity, or geometric topics used will be revised before hand.
Topics:
First topic: Convex Geometry in linear and semidefinite Optimization.
(week 1) Linear Programming and its Duality
Ellipsoid's Method and its applications
Applications: SDP efficiency, Stable Set and MAXCUT
Second Topic: Global Optimization with non-linear constraints.
The set of Nonnegative Polynomials and global minimization
Sums of Squares and Semidefinite Programming
Real algebra, semi-algebraic geometry, and the PositiveStellensatz
Applications: SDP Representability and semi-algebraic programming.
Third topic: Gr\"obner bases and the Nullstellensatz in Optimization.
Introduction to Gr\"obner bases, Varieties and the Nullstellensatz
Applications: Global Geometry of Central Paths, Lagrange Multipliers, Toric ideals.
Circuits, Test sets, Hilbert and Graver bases.
N-fold matrices.
Fourth topic: Efficient representation of lattices and Optimization:
Lattice algorithms (Hermite Normal form, LLL), Lenstra's algorithm
Barvinok's generating functions
Applications in Integer Optimization.
Grading and Work: The final grades will be based Grading: Final Project 60%, notes-scribe work 40%. Note-scribe work means that students will be responsible to render a nice latex presentation of a topic discussed in class.
Here is the LaTeX template to write the lectures.
An free version of the lecture notes is available here
More LECTURES: Lectures notes (from Goemans-Williamson to Sums of squares)