[Phd thesis topic 2023] Combinatorial convexity, its generalizations and applications to optimization
Title : Combinatorial convexity, its generalizations and applications to optimization [PDF]
Localization : Nancy
Advisor : Xavier Goaoc (https://members.loria.fr/XGoaoc/).
Team : Gamble, laboratoire LORIA and INRIA Nancy Grand Est.
Context
The general goal of this PhD thesis is to contribute to the development of combinatorial convexity and its topological generalization, as well as their applications to optimization (convex or otherwise).
The theorems of Carathéodory, Helly and Radon initiated a combinatorial theory of convexity, often dubbed combinatorial convexity, that investigates the intersection patterns of families of convex sets, with a particular attention to the systems formed by the convex hulls of subsets of a finite point set. Some landmarks in this line of research are the fractional Helly theorm of Kalai and the (p,q)-theorem of Alon and Kleitman. See for instance the textbooks [Mat02, Bár21] or the introductory lectures [BGJ+20 french).
A classical extension of combinatorial convexity relaxes the convexity asumption into more topological conditions. One way to do this is to retain only some of the topological properties of convex sets (e.g. they form good covers); another way is to interpret the system of convex hulls of a finite point set as the image of some simplicial complex under the linear map with vertices mapped to those points, and broaden our attention to the class of continuous maps. Both ways naturally relates combinatorial convexity to classical results in algebraic topology (e.g. the nerve or the Borsuk-Ulam theorems). A recent development in this line of research is the use of homological minors to deal with set systems of bounded topological complexity [GHP21, GPP+17 GPP+17, Pat20].
Convex optimization is a natural application area for combinatorial convexity, as the latter allows to analyze, explain, unify or generalize various algorithms or problems. For instance, the pivoting principle of the simplex algorithm (for linear programming) and the Lemke-Howson algorithm (for linear complementarity problems) both stem from Carathéodory’s theorem. Another example is the bounded size of bases in linear programming or chance constrained optimization, which can be traced back to Helly’s theorem and gave rise to the class of LP-type problems. See the survey [DLGMM19] for these and more examples.
Tasks
The more advanced results from combinatorial convexity, for instance the fractional Helly theorem and the (p, q)-theorem, have found so far little application in combinatorial optimization. A first task is to investigate such applications. One concrete question is the k-adaptability problem [SGW20], which asks for instance, given a parameterized linear problem, to determine some k solutions such that for any choice of parameter there is one solution that is feasible (or even as good as possible). Can combinatorial convexity guarantee that this is always possible, or help deciding whether it is? The topic of chance constrained optimization also offers many interesting questions. Raising these problems is likely to pinpoint algorithmic questions related 1to combinatorial convexity; for instance, how efficiently can one decide if a given collection of convex sets satisfies the assumption of the (p,q)-theorem (among any p, some q have a point in common)?
The combination of homological minors and Ramsey theory established that a large part of combinatorial convexity generalizes to set systems of bounded topological complexity, that is families of sets in Rd such that the intersection of any subfamily has bounded Betti numbers. These results typically give upper bounds on parameters (e.g. Helly or Radon number) that are galactic due to the use of Ramsey theory. Another task would be to revisit this body of work and give quantitatively meaningful bounds; this requires to identify and carefully analyze the combinatorial problems that were initially squashed by the Ramsey hammer. Another important question is whether the topological complexity can be allowed to grow polynomially (rather than being bounded); that this is possible was asserted some 20 years ago by Kalai and Meshulam [Kal04] in a series of conjectures that outline a theory of homological Vapnik-Chervonenkis dimension.
These two tasks naturally lead to the third task of generalizing optimization methods to set systems that are not convex, but satisfy topological assumptions. A natural example of such sets are geometric transversals.
Pre-requisites
• Msc in Computer science or in mathematics. Fluency in French or English.
• An interest in the interplay between computer science and mathematics.
• Asolid background in areas such as discrete or computational geometry, algorithms, complexity theory, topology, algebra, … is a plus.
References
[Bár21] [BGJ+20] Imre Bárány. Combinatorial convexity, volume 77. American Mathematical Soc., 2021. Marthe Bonamy, Xavier Goaoc, Fredrik Johansson, Jérôme Leroux, Marni Mishna, Irena Penev, and Sylvain Schmitz. Informatique Mathématique Une photographie en 2020. 2020.
Read more
[DLGMM19] Jesús De Loera, Xavier Goaoc, Frédéric Meunier, and Nabil Mustafa. The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg. Bulletin of the American Mathematical Society, 56(3):415–511, 2019
[GHP21] Xavier Goaoc, Andreas F. Holmsen, and Zuzana Patáková. A Stepping-Up Lemma for Topological Set Systems. In Kevin Buchin and Éric Colin de Verdière, editors, 37th International Symposium on Computational Geometry (SoCG 2021), volume 189 of Leibniz International Proceedings in Informatics (LIPIcs), pages 40:1–40:17, 2021.
[GPP+17] Xavier Goaoc, Pavel Paták, Zuzana Patáková, Martin Tancer, and Uli Wagner. Bounding Helly numbers via Betti numbers. A Journey Through Discrete Mathematics: A Tribute to Jiří Matoušek, pages 407447, 2017.
[Kal04] G. Kalai. Combinatorial expectations from commutative algebra. In I. Peeva and V. Welker, editors, Combinatorial Commutative Algebra, volume 1(3), pages 1729–1734. Oberwolfach Reports, 2004.
[Mat02] Jiri Matousek. Lectures on discrete geometry, volume 212. Springer Science & Business Media, 2002.
[Pat20] Zuzana Patáková. Bounding Radon Number via Betti Numbers. In Sergio Cabello and Danny Z. Chen, editors, 36th International Symposium on Computational Geometry (SoCG 2020), volume 164 of Leibniz International Proceedings in Informatics (LIPIcs), pages 61:1–61:13, 2020.
[SGW20] Anirudh Subramanyam, Chrysanthos E Gounaris, and Wolfram Wiesemann. K-adaptability in twostage mixed-integer robust optimization. Mathematical Programming Computation, 12:193–224, 2020
