|
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: |
|
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>
|
|