Main navigation | Main content

HOME » PROGRAMS/ACTIVITIES » Annual Thematic Program

PROGRAMS/ACTIVITIES

Annual Thematic Program »Postdoctoral Fellowships »Hot Topics and Special »Public Lectures »New Directions »PI Programs »Industrial Programs »Seminars »Be an Organizer »Annual »Hot Topics »PI Summer »PI Conference »Applying to Participate »

Windter 2003

IMA Tutorial

Semidefinite Programming and Robust Optimization

IMA Tutorial

Semidefinite Programming and Robust Optimization

March 11, 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 11All
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 |

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 |

**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).

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 |