Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Robust Semidefinite Programming

Student-Run Research Seminar

Speaker: Prof. Laurent El-Ghaoui
Location: 593 Kerr
Start time: Mon, Nov 27 2000, 2:10PM

A semidefinite program (SDP) is an optimization problem with linear objective and positive semidefinite constraints on symmetric matrices depending affinely on the decision variables. SDPs arise in connection with a host of engineering and operations research problems; most of the time however, the data in these problems is not exactly known.

The SDP framework is particularly attractive because it can be used for {em robust optimization}. In a robust optimization problem, the data that defines the constraints and objective is only known to belong to a given set, and the purpose is to find a solution that remains feasible despite the uncertainty on the data, and which minimizes a worst-case objective. Using SDPs, one can approximate exhaustively (compute guaranteed bounds) for these problems.

In this talk, we describe several applications of SDP and robust optimization, ranging from linear equations with interval data, combinatorial optimization, and moment problems, in which the probability of an event is to be estimated, given partial (moment) information on the distribution.