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 |

## 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 |

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

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

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