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 \geq 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.
BIO: Jesús A. De Loera was born and raised in Mexico City. His work includes over 80 papers and books in Combinatorics, Algorithms, Convex Geometry, Algebra, Optimization and other Applications. He received an Alexander von Humboldt Fellowship in 2004 and the 2010 INFORMS computer society prize. For his contributions to Discrete Geometry and Combinatorial Optimization he was elected fellow of the American Mathematical Society in 2014. For his mentoring and teaching he received the 2013 Chancellor's award for mentoring undergraduate research and, in 2017, the Mathematical Association of America Golden Section Award. He has supervised twelve Ph.D students, and over 50 undergraduates research projects. He is an associate editor for ``SIAM Journal of Discrete Mathematics'' and ``SIAM journal of Applied Algebra and Geometry''.
Copyright. All Rights Reserved.