Friday, January 20, 2006
1:30 p.m. Posner Hall 261
Javier Pena Professor, Tepper School of Business Carnegie Mellon University
Semidefinite Programming Relaxations for Polynomial Optimization Problems
A common paradigm in optimization is the use of well-understood models to address more complex problems. For instance, linear programming is used as a fundamental subroutine in branch-and-bound and branch-and-cut algorithms for integer programming. An interesting parallel is the use of semidefinite programming to address optimization problems involving polynomials. In this context semidefinite programming relaxations can often be obtained by a clever application of tools from algebraic geometry. In this presentation we will discuss some of the main ideas underlying these connections between semidefinite programming and algebraic geometry. We will also discuss some of the structural patterns that typically arise in the resulting semidefinite programming relaxations, and techniques to take advantage of such structure.
This is based on joint work with Juan Vera at Carnegie Mellon and Luis Zuluaga at University of New Brunswick in Canada.
