HOME    »    PROGRAMS/ACTIVITIES    »    Annual Thematic Program
Windter 2003
IMA Tutorial
Semidefinite Programming and Robust Optimization
March 11, 2003


Optimization, September 2002 - June 2003

Organizer:

Michael J. Todd
Operations Research and Industrial Engineering
Cornell University
miketodd@cs.cornell.edu
http://www.orie.cornell.edu/~miketodd/todd.html

This tutorial consists of two introductory lectures on semidefinite programming, robust optimization, and their applications in various fields.

TUTORIAL SCHEDULE
TUESDAY, MARCH 11
All talks are in Lecture Hall EE/CS 3-180 unless otherwise noted.
9:00-9:30 am Coffee and Registration

Reception Room EE/CS 3-176

9:30-10:30 am
10:45-11:45 am
Farid Alizadeh
RUTCOR and School of Business, Rutgers University

Semidefinite and Second Order Cone Programming: Foundations, Algorithms and Applications

Slides:   pdf    ps

1:45-2:30 pm
2:45-3:30 pm
Laurent El Ghaoui
(University of California at Berkeley)

Robust Optimization: Applications in Control and Machine Learning Problems

Slides:   html    pdf    ppt

Abstracts

Farid Alizadeh (RUTCOR and School of Business, Rutgers University) alizadeh@rutcor.rutgers.edu

Semidefinite and Second Order Cone Programming: Foundations, Algorithms and Applications    Slides:   pdf    ps

Semidefinite programming (SDP) is an optimization problem which, broadly stated, has as decision variables one or more symmetric matrices that are positive semidefinite. SDP is a powerful modeling tool and can be used to formulate many optimization problems. Among them are 1) minimization (maximization) of the largest (smallest) eigenvalues of symmetric or Hermitian matrices or the largest singular values of arbitrary matrices with additional constraints on them, 2) shape-constrained approximation and regression of unknown functions from a finite sample, 3) several combinatorial optimization problems including some that have prohibitive computational cost which nonetheless can be approximated using SDP, 4) and some robust optimization problems.

Second Order Cone Programming (SOCP) is an optimization problem which is more general than linear programming, but is a special case of semidefinite programing. Similar to SDP, SOCP is a powerful modeling tool that can be applied to a wide array of applications. However its special structure allows us to provide tailor-made algorithms that make SOCP easier to handle than a general semidefinite program.

In this tutorial we divide the time into three parts. First we spend some time defining the SDP and SOCP problems and survey their applications in areas as diverse as robust linear and quadratic programming, optimal stock portfolio selection, truss topology design in structural engineering, and many other areas. Next we survey the structure of SDP and SOCP, in particular we review concepts of duality, nondegeneracy, and their underlying algebraic structure. Finally we discuss efficient algorithms and some software design issues for these problems. In particular we will discuss interior point methods, and for SOCP active set methods and Goldfarb's extension of linear programming simplex method. We will also review the issue of sparse input data and how it may be used to design more efficient software.

Throughout the presentation we will emphasize the close relationship between SDP and SOCP, and in particular underscore how much simpler SOCP problems are. The lecture will be kept as intuitive as possible, and not much beyond basic linear algebra will be required to follow it.

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

Robust Optimization: Applications in Control and Machine Learning Problems    Slides:   html    pdf    ppt

Robust optimization deals with optimization problems in which the data (say, the coefficients in a linear program) are only known within a set, and a decision variable guaranteed to satisfy all the constraints despite data uncertainty is sought. We describe the main results in robust optimization, in particular how second-order cone or semidefinite programming relaxations can be used to obtain robust solutions to uncertain programs. We explore connections between the robust (or worst-case) approach and stochastic descriptions of uncertainty, in which the distribution of the uncertainty is partially known. We then give an overview of applications, ranging from control systems (robust control of uncertain dynamical systems) to machine learning (robust classification, support vector machines, and kernel optimization).

LIST OF CONFIRMED PARTICIPANTS

As of 3/20/2003
Name Department Affiliation
Farid Alizadeh RUTCOR Rutgers University
Kartik B. Ariyur Honeywell Labs Honeywell, Inc.
Slava Belyaev   ITEP-Minneapolis, MN
Aharon Ben-Tal Industrial Engineering and Management Technion
Paul Blue Computer Science University of Minnesota
Brian Borchers Mathematics New Mexico Tech
Olga Brezhneva Institute for Mathematics and its Applications University of Minnesota
Jamylle Carter Mathematics University of Minnesota
Collette Coullard Industrial Eng. & Mgmt. Sciences Northwestern University
Ranjana Deshpande AES Honeywell Lab
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
Michael R. Elgersma Control and Optimization Honeywell
Marina A. Epelman Dept of Industrial and Operations Engineering University of Michigan
Grant Erdmann Mathematics University of Minnesota
Lisa Evans IMA University of Minnesota
Robert Fourer Industrial Engineering & Management Scien Northwestern University
Mituhiro Fukuda Mathematics New York University
Ashwin Ganesan Electrical Engineering & Computer Science University of California at Berkeley
Ankur Ganguli Mechanical Engineering University of Minnesota
Subhabrata Ganguli Mechanical Engineering University of Minnesota
Balaji Gopalakrishnan Institute for Mathematics and its Application University of Minnesota
Herve Kerivin IMA University of Minnesota
Tamas Keviczky Control Science & Dynamical Systems University of Minnesota
Masakazu Kojima Mathematical & Computing Sciences Tokyo Institute of Technology
Nitin Lamba Aerospace Electronic Systems Honeywell Labs
Gert Lanckriet Electrical Engineering & Computer Science University of California at Berekley
Jean B. Lasserrre   LAAS-CNRS
Andres Marcos Aerospace Engineering University of Minnesota
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
Peh Ng IMA University of Minnesota
Jerome W. O'Neal Industrial and Systems Engineering Georgia Institute of Technology
Pablo A. Parrilo Automatic Control Laboratory Swiss Federal Institute of Technology
Javier Pena Graduate Industrial Administration Carnegie Mellon University
Damrongrit Piyabongkarn Mechanical Engineering University of Minnesota
Aliveza Razari Electrical Computer Engineering University of Minnesota
Vic Reiner Mathematics University of Minnesota
Katya Scheinberg   IBM T.J. Watson Research Center
M. Nuri Sendil Industrial Eng. & Mgmt. Sciences Northwestern University
Sashirekha Shanmugavelu Computer Engineering University of Minnesota
Tamon Stephen IMA University of Minnesota
Dharmashankar Subramanian ACS Honeywell Labs
Michael Todd Operations Research and Industrial Engin Cornell University
Kim-Chuan Toh Mathematics National University of Singapore
Takashi Tsuchiya Statistical Computing The Institute of Statistical Mathematics
Luis Nunes Vicente Matemática Universidade de Coimbra
Jing Wang Institute for Mathematics and its Application University of Minnesota
Emre Alper Yildirim Applied Mathematics & Statistics SUNY at Stonybrook
Luis F. Zuluaga GSIA Carnegie Mellon University

Workshop 5, March 12-19, 2003

Connect With Us:
Go