### Doctoral school on: Optimization over Polynomials and Semidefinite Programming

#### organized by M. Laurent (CWI, Amsterdam) and F. Rendl (University of Klagenfurt)

 The doctoral school is sponsored by the research network ADONET (Algorithmic Discrete Optimization Network) funded by the European Community with 12 participating universities in 10 european countries.

### Theme of the doctoral school

The central topic of the doctoral school is the study of "sum of squares" representations of polynomials as a tool to get approximate solutions to NP-hard optimization problems. As finding such a representation amounts to solving a semidefinite program, one can approximate the global minimum of a polynomial over a set defined by polynomial inequalities and equations efficiently using semidefinite programming. Polynomial optimization includes 0/1 programming problems which can be modelled by the quadratic equations x²=x for all variables.

The purpose of the doctoral school is to introduce interested graduate students into this field and to give them a hands-on experience with software developed for minimizing polynomials. Some prior knowledge in linear algebra, numerics, algebra and optimization will be useful.

More specifically, the doctoral school offers an introduction to the following topics:

• Theoretical background from real algebraic geometry about representations of positive polynomials as sums of squares (Hilbert's 17th problem, representation theorems of Pólya, Putinar, Schmüdgen, etc.)
• The dual theory of moments (theorems about moment matrices of Curto and Fialkow, Carleman's condition, etc., used for the approximation of polynomial programs)
• Minimizing polynomials over basic closed semi-algebraic sets via the "sum of squares" approach and the "moment matrix" dual approach (convergence results, stopping criteria, extracting optimum solutions, application to combinatorial optimization)
• Exploiting symmetries to reduce the size of semidefinite programs (block-diagonalization of matrix ∗-algebras, link with representation theory, application to coding theory - improving the Delsarte bound using Terwiliger algebras, etc.)
• Algorithmic issues related to finding sum of squares representations (algorithmic alternatives to interior-point methods for large semidefinite programs, augmented Lagrangian, bundle methods, etc.)
• Barvinok's method and integer polynomial optimization (using Barvinok's rational functions for representing lattice points in polyhedra and optimizing polynomials over them) and using polynomials to model combinatorial optimization problems

### Speakers

 J. Lasserre, LAAS-CNRS, Toulouse reading suggestion and slides M. Laurent, CWI, Amsterdam summary, reading suggestion and slides J. de Loera, University of California, Davis summary, reading suggestion and slides P. Parrilo, MIT, Cambridge reading suggestions F. Rendl, University of Klagenfurt summary and slides B. Reznick, University of Illinois at Urbana-Champaign summary and reading suggestion A. Schrijver, CWI, Amsterdam summary

### Tentative schedule

Here is a short file containing further details: read and print this

• Sunday
• 18.00 – 20.00: informal get together at the University in room SR i-201, mathematics department
• Monday
• 8.30 – 9.00: opening session
• 9.00 – 12.00: B. Reznick
• 16.00 – 19.00: P. Parrilo
• Tuesday
• 9.00 – 12.00: A. Schrijver
• 16.00 – 19.00: A. Schrijver, P. Parrilo (work on computer)
• Wednesday
• 9.00 – 12.00: J. Lasserre
• 12.00 – 13.00: J. Lasserre (work on computer)
• 14.00 – 21.00: hiking tour and workshop dinner
• Thursday
• 9.00 – 12.00: M. Laurent
• 16.00 – 19.00: F. Rendl
• Friday
• 9.00 – 12.00: J. de Loera
• 12.00 – 12.30: closing session
• 13.00 – 14.00: farewell lunch

### Social program

• Sunday, Sept. 11, 18.00 – 20.00: Informal get together at the Univeristy in room SR i-201, mathematics department
• Wednesday, Sept. 14, afternoon: Hiking in the Alps and Workshop Dinner at Klagenfurter Hütte
• Friday, Sept. 16, noon: Farewell Lunch at the University restaurant IQ

### Participants

• Michael Armbruster, Chemnitz University of Technology, Germany
• Ivo Bleylevens, University of Maastricht, Netherlands
• Hartwig Bosse, CWI, Amsterdam, Netherlands
• Stefan Bundfuss, Technische Universität Darmstadt, Germany
• Martin Burke, Imperial College London, UK
• Jaroslaw Byrka, CWI, Amsterdam, Netherlands
• Andrea Cassioli, Università degli Studi di Firenze, Italy
• Jakob Cimpric, University of Ljubljana, Slovenia
• Zsolt Csizmadia, Eötvös Loránd University, Budapest, Hungary
• Igor Dukanovic, University of Maribor, Slovenia
• Christian Ebenbauer, University of Stuttgart, Germany
• Gamal Elabwabi, University of Tilburg, Netherlands
• Ioannis A. Fotiou, ETH Zurich, Switzerland
• Florian Frommlet, University of Vienna, Austria
• Monia Giandomenico, University of Rome "La Sapienza", Italy
• Gaelle Giberti, Laboratoire Leibniz, Grenoble, France
• Magdalena Grüber, Humboldt-University Berlin, Germany
• Nebojsa Gvozdenovic, CWI, Amsterdam, Netherlands
• Johannes Hatzl, Graz University of Technology, Austria
• Tamas Kis, Computer and Automation Research Institute, Hungarian Academy of Sciences, Hungary
• Igor Klep, Universität Konstanz, Germany
• Etienne de Klerk, Tilburg University, Netherlands
• Dennis Michaels, Otto-von-Guericke Universitaet Magdeburg, Germany
• Marianna Nagy, Eötvös Loránd University, Budapest, Hungary
• Helfried Peyrl, ETH Zurich, Switzerland
• Gema Plaza, University of Alicante, Spain
• Janez Povh, School of Business and Management Novo Mesto, Slovenia
• Philipp Rostalski, ETH Zurich, Switzerland
• Doris Rotheigner, University of Regensburg, Germany
• Cristiano Saturni, University of Padova, Italy
• Carlo Savorgnan, Università Degli Studi Di Udine, Italy
• Markus Schweighofer, Universität Konstanz, Germany
• Marco di Summa, University of Padova, Italy
• Hakan Umit, Université Catholique de Louvain, Belgium
• Frank Vallentin, Hebrew University Jerusalem, Israel
• Dejan Veluscek, University of Ljubljana, Slovenia
• Juan Vera, Carnegie Mellon University, USA
• Hayato Waki, Tokyo Institute of Technology, Japan
• Angelika Wiegele, University of Klagenfurt, Austria
• Rico Zenklusen, ETH Zurich, Switzerland
• Stefan van Zwam, Technische Universiteit Eindhoven, Netherlands

### Accomodation and Fees

We can offer accommodation in the youth hostel in double rooms for the duration of the school (i.e. arrival on Sunday Sept. 11, 2005, departure on Saturday Sept. 17, 2005) at a rate of 22 Euro per person and night including breakfast for participants who register no later than June 26, 2005. (The youth hostel is located in walking distance to the university, the rooms are equipped with private shower and toilet.)
If you are interested in this offer, please indicate so in your registration e-mail and specify arrival and departure times. Confirmations will be sent out on June 30, 2005. All other participants will be asked to make their own accommodation arrangements.

Information about the youth hostel: www.oejhv.or.at (Address: Neckheimgasse 6, phone number +43 463 230020)
Online booking at the youth hostel: www.hihostels.com
More information on accomodation in Klagenfurt: Klagenfurt tourist information.

Travel, accommodation and living expenses must be paid by (the home institutions of) the participants. There will be no fee for participation and course material.

### Registration

To register, send an e-mail to adonet@uni-klu.ac.at containing the following information:

• Name
• Affiliation
• Current status (doctoral student / post-doc / other)
• e-mail address
• Research area of interest
• Supervisor (if applicable)
• Accomodation required (yes/no)     deadline is over - please make your own arrangements
• Male/Female (if accomodation required)

### Location

The doctoral courses will take place at the University of Klagenfurt in lecture room HS B (main building, "Südtrakt") and in computer room UR z-514b.

### Travelling to Klagenfurt...

To get an idea on the location of Klagenfurt, you may have a look at this small overview map.

#### ...by car from the highway (all directions) to the University:

Coming from the West (Salzburg, Villach), you first go until "Klagenfurt West" which is the next crossing after Krumpendorf. Be careful and take at Klagenfurt-West the leftmost lane directly to Klagenfurt Center. At Klagenfurt-Wörthersee (1,5 km after Klagenfurt-West) you leave the highway. Coming from the North (St. Veit) or the East (Graz, Vienna), you follow the many tunnels in the north of Klagenfurt westwards. Immediately after the Falkenbergtunnel you take the second exit (about 300 m after the end of the Tunnel, so be alert!) directed to "Klagenfurt West". About 1,5 km after that you leave the highway at Exit "Klagenfurt-Wörthersee".
After having left the highway at Klagenfurt-Wörthersee (=Klagenfurt-See in short) you immediately come to the so called "Minimundus-Crossing" (with traffic-lights). You keep straight direction towards south. After 400 m you will see the logo of the University of Klagenfurt. Turn left into the Universitätsstraße. You have arrived at your destination.

#### ...by car from Slovenia (via Loiblpass) to the University:

Coming down the Loiblpass you go right through Unterloibl, Kirschentheuer, passing the Hollenburg and Maria Rain until you come to the first traffic lights of Klagenfurt. There you go straight ahead. After about 800 m at the next traffic lights you turn left towards the direction Wörthersee/Universität/Autobahn Villach to the so-called "Südring". You go along the Südring, passing the Wörthersee stadium. About 1 km after the stadium the road makes a big turn right. Looking ahead then you will see on your right the "Lakeside Park" and just behind it is the University of Klagenfurt.

There is a sufficient number of parking lots around the university area.

#### ...by plane or train:

Klagenfurt Airport is reachable by direct flights from Vienna and Frankfurt (Austrian Airlines), from Berlin, Cologne/Bonn, Hamburg and Hannover (Hapag-Lloyd Express) and from London Stansted and Frankfurt-Hahn (Ryanair).

NEW DESTINATIONS FROM KLAGENFURT AIRPORT: Zurich and Paris. (with a stop in Salzburg)
Styrian Spirit flies from September 6 on from Klagenfurt to Zurich and Paris (via Salzburg).

For details on travelling to Klagenfurt by train search the time-table of the Austrian Federal Railways.

#### Reaching Klagenfurt University (and the youth hostel) by bus from the main station or airport

The University of Klagenfurt is easily reachable by public transportation. The bus route system in Klagenfurt is star-shaped. The stop Heiligengeistplatz is the centre of the star. Heiligengeistplatz can be reached by bus lines from the train station (Hauptbahnhof) and from the airport (Flughafen). (For more information see the route map. The stops Hauptbahnhof (main station), Flughafen (airport) and Universität are indicated by large yellow circles.)
To reach the university from Heiligengeistplatz, lines 10, 11, 12, 20 and 21 can be used. Line 12 is the most convenient because it directly goes to the university. Get off the bus at the stop Universität or if you want to go to the hostel at the stop Jugendgästehaus, which is just one stop before Universität. Line 12 does not run, however, on Sunday.
Lines 10, 11, 20 and 21 stop at Minimundus which is close to the university. The stop Minimundus is located in Villacher Straße. If you go to the youth hostel get off at the stop Neckheimgasse, which is just one stop before Minimundus. For details see the map of the bus routes (the stop Minimundus is indicated by a red circle) and the campus map.
The travel time from Heiligengeistplatz to the university is about 10 minutes. It is recommendable to have a look at the bus schedule in order to avoid long waiting times.

The cost of a bus-ticket (valid for one hour) is 1.60 Euro and can be bought on the bus.

#### Reaching Klagenfurt University by taxi from the main station or airport

Taxis are available in front of the Arrival/Departure Hall of Klagenfurt Airport as well as in front of the train station. Typical fares and driving times are:

• Airport – University: 15-17 Euro, 20 minutes
• Main station – University: 8-10 Euro, 10 minutes

### Other useful information

Bring adequate shoes for hiking and a swimsuit. The campus is located quite close to lake "Wörthersee". You may have a look at the weather in Klagenfurt.

Information about the youth hostel: www.oejhv.or.at (Address: Neckheimgasse 6, phone number +43 463 230020)

Internet-access: Participants will have access to the University's Computer rooms. Also, wireless LAN and plug-in connections for notebooks are available at the campus area.

### Contact

For information please contact Franz Rendl (phone: +43 463 2700 3114).

### Photo download

 Angelika Wiegele Last modified: Sun Oct 2 12:20:50 CEST 2005 Free counter