Jesús de Loera: "Variations of Carathéodory theorem for Integer Optimization"
Latinx in the Mathematical Sciences Conference 2018 "Variations of Carathéodory theorem for Integer Optimization" Jesús de Loera, University of California, Davis ABSTRACT: Geometry has been an important pillar of the theory of optimization algorithms (e.g., think of Ellipsoid method). My talk will show this continues to be the case today by focusing on one influential theorem, Carathéodory's theorem from 1905. In its most basic form it describes the size of a minimal linear combination representing a vector in a cone and it is among the most fundamental results in Convex Geometry and it has seen many variations and extensions. I will review some variations of Carathéodory's theorem that have interesting applications in integer optimization. E.g., given a system Ax=b,x≥0, what is the size of the sparsest solution integer? Integral versions of Carathéodory’s theorem improve prior bounds and show some of the fascinating structure of sparse integer solutions of Diophantine equations. Another example will be the use of in augmentation algorithms for optimization. Our new results are joint work with Chris O’Neill, Jon Lee, Raymond Hemmecke, Iskander Aliev, Timm Oertel, Frederic Eisenbrand, and Robert Weismantel. Institute for Pure and Applied Mathematics, UCLA March 10, 2018 For more information: http://www.ipam.ucla.edu/programs/special-events-and-conferences/latinx-in-the-mathematical-sciences-conference-2018/?tab=overview
Latinx in the Mathematical Sciences Conference 2018 "Variations of Carathéodory theorem for Integer Optimization" Jesús de Loera, University of California, Davis ABSTRACT: Geometry has been an important pillar of the theory of optimization algorithms (e.g., think of Ellipsoid method). My talk will show this continues to be the case today by focusing on one influential theorem, Carathéodory's theorem from 1905. In its most basic form it describes the size of a minimal linear combination representing a vector in a cone and it is among the most fundamental results in Convex Geometry and it has seen many variations and extensions. I will review some variations of Carathéodory's theorem that have interesting applications in integer optimization. E.g., given a system Ax=b,x≥0, what is the size of the sparsest solution integer? Integral versions of Carathéodory’s theorem improve prior bounds and show some of the fascinating structure of sparse integer solutions of Diophantine equations. Another example will be the use of in augmentation algorithms for optimization. Our new results are joint work with Chris O’Neill, Jon Lee, Raymond Hemmecke, Iskander Aliev, Timm Oertel, Frederic Eisenbrand, and Robert Weismantel. Institute for Pure and Applied Mathematics, UCLA March 10, 2018 For more information: http://www.ipam.ucla.edu/programs/special-events-and-conferences/latinx-in-the-mathematical-sciences-conference-2018/?tab=overview