Spring School 'Continuum Methods for Discrete Problems in Combinatorics, Optimization and Mathematical Physics'

at AIMS Senegal, 13.4.2015 - 17.4.2015

Student Seminar

The aim of the students seminar is ... (TO BE INCLUDED)

Students NOT from AIMS-Senegal willing to participate in this event can apply for grants, covering travel and/or living expenses, by sending a  motivation letter and a cv to mtbaesse@aims-senegal.org.

The deadline for application is: March 02, 2015.

The following talks are available:

Talk 1: Applications of Second Order Cone Programming

The Second Order Cone or Icecream Cone is the closed convex cone in n-dimensional real space consisting of all points so that the first coordinate is an upper bound on the euclidean norm of the remaining coordinates. Second order cone programming (SOCP) deals with the problem of optimizing a linear function over the intersection of an affine (shifted linear) subspace with one or several second order cones. SOCP allows to model and solve a rich spectrum of applications in convex quadratic optimization. Several important ones are collected in sections 2 and 3 of

http://stanford.edu/~boyd/papers/pdf/socp.pdf

In their seminar presentation, 3-4 students should explain the workings of these applications in sections 2 and 3 in detail to their fellow students. While the paper also contains a lot of material on the theory and solution algorithms, it is NOT the objective of the seminar to go into this. Theory and algorithms will be adressed in the lecture series.

Talk 2: Applications of Semidefinite Programming

The Semidefinite Cone of order n is the closed convex cone of symmetric positive semidefinite n-by-n matrices. Semidefinite programming (SDP) deals with the problem of optimizing a linear function over the intersection of an affine (shifted linear) subspace with the semidefinite cone. SDP allows to model and solve an even richer spectrum of applications in convex optimization. A few relevant initial ones are listed in section 2 of

https://web.stanford.edu/~boyd/papers/pdf/semidef_prog.pdf

In their seminar presentation, 3-4 students should explain the workings of these applications in section 2 in detail to their fellow students. While the paper also contains a lot of material on the theory and solution algorithms, it is NOT the objective of the seminar to go into this. Theory and algorithms will be adressed in the lecture series.

If students are interested in further applications of SDP, they are invited to consult the section "Survey Papers and Books" on the web page

https://www.tu-chemnitz.de/~helmberg/semidef.html

Talk 3: The principle of inclusion and exclusion with generating functions

Consider a game of poker in which a player is dealt a hand of five cards from a deck of 52 cards. How many possible hands are there with at least two aces? How many with exactly two aces? The first question is easy to answer. The second is answered with the principle of inclusion and exclusion which relates both questions. This talk shows the relation of the two questions: at generating function level it simply boils down to a substitution of variables.

The material (method and examples) are in Section 4.2 of Wilf’s Generatingfunctionology.

For both talks accompanying the Generating Functions course I recommend reading Chapters 1 and 2 of Wilf’s book, in particular Sections 2.1, 2.2. Also have a look at Section 2.5 which contains a catalogue of useful series.

Talk 4: Counting polyominoes

Polyominoes are roughly a finite collections of unit squares (cells) which are arranged in an edge to edge fashion. These objects have been studied by chemists, physicists and mathematicians alike and the question for the (asymptotic) number of polyominoes with a given number of cells is very hard and as yet unanswered. This talk gives a solution for a subclass called horizontally convex polyominoes.

The material for this talk is in Section 4.9 of Generatingfunctionology.

Talk 5: Why Percolation?

Talk 6: Percolation, the one-dimensional case.

Registration