Lifts of convex sets
 
 
Description:  It is well-known that some complicated polytopes can be represented as projections of much simpler polytopes permitting polynomial time algorithms for linear optimization over them. In 1991 Yannakakism established a connection between the existence of such lifts and the nonnegative rank of the slack matrix of the polytope. In this talk we will introduce the basic theory and extend Yannakakis results to general lifts of arbitrary convex sets. These results offer a uniform view of all LP and SDP-based lift-and-project methods. Joint work with Pablo Parrilo and Rekha Thomas.
Date:  2011-09-21
Start Time:   14:30
Speaker:  João Gouveia (Mat FCTUC)
Institution:  Dep. Matemática, Universidade de Coimbra, Portugal
Place:  Room 5.5
Research Groups: -Numerical Analysis and Optimization
See more:   <Main>  
 
© Centre for Mathematics, University of Coimbra, funded by
Science and Technology Foundation
Powered by: rdOnWeb v1.4 | technical support