Algebra, Convexity and Optimization
3-4 hours of lectures per week.
Lecturer
Niels Lauritzen
Content
Consider a thief carrying a knapsack with a certain weight limit. Given a collection of items with weight and price tags, which items should he steal and carry away in his knapsack to optimize the total cost? This is an example of an optimization problem called the 0/1-knapsack.
Knapsacks and related optimization problems can be studied in the framework of Gröbner bases using input from algebraic geometry, commutative algebra and convex geometry. The object of the course is the study of optimization problems from an algebraic point of view
We will focus on Gröbner bases from the point of view of convex geometry (the course will contain a complete course in the basics of convex geometry) and algebraic geometry if time permits. The central object is the state polytope which loosely spoken is the convex hull of all possible reduced Gröbner bases of a given ideal. The state polytope was born in Mumford's geometric invariant theory and has turned out to be an extremely useful object in algebra and optimization theory.
Prerequisites
Algebra 1
Literature
B. Sturmfels, ``Gröbner Bases and Convex Polytopes'', American Mathematical Society, Providence 1996 along with explanatory notes and selected recent papers.
Evaluation
Students who do not intend to take a degree in Mathematics or Statistics from the University of Aarhus, but wish to earn credits for a 2.dels course from the Department of Mathematics, should indicate at the beginning of the course that they wish to be examined.
The form of examination for the course will be active participation together with oral or written contributions.
Credits
10 ECTS
Quarter
Spring 2004