Session: Applications of polynomial optimization to data analysis II
Chair: Yong Sheng Soh
Cluster: Conic and Semidefinite Optimization
Talk 1: Semidefinite Network Games
Speaker: Antonios Varvitsiotis
Abstract: Network games are an important class of games that model agent interactions in networked systems, where players are situated at the nodes of a graph and their payoffs depend on the actions taken by their neighbors. We extend the classical framework by considering a game model where the strategies are positive semidefinite matrices having trace one. These (continuous) games can serve as a simple model of quantum strategic interactions. We focus on the zero-sum case, where the sum of all players’ payoffs is equal to zero. We establish that in this class of games, Nash equilibria can be characterized as the projection of a spectrahedron, that is, the feasible region of a semidefinite program. Furthermore, we demonstrate that determining whether a game is a semidefinite network game is equivalent to deciding if the value of a semidefinite program is zero. Beyond the zero-sum case, we characterize Nash equilibria as the solutions of a semidefinite linear complementarity problem.
Talk 2: Sum of squares hierarchy for the Gromov-Wasserstein Problem
Speaker: Yong Sheng Soh
Abstract: The Gromov-Wasserstein (GW) Problem is an extension of the classical optimal transport problem that allows one to compute distances between probability distributions specified over incomparable metric spaces. Broadly speaking, to get around the lack of a natural notion of distance between objects residing in different metric spaces, the GW computes the minimum of a suitably defined objective taken over all possible embeddings of the input metric spaces to a common space. This process leaves us with solving a non-convex quadratic programming instance. In this talk, we discuss the ideas of the sum-of-squares hierarchy applied to solving the GW problem. As a note, the central object of interest in the GW problem is a probability distribution, and we describe the necessary language in which ideas of polynomial optimization carry through to distributions.
Talk 3: On the geometric and computational complexity of polynomial bilevel optimization
Speaker: Quoc-Tung Le
Abstract: Bilevel optimization is an important mathematical tool to model phenomena in many domains, such as economic game theory, decision science and machine learning, to name but a few. Despite its importance, efficient and scalable algorithms for bilevel optimization are mostly developed for the (strong) convexity of the lower-level problem case, which is unrealistic for many practical tasks. In the quest to understand more general bilevel problems, we relax the lower level strong convexity and consider polynomial bilevel optimization, i.e., polynomial objective functions and constraints. We focus on the worst-case analysis of this class of problems, from both geometric and computational viewpoints. Our analysis suggests that even the algebraic rigidity of polynomials does not exclude extreme pathologies induced by the bilevel optimization. More specifically, we demonstrate that any semi-algebraic function can be represented as the objective of a polynomial bilevel problem. This discovery implies that solving polynomial bilevel optimization is equivalent to optimizing general semi-algebraic functions. We obtain other sharp variations of this result by considering relevant properties of the lower problem, such as convexity or feasible set compacity. In addition, we show the Σ2p-hardness of polynomial bilevel optimization, characterizing polynomial bilevel problems as vastly more challenging than NP-complete problems (under reasonable hardness assumptions).
