Semidefinite Programming and Robust Optimization

March 12 - 19, 2003

Content

Overview

Organizers:

Laurent El Ghaoui	University of California, Berkeley
Michel Goemans	Massachusetts Institute of Technology
Donald Goldfarb	Columbia University
Michael Overton	New York University
Michael Todd	Cornell University

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.

Schedule

Wednesday, March 12, 2003

8:30 am - 9:15 am	Coffee and Registration	Keller 3-176
9:15 am - 9:30 am	Welcome and Introduction Scot Adams (University of Minnesota, Twin Cities), Douglas Arnold (University of Minnesota, Twin Cities), Laurent El Ghaoui (University of California, Berkeley), Donald Goldfarb (Columbia University), Michael Overton (New York University), Michael Todd (Cornell University)	Keller 3-180
9:30 am - 10:20 am	Hyperbolic Polynomials, Riemannian Geometry and Optimization James Renegar (Cornell University)	Keller 3-180
10:20 am - 10:30 am	Discussion James Renegar (Cornell University)	Keller 3-180
10:30 am - 11:00 am	Coffee Break	Keller 3-176
11:00 am - 11:50 am	Interior Point Methods on Homogeneous Cones Osman Guler (University of Maryland Baltimore County)	Keller 3-180
11:50 am - 12:00 pm	Discussion Osman Guler (University of Maryland Baltimore County)	Keller 3-180
12:00 pm - 1:30 pm	Lunch
1:30 pm - 2:20 pm	Matrix Cube Theorems and Tight Tractable Approximations of Semi-Infinite LMIs Arkadi Nemirovski (Technion-Israel Institute of Technology)	Keller 3-180
2:20 pm - 2:30 pm	Discussion Arkadi Nemirovski (Technion-Israel Institute of Technology)	Keller 3-180
2:30 pm - 3:00 pm	Coffee Break	Keller 3-176
3:00 pm - 3:30 pm	Second Chances	Keller 3-180
3:30 pm - 5:30 pm	IMA Tea and more (with POSTER SESSION)	Lind 400

Thursday, March 13, 2003

9:00 am - 9:30 am	Coffee	Keller 3-176
9:30 am - 10:20 am	The Adjustable Robust Counterpart (ARC) Approach to Uncertain Linear Programs Aharon Ben-Tal (Technion-Israel Institute of Technology)	Keller 3-180
10:20 am - 10:30 am	Discussion Aharon Ben-Tal (Technion-Israel Institute of Technology)	Keller 3-180
10:30 am - 11:00 am	Coffee Break	Keller 3-176
11:00 am - 11:50 am	Robust Quadratically Constrained Quadratic Programs Garud Iyengar (Columbia University)	Keller 3-180
11:50 am - 12:00 pm	Discussion Garud Iyengar (Columbia University)	Keller 3-180
12:00 pm - 1:30 pm	Lunch
1:30 pm - 2:20 pm	Efficient Implementation of Interior-Point Methods for SDPs Arising in Control and Signal Processing Lieven Vandenberghe (University of California, Los Angeles)	Keller 3-180
2:20 pm - 2:30 pm	Discussion Lieven Vandenberghe (University of California, Los Angeles)	Keller 3-180
2:30 pm - 3:00 pm	Coffee Break	Keller 3-176
3:00 pm - 4:00 pm	Second Chances	Keller 3-180

Friday, March 14, 2003

9:00 am - 9:30 am	Coffee	Keller 3-176
9:30 am - 10:20 am	A New Iteration-Complexity Bound for the MTY Predictor-Corrector Algorithm Renato Monteiro (Georgia Institute of Technology)	Keller 3-180
10:20 am - 10:30 am	Discussion Renato Monteiro (Georgia Institute of Technology)	Keller 3-180
10:30 am - 11:00 am	Coffee Break	Keller 3-176
11:00 am - 11:50 am	A New Property of the Cholesky Factorization of the Matrices Arising in Interior Point Methods Katya Scheinberg (IBM)	Keller 3-180
11:50 am - 12:00 pm	Discussion Katya Scheinberg (IBM)	Keller 3-180
12:00 pm - 1:30 pm	Lunch
1:30 pm - 2:20 pm	An Interior Point Method with Column Aggregation and Selection Jos Sturm (Katholieke Universiteit Brabant (Tilburg University))	Keller 3-180
2:20 pm - 2:30 pm	Discussion Jos Sturm (Katholieke Universiteit Brabant (Tilburg University))	Keller 3-180
2:30 pm - 2:40 pm	Coffee Break	Keller 3-176
2:40 pm - 3:30 pm	PANEL: Applications of Conic Programming to Robust Optimization and Other Domains V. Balakrishnan (Purdue University), Etienne De Klerk (Technische Universiteit te Delft), Leonid Faybusovich (University of Notre Dame), Michel Goemans (Massachusetts Institute of Technology), Takashi Tsuchiya (The Institute of Statistical Mathematics), Reha Tutuncu (Carnegie-Mellon University), David Williamson (IBM)	Keller 3-180
3:30 pm - 3:40 pm	Coffee Break	Keller 3-176
3:40 pm - 4:30 pm	Second Chances	Keller 3-180

Saturday, March 15, 2003

9:00 am - 9:30 am	Coffee	Keller 3-176
9:30 am - 10:20 am	A General Framework for Convex Relaxation of Polynomial Optimization Problems over Cones Masakazu Kojima (Tokyo Institute of Technology)	Keller 3-180
10:20 am - 10:30 am	Discussion Masakazu Kojima (Tokyo Institute of Technology)	Keller 3-180
10:30 am - 11:00 am	Coffee Break	Keller 3-176
11:00 am - 11:50 am	Robust Regularization and Pseudospectra Adrian Lewis (Simon Fraser University)	Keller 3-180
11:50 am - 12:00 pm	Discussion Adrian Lewis (Simon Fraser University)	Keller 3-180
12:00 pm - 1:30 pm	Lunch
1:30 pm - 2:20 pm	Theoretical Efficiency of Lift-and-Project Methods for Combinatorial Optimization Levent Tuncel (University of Waterloo)	Keller 3-180
2:20 pm - 2:30 pm	Discussion Levent Tuncel (University of Waterloo)	Keller 3-180
2:30 pm - 3:00 pm	Coffee Break	Keller 3-176
3:00 pm - 4:00 pm	Second Chances	Keller 3-180

Monday, March 17, 2003

9:00 am - 9:30 am	Coffee	Keller 3-176
9:30 am - 10:20 am	Decomposing the Algebra Associated to an SDP Pablo Parrilo (Eidgenössische TH Zürich-Zentrum)	Keller 3-180
10:20 am - 10:30 am	Discussion Pablo Parrilo (Eidgenössische TH Zürich-Zentrum)	Keller 3-180
10:30 am - 11:00 am	Coffee Break	Keller 3-176
11:00 am - 11:50 am	Some Applications of Semidefinite Programming in Probability and Algebra Jean Lasserre (Centre National de la Recherche Scientifique (CNRS))	Keller 3-180
11:50 am - 12:00 pm	Discussion Jean Lasserre (Centre National de la Recherche Scientifique (CNRS))	Keller 3-180
12:00 pm - 1:30 pm	Lunch
1:30 pm - 2:20 pm	Semidefinite Relaxations for Approximate Inference and Counting Problems Martin Wainwright (University of California, Berkeley)	Keller 3-180
2:20 pm - 2:30 pm	Discussion Martin Wainwright (University of California, Berkeley)	Keller 3-180
2:30 pm - 2:40 pm	Coffee Break	Keller 3-176
2:40 pm - 3:30 pm	Case Studies in Robust Optimization Laurent El Ghaoui (University of California, Berkeley)	Keller 3-180
3:30 pm - 3:40 pm	Discussion Laurent El Ghaoui (University of California, Berkeley)	Keller 3-180
3:40 pm - 3:50 pm	Coffee Break	Keller 3-176
3:50 pm - 4:30 pm	Second Chances	Keller 3-180

Tuesday, March 18, 2003

9:00 am - 9:30 am	Coffee	Keller 3-176
9:30 am - 10:20 am	Robust Discrete and Dynamic Optimization Dimitris Bertsimas (Massachusetts Institute of Technology)	Keller 3-180
10:20 am - 10:30 am	Discussion Dimitris Bertsimas (Massachusetts Institute of Technology)	Keller 3-180
10:30 am - 11:00 am	Coffee Break	Keller 3-176
11:00 am - 11:50 am	Optimal Transceiver Design for Multi-user Communication Zhi-Quan Luo (McMaster University)	Keller 3-180
11:50 am - 12:00 pm	Discussion Zhi-Quan Luo (McMaster University)	Keller 3-180
12:00 pm - 1:30 pm	Lunch
1:30 pm - 2:20 pm	On the Block-structured Distance to Infeasibility Javier Pena (Carnegie-Mellon University)	Keller 3-180
2:20 pm - 2:30 pm	Discussion Javier Pena (Carnegie-Mellon University)	Keller 3-180
2:30 pm - 2:40 pm	Coffee Break	Keller 3-176
2:40 pm - 3:30 pm	PANEL: Algorithmic and Implementational Issues in Conic Programming Erling Andersen (MOSEK), Samuel Burer (The University of Iowa), Michael Overton (New York University), Tamás Terlaky (McMaster University), Kim-Chuan Toh (National University of Singapore), Henry Wolkowicz (University of Waterloo)	Keller 3-180
3:30 pm - 3:40 pm	Coffee Break	Keller 3-176
3:40 pm - 4:30 pm	Second Chances	Keller 3-180
6:00 pm - 8:00 pm	Workshop Dinner

Wednesday, March 19, 2003

9:00 am - 9:10 am	Coffee	Keller 3-176
9:10 am - 10:00 am	Smooth Minimization of Non-smooth Functions Yurii Nesterov (Université Catholique de Louvain)	Keller 3-180
10:00 am - 10:10 am	Discussion Yurii Nesterov (Université Catholique de Louvain)	Keller 3-180
10:10 am - 10:20 am	Coffee Break	Keller 3-176
10:20 am - 11:10 am	Semidefinite Programming and the Bundle Method Franz Rendl (Universität Klagenfurt)	Keller 3-180
11:10 am - 11:20 am	Discussion Franz Rendl (Universität Klagenfurt)	Keller 3-180
11:20 am - 11:30 am	Coffee Break	Keller 3-176
11:30 am - 12:20 pm	Semidefinite Programming for Approximation Yinyu Ye (Stanford University)	Keller 3-180
12:20 pm - 12:30 pm	Discussion Yinyu Ye (Stanford University)	Keller 3-180
12:30 pm - 12:40 pm	Coffee Break	Keller 3-176
12:40 pm	Concluding Remarks by Organizers Laurent El Ghaoui (University of California, Berkeley), Donald Goldfarb (Columbia University), Michael Overton (New York University), Michael Todd (Cornell University)	Keller 3-180

Participants

Name	Department	Affiliation
Scot Adams	School of Mathematics	University of Minnesota, Twin Cities
Montaz Ali	School of Computational and Applied Mathematics	University of the Witwatersrand
Farid Alizadeh	RUTCOR	Rutgers, The State University of New Jersey
Erling Andersen	EKA Consulting Aps	MOSEK
Douglas Arnold	Institute for Mathematics and its Applications	University of Minnesota, Twin Cities
Donald Aronson	Institute for Mathematics and its Applications	University of Minnesota, Twin Cities
V. Balakrishnan	School of Electrical and Computer Engineering	Purdue University
Steven Benson	Mathematics and Computer Science Division	Argonne National Laboratory
Aharon Ben-Tal	Department of Industrial Engineering and Management Sciences	Technion-Israel Institute of Technology
Dimitris Bertsimas	Sloan School of Management	Massachusetts Institute of Technology
Paul Blue	Department of Computer Science	University of Minnesota, Twin Cities
Brian Borchers	Department of Mathematics	New Mexico Institute of Mining and Technology (New Mexico Tech)
Olga Brezhneva	Institute for Mathematics and its Applications	University of Minnesota, Twin Cities
Samuel Burer	Department of Management Sciences	The University of Iowa
James Burke	Department of Mathematics	University of Washington
Jamylle Carter		University of Minnesota, Twin Cities
Chek Chua	School of Operations Research and Industrial Engineering	Cornell University
Collette Coullard		Northwestern University
Etienne De Klerk	Department of Information, Systems and Algorithms	Technische Universiteit te Delft
John Dennis Jr.	Department of Computational and Applied Mathematics	Rice University
Moritz Diehl	Interdisciplinary Center for Scientific Computing	Ruprecht-Karls-Universität Heidelberg
Gregory Duane		University of Minnesota, Twin Cities
Laurent El Ghaoui	Department of Electrical Engineering and Computer Science	University of California, Berkeley
Marina Epelman	Department of Industrial and Operations Engineering	University of Michigan
Grant Erdmann	School of Mathematics	University of Minnesota, Twin Cities
Leonid Faybusovich	Department of Mathematics	University of Notre Dame
Robert Fourer	Department of Industrial Engineering and Management Sciences	Northwestern University
Robert Freund	Sloan School of Management	Massachusetts Institute of Technology
Mituhiro Fukuda	Department of Mathematics	New York University
Ashwin Ganesan	Department of Electrical Engineering and Computer Science	University of California, Berkeley
Sonja Glavaski	Advanced Technology Laboratory	Honeywell
Michel Goemans		Massachusetts Institute of Technology
Jean-Louis Goffin	Department Faculty of Management	McGill University
Donald Goldfarb	Department of Industrial Engineering and Operations Research	Columbia University
Balaji Gopalakrishnan	Institute for Mathematics and its Applications	University of Minnesota, Twin Cities
Osman Guler	Department of Mathematics & Statistics	University of Maryland Baltimore County
Anders Hansson	Department of Electrical Engineering	Linköping University
Raphael Hauser		University of Oxford
Didier Henrion	LAAS	Centre National de la Recherche Scientifique (CNRS)
Garud Iyengar	IEOR Department	Columbia University
Florian Jarre	Mathematisches Institut	Heinrich-Heine-Universität Düsseldorf
Lili Ju		University of Minnesota, Twin Cities
Herve Kerivin	Institute for Mathematics and its Applications	University of Minnesota, Twin Cities
Michal Kocvara	Institute of Applied Mathematics	Friedrich-Alexander-Universität Erlangen-Nürnberg
Masakazu Kojima	Department of Mathematical and Computing Sciences	Tokyo Institute of Technology
Vera Kovacevic-Vujcic	Faculty Organizational Sciences	University of Belgrade
Gert Lanckriet	Department of Electrical Engineering and Computer Science	University of California, Berkeley
Jean Lasserre	LAAS	Centre National de la Recherche Scientifique (CNRS)
Bruce Legan		University of Minnesota, Twin Cities
Friedemann Leibfritz	Department of Mathematics	Universität Trier
Adrian Lewis	Department of Mathematics	Simon Fraser University
Zhi-Quan Luo	Department of Electrical and Computer Engineering	McMaster University
Lisa Miller	Institute for Mathematics and its Applications	University of Minnesota, Twin Cities
Aurelia Minut	Institute for Mathematics and its Applications	University of Minnesota, Twin Cities
Renato Monteiro	Industrial and Systems Engineering Department	Georgia Institute of Technology
Francesco Montrone	Corporate Technology	Siemens AG
Thanasak Mouktonglang	Department of Mathematics	University of Notre Dame
Madhu Nayakkankuppam	Department of Mathematics & Statistics	University of Maryland Baltimore County
Arkadi Nemirovski	Department of Industrial Engineering and Management Sciences	Technion-Israel Institute of Technology
Yurii Nesterov	CORE	Université Catholique de Louvain
Peh Ng	Division of Science and Mathematics	University of Minnesota
Arnab Nilim	Department of Electrical Engineering and Computer Science	University of California, Berkeley
Jerome O'Neal	School of Industrial and Systems Engineering	Georgia Institute of Technology
Fernando Ordonez		University of Southern California
Miao-Jung Ou	Institute for Mathematics and its Applications	University of Minnesota, Twin Cities
Michael Overton	Department of Computer Science	New York University
Pablo Parrilo	Automatic Control Laboratory	Eidgenössische TH Zürich-Zentrum
Samuel Patterson	Department of Mathematics	Carleton College
Dimitri Peaucelle	Methods and Algorithms in Control	Centre National de la Recherche Scientifique (CNRS)
Javier Pena	Tepper School of Business	Carnegie-Mellon University
Florian Potra	Department of Mathematics & Statistics	University of Maryland Baltimore County
Bharath Rangarajan	Department of ORIE	Cornell University
Franz Rendl	Institut für Mathematik	Universität Klagenfurt
James Renegar	School of Operations Research and Information Engineering	Cornell University
Kees Roos	Department of Information Systems and Algorithms	Technische Universiteit te Delft
Fadil Santosa	Institute for Mathematics and its Applications	University of Minnesota, Twin Cities
Katya Scheinberg		IBM
Stefan Schmieta		Axioma Inc.
M. Nuri Sendil	Department of Industrial Engineering and Management Sciences	Northwestern University
Sashirekha Shanmugavelu	Department of Computer Engineering	University of Minnesota, Twin Cities
Tamon Stephen	Institute of Mathematics and its Application	University of Minnesota, Twin Cities
Jos Sturm	Department of Econometrics	Katholieke Universiteit Brabant (Tilburg University)
Dharmashankar Subramanian	ACS	Honeywell
Tamás Terlaky	Department of Mathematics & Statistics	McMaster University
Michael Todd	School of Operations Research and Industrial Engineering	Cornell University
Kim-Chuan Toh	Department of Mathematics	National University of Singapore
Paul Tseng	Department of Mathematics	University of Washington
Takashi Tsuchiya	Division of Statistical Computing	The Institute of Statistical Mathematics
Levent Tuncel	Department of Cominatorics and Optimization	University of Waterloo
Reha Tutuncu	Department of Mathematical Sciences	Carnegie-Mellon University
Lieven Vandenberghe	Department of Electrical Engineering	University of California, Los Angeles
Jorge Vera	Department de Ingenieria Industrial y Sistemas	Catholic University of Chile
Luis Vicente	Departamento de Matemáticas	University of Coimbra
Martin Wainwright		University of California, Berkeley
Jing Wang		University of Minnesota, Twin Cities
David Williamson		IBM
Henry Wolkowicz		University of Waterloo
Yinyu Ye		Stanford University
Emre Yildirim	Department of Applied Mathematics and Statistics	University at Albany (SUNY)
Toshio Yoshikawa	Institute of Mathematics and its Application	University of Minnesota, Twin Cities
Shuzhong Zhang	Department of Systems Eng. and Eng. Management	Chinese University of Hong Kong
Yin Zhang	Department of Computational and Applied Mathematics	Rice University
Yuriy Zinchenko	ORIE	Cornell University
Luis Zuluaga	Graduate School of Industrial Administration	Carnegie-Mellon University