**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)