Workshop
Semidefinite Programming: Applications and Algorithms

ZIB-Berlin, November 15-17, 1998

Contents

(dd.mm.year) gives the date of the last change in the section.

Aim of the Workshop

Semidefinite Programming has been around for some time. Initially it was mainly a theoretical tool for proving, e.g., bounds or showing desirable properties of certain mathematical models. Roughly ten years ago - with the extension of the theory of interior point methods from Linear Programming to Semidefinite Programming - many of these problems came into the realm of computational tractability.

This spurred interest into the field and resulted in several new applications of Semidefinite Programming and in an increasing demand for general purpose codes that solve these problems for variables and constraints steadily growing in number and size.

At the same time various algorithmic approaches have been and are being developed that try to provide such tools. However, none of them qualifies as THE general purpose tool one would hope for. Rather, each algorithm has its own merits and limits.

It seems to be time to

and to To initiate this process we have decided to dedicate the workshop to this topic.

The workshop consisted of 22 invited presentations, 5 of them one-hour lectures of survey character and 17 talks (30 minutes each) on special issues. We thank all speakers for having accepted our invitation, and the Deutsche Forschungsgemeinschaft whose funds have made this workshop possible.

Martin Grötschel, Christoph Helmberg, and Lieven Vandenberghe

Program

Sunday, November 15
  Chair: Michael J. Todd
14:30 - 15:30 Yinyu Ye, University of Iowa.
"Mixed Linear and Semidefinite Programming for Combinatorial and Quadratic Optimization"
(abstract)

Reference:

  • S. Benson, Y. Ye, and X. Zhang.
    "Mixed Linear and Semidefinite Programming for Combinatorial and Quadratic Optimization",
    Working Paper, Department of Management Sciences, The University of Iowa, February 1998.
    ps-file (ftp)
15:30 - 16:00 Jos F. Sturm, Maastricht University, Netherlands.
"The `SeDuMi' interior point algorithm for optimization over symmetric cones"
(slides as dvi or ps.gz-file)

References:

coffee break
  Chair: László Lovász
16:30 - 17:00 Michel X. Goemans, CORE, Belgium and MIT.
"The Lovász-Schrijver procedure" (tentative title)
17:00 - 17:30 Yurii Nesterov, CORE, Belgium.
"Global optimization via conic relaxations"
17:30 - 18:00 Masakazu Kojima, Tokyo Institute of Technology, Japan.
"Cones of Matrices and Successive Convex Relaxation of Nonconvex Sets"

References:

  • Masakazu Kojima and Levent Tuncel.
    "Cones of Matrices and Successive Convex Relaxations of Nonconvex Sets",
    Research Report B-341, Dept. of Mathematical and Computing Sciences, Tokyo Institute of Technology, March 1998.
    ps-file
  • Masakazu Kojima and Levent Tuncel.
    "Discretization and Localization in Successive Convex Relaxation Methods for Nonconvex Quadratic Optimization Problems",
    Research Report B-341, Dept. of Mathematical and Computing Sciences, Tokyo Institute of Technology, July 1998.
    ps-file
 
Monday, November 16
  Chair: Yurii Nesterov
9:00 - 10:00 Jochem Zowe, Universität Erlangen, Germany.
"Material Optimization"
10:00 - 10:30 Aharon Ben-Tal, Technion, Israel.
"General Structural Design via Semidefinite Programming"
coffee break
  Chair: Yinyu Ye
11:00 - 11:30 Lieven Vandenberghe, UCLA, Electrical Engineering Department.
"Some applications of SDP in circuit design"
11:30 - 12:00 Michael J. Todd, Cornell University, New York.
"Detecting infeasibility in SDPs using path-following infeasible-interior-point methods" (Joint work with Yinyu Ye)
12:00 - 12:30 Tamás Terlaky, Delft University of Technology, Netherlands.
"Do we need second- and $p-$order conic programming?
(reformulations and duality issues)"
(slides (ps.gz-file))
lunch break
  Chair: Martin Grötschel
14:30 - 15:30 László Lovász, Yale University.
"Applications in Combinatorial Optimization"

References:

15:30 - 16:00 Monique Laurent, CWI, The Netherlands.
"A polynomial instance of the positive semidefinite matrix completion problem"
coffee break
  Chair: Michael L. Overton
16:30 - 17:00 Kurt M. Anstreicher, University of Iowa.
"The volumetric barrier for semidefinite programming"
(abstract)

References:

  • K.M. Anstreicher.
    "The Volumetric Barrier for Semidefinite Programming",
    Dept. of Managment Science, University of Iowa, January 1998.
    ps-file (http)
  • K. M. Anstreicher.
    "The Volumetric Barrier for Convex Quadratic Constraints",
    Dept. of Management Sciences, University of Iowa, Iowa City, October 1998.
    ps-file (http)
17:00 - 17:30 Christoph Helmberg, ZIB-Berlin, Germany.
"The spectral bundle method with sign constraints"
17:30 - 18:00 Franz Rendl, Universität Klagenfurt, Austria.
"Spectral Bundle with Second Order Information"
 
Tuesday, November 17
  Chair: Lieven Vandenberghe
9:00 - 10:00 Laurent El Ghaoui, ENSTA, France.
"Decision problems with uncertain data: a semidefinite programming approach"
(slides as ps.gz-file)

10:00 - 10:30 Venkataramanan Balakrishnan, Purdue University.
"Applications of Semidefinite Programming in Robust Control"
coffee break
  Chair: Kurt M. Anstreicher
11:00 - 11:30 Frédéric Bonnans, INRIA, France.
"Perturbation analysis of semidefinite programming problems"
(abstract)

References:

11:30 - 12:00 Donald Goldfarb, Columbia University NY.
"Solving Second Order Cone Programs in an Efficient and Numerically Stable Manner"
12:00 - 12:30 Florian Jarre, Universität Würzburg, Germany.
"A QQP-Minimization Method for Semidefinite and Smooth Nonconvex Programs"
(abstract)

References:

lunch break
  Chair: Franz Rendl
14:00 - 15:00 Michael L. Overton, New York University.
"Non-Lipschitz Eigenvalue Optimization"
15:00 - 15:30 Lorant Porkolab, Max-Planck-Institute for Computer Science, Germany.
"On the Complexity of Real and Integer Semidefinite Programming"

References:

  • L. Porkolab and L. Khachiyan.
    "On the Complexity of Semidefinite Programs",
    Journal of Global Optimization, 10 (1997), 351-365. [This paper also received a Featured Review in the Mathematical Reviews, May 1998, issue 98e, 98e:90168.]
    ps.gz-file (http, not identical to paper version)
  • L. Khachiyan and L. Porkolab.
    "Computing Integral Points in Convex Semi-algebraic Sets",
    Proceedings 38th Annual IEEE Symposium on Foundations of Computer Science, 162-171, 1997.
    ps.gz-file (http)
coffee and discussion

Time and Place

The workshop was held at from Sunday, Nov. 15, 1998 to Tuesday, Nov. 17, 1998,
in the Lecture Hall (Room 2005) on the ground floor of the circle wing.

Detailed information on how to arrive at ZIB is given on the page Hints for Visitors.

Accommodation

For speakers we have made reservations in The hotel (see the red circle in the map) is easy to reach by underground U9 (final stop "Rathaus Steglitz") and S-Bahn (inner-city railway; stop "Rathaus Steglitz"). The neighboring "Schloßstraße" is one of the best shopping streets in Berlin.

ZIB is within walking distance (20 min). Follow Grunewaldstraße to Königin-Luise-Platz, turn left into Altensteinstraße, walk another 400m to find a (small) sign on your right showing the way to ZIB (and other buildings on the campus of FU Berlin). The last part is well displayed on the local ZIB map.

If you prefer not to walk, there is Bus 183 which stops directly in front of the Hotel; step out at the fourth stop and find yourself on the local ZIB map at the right most stop of Bus 183.

To reach the hotel from Airport Berlin-Tegel take either Bus X9 or 109 to Railway Station Zoologischer Garten; change to underground U9 and go to the final stop "Rathaus Steglitz".

If you happen to arrive at Airport Berlin-Tempelhof take underground U6 direction "Alt-Tegel", step out at "Friedrich-Strasse" and switch to S-Bahn S1 direction "Wannsee". Get off at "Rathaus Steglitz".

From Airport Berlin-Schönefeld take S-Bahn S45 till stop "Schöneberg", change to S-Bahn S1 direction "Wannsee" and get off at "Rathaus Steglitz".

The S-Bahn and underground network of Berlin is displayed on this schematic map. In all cases you will have to buy an AB-ticket for 3.90 DM at e.g. an automatic ticket machine (they accept notes and do provide change). Please remember to cancel your ticket before you start your trip.

Guests

We regret that there will be no possibility for contributed talks. However we invite everyone who is interested in the topic of the workshop to join us in Berlin, and participate in the discussions at the meeting.

Unfortunately, we are unable to offer any financial support.

The following persons have informed us that they will participate in the workshop:

Social Program

Sunday, November 15
9:15 meeting point: Hotel Steglitz,
S-Bahn (inner city railway) to Potsdamer Platz, visit to the Info-Box and the "Arkaden".
11:15 guided tour of "Gemäldegalerie Kulturforum", Matthäikirchplatz 8 (map), starting at the information counter
 
Monday, November 16
20:00 Workshop-Dinner at Restaurant Mommsen-Eck, Mommsenstr. 45 (map)

Organizers

The workshop is organized by Martin Grötschel, Christoph Helmberg, and Lieven Vandenberghe.

Please direct all correspondence and inquiries to

helmberg@zib.de
Last Update: January 2, 1999