TUM – TUM – Menü

 

 
Algebraic and Geometric Techniques for Optimization (MA 5210)

lecture

 

Lectures: Prof. Dr. Jesus De Loera
Exercises: Dr. Steffen Borgwardt

News Dates of lectures/exercise classes and office hours Lecture notes Problem sheets Literature FAQ

Optimization is a vibrant growing area of Applied Mathematics. Its many successful applications depend on efficient algorithms and this has pushed the development of theory and software. In recent years there has been a resurgence of interest to use ``non-standard'' techniques to estimate the complexity of computation and to guide algorithm design. New interactions with fields like algebraic geometry, representation theory, number theory, combinatorial topology, algebraic combinatorics, and convex analysis have contributed non-trivially to the foundations of computational optimization. This course will be an introduction to the new techniques used in Optimization that have foundation in algebra (number theory, commutative algebra, real algebraic geometry, representation theory) and geometry (convex and differential geometry, combinatorial topology, algebraic topology, etc).

In these introductory lectures I will present these new approaches to all senior students. Topics to be included are: Convex and linear optimization (topological tools for on the simplex method, differential geometry and curvature for the central paths of interior point methods), Integer programming and Combinatorial optimization (Graver bases, Generating functions, Nullstellensatz for combinatorial problems), Nonlinear Global Optimization (sum of square methods, semidefinite programming, compressed sensing, cone programming and hyperbolic geometry).

News

  • 25.07.13: The deadline for submission of your projects has been extended until August 8th.
  • 15.07.13: Here are some details on the files you are to submit as part of your project: Create a folder "Name_Firstname" and put all of your files in there. Name your files "solutions_Name", "slides_Name", "presentation_Name", "exercisevideo_Name". Bring these on an USB stick to Steffen Borgwardt. The files then are copied from the stick, and you get a confirmation that you submitted your files. Thanks!
  • 21.06.13: There will be no exercise class on July 2nd.
  • 18.06.13: Recall that you have meetings with Prof. De Loera today or tomorrow, to discuss the contents of your main presentation!
  • 18.06.13: The Projects section has been updated with the announcements from the last lecture: Please note that you are asked to present the key concepts and contents of your book chapter in your main presentation.
  • 31.05.13: The announced two-week break begins now! See you again in the week of June 17th to June 21st!
  • 31.05.13: Programming examples for sheets 2 and 3 are online.
  • 31.05.13: Under Literature you now also find a file with download links for software.
  • 31.05.13: If you are working on project B, you only have to provide solutions to a bit more than 50% of the exercises in the sections. You are free to choose the exercises you work on, but a smart choice of them will be part of the evaluation of your project. E.g., make sure you work on exercises to many different subsections, and that you work on interesting, not 'easy' questions. --- Remainder of this news removed, as outdated.
  • 28.05.13: In the project section, you find a short overview over the exercises to present.
  • 28.05.13: If you are participating in the projects, remember to register for the exam in tumonline. The registration is open.
  • 28.05.13: Recall to contact Prof. Loera for fixing a time on June 18th or 19th, to have a short discussion. There will be no exercise class on June 18th!
  • 28.05.13: Added final details on literature of certificate projects. (Revised.)
  • 24.05.13: Recall that on Tuesday 28th, there will be a lecture. On Friday 31st, there will be an exercise class in which we give an introduction to video recording yourself in a presentation. In these two slots, we fix the sheet exercises you will present in your video (step 4).
  • 24.05.13: Use the two-week break in our regular schedule to read the book chapters of the project! In the week from June 17th to June 21st, there will be short interviews to discuss the topics you are working on.
  • 17.05.13: By request, the exercise class has been moved to Tuesday, 14:15 - 15:45, in room MI 01.09.014.
  • 14.05.13: More details about the projects are online.
  • 13.05.13: Tomorrow's exercise class once more will be more from 12:15 - 13:45. Finding a new slot proves more difficult than expected, and will probably be done by next week.
  • 13.05.13: The literature reference for both projects is final now.
  • 11.05.13: The literature reference for project A is TBA.
  • 10.05.13: The information about obtaining a certificate, as announced in the first lecture, has been added under the point Project. More details TBA.
  • 06.05.13: IMPORTANT The Friday lecture was moved to 14:15 - 15:45 as requested, one hour earlier than before.
  • 06.05.13: First update to the lecture notes section.
  • 01.05.13: There will be a colloquium of June 19th on the topic "Algebraic and Topological Methods in Linear programming''. More details TBA.
  • 01.05.13: Prof. De Loera will give a talk on "Linearizing Hilbert Nullstellensatz and the Orientability of Matroids" in the next SFB 109 colloquium in room 02.06.011, on May 7th, starting at 16:15. Then Prof. Richter-Gebert will be speaking about "Complex matroids: rigidity and syzygies", starting at 17:30.
  • 24.04.13: Exercise classes begin on May 7th.
  • 24.04.13: If you plan on attending the lecture, please register for the exercise class in the tumonline system until April 30th.
  • 17.04.13: Added literature.
  • 12.04.13: The first lecture will be held on May 2nd.
  • 31.03.13: Added an exception to the lecture and exercise schedule, for the week from May 27th to May 31st.
  • 28.03.13: Lecture and exercise rooms, dates and times are online.
  • 20.03.13: (edited) The course will consist of TBA lectures (90 minutes per lecture).

Dates of lectures/exercise classes and office hours

The lecture will be broken into two parts:

1) first 5 weeks from April 30th 2013 to May 31st

2) Second half from June 16th to July 12th (4 more lectures + student projects presentations).

Type Day Time Room Teacher/Tutor
Lecture Thursday 12:15-13:45 MI 02.08.011 De Loera
Lecture Friday 14:15-15:45 MI 02.08.011 De Loera
Exercises Tuesday 14:15-15:45 MI 01.09.014 Borgwardt

In the week from May 27th to May 31st, the Tuesday slot is used for a lecture, the Friday slot is used for the exercises.

Person Office hours (during semester)
Prof. Dr. Jesus De Loera by appointment
Dr. Steffen Borgwardt by appointment

Lecture notes

Slides Video lecture (part 1) Video lecture (part 2) Video lecture (part 3) Date of announcement
lecture1.pdf video1-a  video1-b    May 2nd
lecture2.pdf video2-a  video2-b    May 3nd
lecture3.pdf video3      May 10th
lecture3+4.pdf video4      May 16th
lecture5.pdf video5      May 17th
lecture6.pdf video6      May 23rd
lecture7.pdf video7      May 24th
lecture8.pdf video8      May 28th
lecture9.pdf video9      June 20th and later
monographlectures.pdf video10      June 20th and later
lecture10and11.pdf video11      June 28th
lectures_final.pdf       July 4th and later

Problem sheets

Problem sheets Solutions Online version Date of announcement Programming examples
sheet01_problems.pdf sheet01_solutions.pdf May 7th May 7th  
sheet02_problems.pdf sheet02_solutions.pdf May 14th May 14th sedumi_example.m
sheet03_problems.pdf will be uploaded after Aug 1st   May 24th exerciseA.cocoa5, exerciseB.cocoa5
sheet04_problems.pdf   July 5th, original version of 4.4 correct May 28th  
sheet05_problems.pdf sheet05_solutions.pdf   June 25th  
sheet06_problems.pdf sheet06_solutions.pdf   July 9th cuww1, cuww1.cost, magic4x4, transport, transport2

Project

NEWS: You find your assigned exercises in the file Exercises_for_project.docx

To obtain a certificate for the course, we require participation in a project. You will be able to choose from two topics - see the slides of lecture 1.
  • Project A: Transportation problems and Graver bases. (Part II of De Loera, Hemmecke, Köppe. Algebraic and Geometric Ideas in the Theory of Optimization. (pages 61-102))
  • Project B: Positivstellensatz and Semidefinite Programming. (Chapters 3.1 and 3.2 of Blekherman, Parrilo, Thomas. Semidefinite Optimization and Convex Algebraic Geometry. (pages 47-86))

The project will consist of the following steps:
  • Read the specified book chapters and solve the corresponding exercises. Write down your solutions in LaTeX.
  • Create a LaTeX (or powerpoint) slide presentation and ...
  • ... a video (at most 30 minutes long!) in which you explain the key theorems and concepts of Project A or B.
  • Create a video in which you explain the solution to one or two selected exercises from the exercise classes. (At most 10 minutes long!)

For the final grade, these steps are weighted 20%, 30%, 30%, 20%. All of them are due until Aug 8th.

Please note the following:
  • The selection of exercises for presentation is performed in the class on May 28th.
  • A presentation of Camtasia will be done in the class on May 31st.
  • You are required to contact borgwardt@ma.tum.de informally about your participation in the projects before May 24th.
  • You also have to register officially for an 'exam' for our lecture in the tumonline system, as usual.

Literature

  • De Loera, Hemmecke, Köppe. Algebraic and Geometric Ideas in the Theory of Optimization. MPS-SIAM Series on Optimization.
  • Blekherman, Parrilo, Thomas. Semidefinite Optimization and Convex Algebraic Geometry. MPS-SIAM Series on Optimization.
  • Onn. Nonlinear Discrete Optimization: An Algorithmic Theory. EMS Zurich Lectures in Advanced Mathematics.

A list of some of the most important software package URLs for the lecture and projects: download_links.txt

FAQ

Ask away! (borgwardt@ma.tum.de)

Research Unit M9


Department of Mathematics
Boltzmannstraße 3
85748 Garching b. München
Germany
phone:+49 89 289-16858
fax:+49 089 289-16859
sekretariat-m9ma.tum.de

Professors

Prof. Dr. Peter Gritzmann
Applied Geometry and Discrete Mathematics

Prof. Dr. Andreas S. Schulz
Mathematics of Operations Research
(affiliated member of M9)

Prof. Dr. Stefan Weltge
Discrete Mathematics

News

April 2018
Case Studies 2018: Save the date: Case Studies poster presentation on May 25th, 2018, final workshop on July 7th, 2018.