Thorsten Theobald

Cordian Riener, Thorsten Theobald, Lina Jansson Andrén et al.

In this paper we study various approaches for exploiting symmetries in polynomial optimization problems within the framework of semi definite programming relaxations. Our special focus is on constrained problems especially when the symmetric group is acting on the variables. In particular, we investigate the concept of block decomposition within the framework of constrained polynomial optimization problems, show how the degree principle for the symmetric group can be computationally exploited and also propose some methods to efficiently compute in the geometric quotient.

Jesse Elliott, Constantin Ickstadt, Thorsten Theobald et al.

By results of Dantzig (1951) and Adler (2013), computing the optimal solutions of a linear program is equivalent to finding optimal strategies in zero-sum bimatrix games. Dantzig's original result was incomplete, in the sense that the reduction of a linear program to a zero-sum game did not work for all possible linear programs. We show that, under a natural constraint qualification requiring either the existence of strongly optimal primal-dual solutions or of a strictly unbounded direction, computing the solution of a semidefinite program is equivalent to finding optimal strategies in an associated zero-sum semidefinite game. Our work builds upon Ickstadt, Theobald, and Tsigaridas (2024), where, similar to Dantzig's work, the proposed reduction cannot handle a certain subclass of semidefinite programs. Our main proof ingredients for the equivalence result include: (i) a semidefinite generalization of von Stengel's (2023) extension of Dantzig's construction; (ii) techniques for handling more general duality phenomena in the semidefinite setting; and (iii) an explicit bound for the (coordinates) of the solutions of a semidefinite program. As a by-product, the game value provides a certificate: it is zero if and only if strongly optimal solutions exist, and otherwise optimal strategies yield an infeasibility certificate for the primal or dual program.