HOME    »    PROGRAMS/ACTIVITIES    »    Annual Thematic Program
Winter 2003
IMA Workshop 5
Semidefinite Programming and Robust Optimization
March 12-19, 2003

  Schedule   Participants   Tutorial, March 11, 2003   Abstracts   Material from Talks 

2002-2003 Program: Optimization

Organizers:

Laurent El Ghaoui
EECS Department
University of California at Berkeley
elghaoui@eecs.berkeley.edu

Michel X. Goemans
Massachusetts Institute of Technology
goemans@math.mit.edu
http://www-math.mit.edu/~goemans

Donald Goldfarb
 IEOR Department
Columbia University
gold@ieor.columbia.edu

Michael L. Overton
Courant Institute of Mathematical Sciences
New York University
overton@cs.nyu.edu

Michael J. Todd
 School of Operations Research
Cornell University
miketodd@cs.cornell.edu  or  miketodd@orie.cornell.edu

Semidefinite programming (SDP) problems are linear optimization problems over the cone of positive semidefinite symmetric matrices. SDP includes as special cases linear programming, quadratic programming, quadratically constrained quadratic programming and second-order cone programming, and is itself a special case of convex optimization. SDPs arise in many applications, including robust control (where the well known abbreviation LMI: (linear matrix inequalities) describes the constraints of an SDP) and relaxations of hard combinatorial optimization problems (as used in the celebrated .878 approximation method for the max-cut problem). The last decade has seen dramatic advances in the theory and practice of semidefinite programming, stimulated in part by the realization that interior point methods can be applied very effectively to this class of convex optimization problems. Challenges for SDP in the coming years include the solution of large scale problems arising in a variety of applications and the extension of SDP methodology to broader problem classes. These extensions include symmetric cones and their relation to Jordan algebras, as well as bilinear matrix inequalities.

Robust optimization problems arise when a problem's data are known only within certain bounds. The goal is to find a solution which is feasible and acceptably close to optimal for all such data. Robustness is a well studied concept in control, but is also important in many other applications such as engineering design and finance. SDP and second-order cone programming play an important role in modeling a variety of robust optimization problems.

The workshop will bring together those interested in theory, algorithm development, and applications. There will be invited and contributed talks, and panels to discuss progress in the field.

WORKSHOP SCHEDULE

Saturday Monday Tuesday Wednesday
WEDNESDAY, MARCH 12
 All talks are in Lecture Hall EE/CS 3-180 unless otherwise noted.
8:30 am Coffee and Registration

Reception Room EE/CS 3-176
9:15 am Douglas N. Arnold, Scot Adams, and Organizers Welcome and Introduction
9:30 am James Renegar
Cornell University

Hyperbolic Polynomials, Riemannian Geometry and Optimization

Slides:   pdf    ps
10:20 am
Discussion
10:30 am Coffee Break Reception Room EE/CS 3-176
11:00 am Osman Güler
University of Maryland, Baltimore County

Interior Point Methods on Homogeneous Cones

Slides:   pdf

11:50 am
Discussion
12:00 pm
Lunch Break
1:30 pm Arkadi Nemirovski
Technion-Israel Institute of Technology

Matrix Cube Theorems and Tight Tractable Approximations of Semi-Infinite LMIs

Slides:   pdf    ps
2:20 pm
Discussion
2:30 pm Coffee Break Reception Room EE/CS 3-176
3:00 pm SECOND CHANCES, i.e., speakers of the day respond to further questions, suggestions, re-frame their main points, look toward future directions.
3:30 pm

IMA Tea and more (with POSTER SESSION)
400 Lind Hall

Anders Hansson
Linköping University
Joint work with Lieven Vandenberghe and Venkataramanan Balakrishnan.		 Efficient Solution of SDPs Related to the KYP Lemma
Didier Henrion
LAAS-CNRS
Joint work with Jean-Bernard Lasserre.

GloptiPoly - Global Optimization over Polynomials with Matlab and SeDuMi

Slides:   pdf
Michal Kocvara
University of Erlangen

Semidefinite Problems in Structural Optimization and their Solution by PENNON

Slides:   pdf
Vera Kovacevic-Vujcic
University of Belgrade
Joint work with P.S. Stanimirovic and N.V. Stojkovic. 		Stabilization of Mehrotra's Primal-Dual Algorithm and its Implementation
Vera Kovacevic-Vujcic
University of Belgrade
Joint work with M.M. Cangalovic and J.J. Kratica.		 A Predictor-Corrector Algorithm for a Semidefinite Relaxation of the Traveling Salesman Problem
Gert Lanckriet
University of California, Berkeley

Robust Novelty Detection with Single-Class MPM

Slides:   html    pdf    ppt
Gert Lanckriet
University of California, Berkeley

Learning the Kernel Matrix with Semi-Definite Programming

Slides:   html    pdf    ppt
Thanasak Mouktonglang
University of Notre Dame
Joint work with Leonid Faybusovich .		 Multi-Target Linear-Quadratic Control Problem and Second-order Cone Programming
Madhu V. Nayakkankuppam
University of Maryland, Baltimore County
Joint work with Yevgen Tymofyeyev

A Parallel Implementation of the Spectral Bundle Method for Semidefinite Programming

Slides:   pdf

Arnab Nilim
University of California, Berkeley
Joint work with Laurent El Ghaoui .		 Robust Solutions to Markov Decision Problems with Uncertain Transition Matrices: its Applications in Aircraft Path Planning
Tamás Terlaky
McMaster University, Canada
Joint work with Xiaohang Zhu and J. Peng

Computational Experiences with Self-Regular Proximity Based IPMs

Slides:   pdf

Takashi Tsuchiya
The Institute of Statistical Mathematics 		Robust Optimization of Magnetic Shielding
Yin Zhang
Rice University
Joint work with Kartik Krishnan. 		A Nonpolyhedral Primal Active-Set Approach to Semidefinite Programming
THURSDAY, MARCH 13
 All talks are in Lecture Hall EE/CS 3-180 unless otherwise noted.
9:00 am Coffee Reception Room EE/CS 3-176
9:30 am Aharon Ben-Tal
Technion-Israel Institute of Technology 		The Adjustable Robust Counterpart (ARC) Approach to Uncertain Linear Programs
10:20 am
Discussion
10:30 am Coffee Break Reception Room EE/CS 3-176
11:00 am Garud Iyengar
Columbia University

Robust Quadratically Constrained Quadratic Programs

Slides:   pdf

11:50 am
Discussion
12:00 pm
Lunch Break
1:30 pm Lieven Vandenberghe
Electrical Engineering, UCLA

Efficient Implementation of Interior-Point Methods for SDPs Arising in Control and Signal Processing

Slides:   pdf
2:20 pm
Discussion
2:30 pm Coffee Break Reception Room EE/CS 3-176
3:00 pm SECOND CHANCES, i.e., speakers of the day respond to further questions, suggestions, re-frame their main points, look toward future directions.
FRIDAY, MARCH 14
 All talks are in Lecture Hall EE/CS 3-180 unless otherwise noted.
9:00 am Coffee Reception Room EE/CS 3-176
9:30 am Renato D.C. Monteiro
Georgia Tech

A New Iteration-Complexity Bound for the MTY Predictor-Corrector Algorithm
abstract.pdf    abstract.ps

Slides:   pdf    ps
10:20 am
Discussion
10:30 am Coffee Break Reception Room EE/CS 3-176
11:00 am Katya Scheinberg
IBM T.J. Watson Research Center

A New Property of the Cholesky Factorization of the Matrices Arising in Interior Point Methods

Slides:   pdf
11:50 am
Discussion
12:00 pm
Lunch Break
1:30 pm Jos F. Sturm
Tilburg University, The Netherlands

An Interior Point Method with Column Aggregation and Selection

Slides:   pdf

2:20 pm
Discussion
2:30 pm Coffee Break Reception Room EE/CS 3-176
2:40 pm PANEL: Applications of Conic Programming to Robust Optimization and Other Domains
 Moderator: Michel X. Goemans (Massachusetts Institute of Technology)
Panelists:
Takashi Tsuchiya (The Institute of Statistical Mathematics)
Venkataramanan Balakrishnan (Purdue University)
Leonid Faybusovich (University of Notre Dame)
Reha H. Tutuncu (Carnegie Mellon University)
Etienne de Klerk (Delft University of Technology)
David Williamson (IBM Almaden Research Center)
3:30 pm Coffee Break Reception Room EE/CS 3-176
3:40 pm SECOND CHANCES, i.e., speakers of the day respond to further questions, suggestions, re-frame their main points, look toward future directions.
SATURDAY, MARCH 15
 All talks are in Lecture Hall EE/CS 3-180 unless otherwise noted.
9:00 am Coffee Reception Room EE/CS 3-176
9:30 am Masakazu Kojima
 Tokyo Institute of Technology

A General Framework for Convex Relaxation of Polynomial Optimization Problems over Cones

Slides:   pdf
10:20 am
Discussion
10:30 am Coffee Break Reception Room EE/CS 3-176
11:00 am Adrian Lewis
Simon Fraser University, Canada

Robust Regularization and Pseudospectra

Slides:   pdf   ps
11:50 am
Discussion
12:00 pm
Lunch Break
1:30 pm Levent Tuncel
 University of Waterloo

Theoretical Efficiency of Lift-and-Project Methods for Combinatorial Optimization

 Slides:   html
2:20 pm
Discussion
2:30 pm Coffee Break Reception Room EE/CS 3-176
3:00 pm
SECOND CHANCES, i.e., speakers of the day respond to further questions, suggestions, re-frame their main points, look toward future directions.
MONDAY, MARCH 17
 All talks are in Lecture Hall EE/CS 3-180 unless otherwise noted.
9:00 am Coffee Reception Room EE/CS 3-176
9:30 am Pablo A. Parrilo
 Swiss Federal Institute of Technology (ETH Zurich) 		Decomposing the Algebra Associated to an SDP
10:20 am
Discussion
10:30 am Coffee Break Reception Room EE/CS 3-176
11:00 am Jean B. Lasserre
 LAAS-CNRS, Toulouse, France

Some Applications of Semidefinite Programming in Probability and Algebra

Slides:   pdf
11:50 am
Discussion
12:00 pm
Lunch Break
1:30 pm Martin Wainwright
Electrical Engineering and CS, UC Berkeley

Semidefinite Relaxations for Approximate Inference and Counting Problems

Slides:   pdf    ps
2:20 pm
Discussion
2:30 pm Coffee Break Reception Room EE/CS 3-176
2:40 pm Laurent El Ghaoui
UC Berkeley

Case Studies in Robust Optimization

Slides:   pdf

3:30 pm
Discussion
3:40 pm Coffee Break Reception Room EE/CS 3-176
3:50 pm
SECOND CHANCES, i.e., speakers of the day respond to further questions, suggestions, re-frame their main points, look toward future directions.
TUESDAY, MARCH 18
 All talks are in Lecture Hall EE/CS 3-180 unless otherwise noted.
9:00 am Coffee Reception Room EE/CS 3-176
9:30 am Dimitris Bertsimas
Sloan Management (MIT)		 Robust Discrete and Dynamic Optimization
10:20 am
Discussion
10:30 am Coffee Break Reception Room EE/CS 3-176
11:00 am Zhi-Quan (Tom) Luo
McMaster University

Optimal Transceiver Design for Multi-user Communication

Slides:   pdf

11:50 am
Discussion
12:00 pm
Lunch Break
1:30 pm Javier Pena
Carnegie Mellon University

On the Block-structured Distance to Infeasibility

Slides:   pdf    ps
2:20 pm
Discussion
2:30 pm Coffee Break Reception Room EE/CS 3-176
2:40 pm PANEL: Algorithmic and Implementational Issues in Conic Programming
Moderator: Michael Overton (New York University)
Panelists:
Erling D. Andersen (MOSEK)
Samuel Burer (The University of Iowa)
Tamas Terlaky (McMaster University)
Kim Chuan Toh (National University of Singapore)
Henry Wolkowicz (University of Waterloo)
3:30 pm Coffee Break Reception Room EE/CS 3-176
3:40 pm SECOND CHANCES, i.e., speakers of the day respond to further questions, suggestions, re-frame their main points, look toward future directions.
6:00 pm Workshop Dinner Bangkok Thai Restaurant in Dinkytown
425 13th Avenue Southeast
Minneapolis
Phone 612-331-6830
WEDNESDAY, MARCH 19
 All talks are in Lecture Hall EE/CS 3-180 unless otherwise noted.
NOTE THE ABBREVIATED SCHEDULE FOR TODAY; FIRST TALK AT 9:10 AM
9:00 am Coffee Reception Room EE/CS 3-176
9:10 am Yurii Nesterov
 Universite Catholique de Louvain

Smooth Minimization of Non-smooth Functions
pdf    ps

Slides:   pdf    ps
10:00 am
Discussion
10:10 am Coffee Break Reception Room EE/CS 3-176
10:20 am Franz Rendl
Institute of Mathematics, University of Klagenfurt, Austria 		Semidefinite Programming and the Bundle Method
11:10 am
Discussion
11:20 am Coffee Break Reception Room EE/CS 3-176
11:30 am Yinyu Ye
Stanford University

Semidefinite Programming for Approximation

Slides:   pdf

12:20 pm
Discussion
12:30 pm Coffee Break Reception Room EE/CS 3-176
12:40 pm
Concluding Remarks by Organizers
Saturday Monday Tuesday Wednesday

LIST OF CONFIRMED PARTICIPANTS

As of 3/24/2003
Name Department Affiliation
Scot Adams IMA University of Minnesota
Montaz Ali Computational And Applied Mathematics Witwatersrand University
Farid Alizadeh RUTCOR Rutgers University
Erling D. Andersen EKA Consulting Aps MOSEK
Douglas N. Arnold IMA University of Minnesota
Donald Aronson IMA University of Minnesota
Venkataramanan Balakrishnan Electrical and Computer Engineering Purdue University
Aharon Ben-Tal Industrial Engineering and Management Technion
Steven J. Benson Mathematics and Computer Science Argonne National Laboratory
Dimitris Bertsimas Sloan Management MIT
Brian Borchers Mathematics New Mexico Tech
Olga Brezhneva Institute for Mathematics and its Applications University of Minnesota
Samuel Burer Management Sciences The University of Iowa
James Burke Mathematics University of Washington
Jamylle Carter Mathematics University of Minnesota
Check Beng Chua Operations Research & Industrial Eng. Cornell University
Collette Coullard Industrial Eng. & Mgmt. Sciences Northwestern University
Etienne de Klerk Information, Systems and Algorithms Delft University of Technology
John Dennis, Jr. LTV Rice University
Moritz Diehl Interdisciplinary Center for Scientific Computing University of Heidelberg
Gregory S. Duane University of Minnesota Institute for Mathematics and its Applications
Laurent El Ghaoui EECS University of California at Berkeley
Marina A. Epelman Industrial and Operations Engineering University of Michigan
Grant Erdmann Mathematics University of Minnesota
Lisa Evans IMA University of Minnesota
Leonid Faybusovich Mathematics University of Notre Dame
Robert Fourer Industrial Engineering & Management Scien Northwestern University
Robert M. Freund Sloan Management MIT
Mituhiro Fukuda Mathematics New York University
Ashwin Ganesan Electrical Engineering & Computer Science University of California at Berkeley
Sonja Glavaski Honeywell Laboratories Honeywell
Michel Goemans Mathematics MIT
Jean-Louis Goffin Faculty of Management McGill University
Donald Goldfarb Industrial Engineering and Oper Res Columbia University
Balaji Gopalakrishnan Institute for Mathematics and its Application University of Minnesota
Osman Guler Mathematics & Statistics University of Maryland, Baltimore County
Anders Hansson Electrical Engineering Linkoping University
Raphael Hauser Computing Laboratory University of Oxford
Didier Henrion MAC LAAS-CNRS
Garud Iyengar IEOR Columbia University
Florian Jarre Mathematisches Institut Universitat of Dusseldorf
Lili Ju   Minneapolis VA Medical Center
Herve Kerivin IMA University of Minnesota
Michal Kocvara Institute of Applied Mathematics University of Erlangen-Nuremberg
Masakazu Kojima Mathematical & Computing Sciences Tokyo Institute of Technology
Vera Kovacevic-vujcic Fac. Organizational Sciences University of Belgrade
Gert Lanckriet Electrical Engineering & Computer Science University of California at Berekley
Jean B. Lasserrre   LAAS-CNRS
Bruce Legan Mathematics University of St. Thomas
Friedemann Leibfritz Mathematics University of Trier
Adrian Lewis Mathematics Simon Fraser University
Zhi-Quan Luo Electrical and Computer Engineering McMaster University
Renato Monteiro Industrial & Systems Engineering Georgia Institute of Technology
Francesco Montrone Corporate Technology Siemens
Thanasak Mouktonglang Mathematics University of Notre Dame
Madhu Nayakkankuppam Mathematics & Statistics University of Maryland, Baltimore County
Arkadii S. Nemirovskii Industrial Engineering and Management Technion University
Yurii Nesterov CORE Universite Catholique de Louvain
Peh Ng IMA University of Minnesota
Arnab Nilim Electrical Engineering & Computer Science University of California at Berkeley
Jerome W. O'Neal Industrial and Systems Engineering Georgia Institute of Technology
Fernando Ordonez Industrial & Systems Engineering University of Southern California
Michael L. Overton   Courant Institute of Mathematical Sciences
Pablo A. Parrilo Automatic Control Laboratory Swiss Federal Institute of Technology
Dimitri Peaucelle Methods and Algorithms in Control LAAS-CNRS
Javier Pena Graduate Industrial Administration Carnegie Mellon University
Florian A. Potra Mathematics & Statistics University of Maryland, Baltimore County
Bharath Rangarajan ORIE Cornell University
Franz Rendl Institut fur Mathematik University of Klagenfurt
James Renegar Operations Research Cornell University
Kees Roos Statistics, Probability and Oper Research Delft University of Technology-CWI
Fadil Santosa IMA University of Minnesota
Katya Scheinberg   IBM T.J. Watson Research Center
Stefan Schmieta   Axioma, Inc.
M. Nuri Sendil Industrial Eng. & Mgmt. Sciences Northwestern University
Sashirekha Shanmugavelu Computer Engineering University of Minnesota
Tamon Stephen IMA University of Minnesota
Jos F. Sturm Econometrics Tilburg University
Dharmashankar Subramanian ACS Honeywell Labs
Tamas Terlaky Computing and Software McMaster University
Michael Todd Operations Research and Industrial Engin Cornell University
Kim-Chuan Toh Mathematics National University of Singapore
Paul Tseng Mathematics University of Washington
Takashi Tsuchiya Statistical Computing The Institute of Statistical Mathematics
Levent Tuncel Combinatorics & Optimization University of Waterloo
Reha H. Tutuncu Mathematical Sciences Carnegie Mellon University
Lieven Vandenberghe Electrical Engineering University of California, Los Angeles
Jorge R. Vera Dept. de Ingenieria Industrial y Sistemas Pontificia Universidad Catolica de Chile
Luis Nunes Vicente Departamento de Matemática Universidade de Coimbra
Martin Wainwright Electrical Engineering and Computer Science University of California at Berkeley
Jing Wang Institute for Mathematics and its Application University of Minnesota
David Williamson   IBM Almaden Research Center
Henry Wolkowicz Combinatorics & Optimization University of Waterloo
Yinyu Ye Management Science & Engineering Stanford University
Emre Alper Yildirim Applied Mathematics & Statistics SUNY at Stonybrook
Shuzhong Zhang Systems Eng. & Eng. Management Chinese University of Hong Kon
Yin Zhang Computational and Applied Mathematics Rice University
Yuriy Zinchenko ORIE Cornell University
Luis F. Zuluaga GSIA Carnegie Mellon University
Go