Winter 2003

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.

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.

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