On the equivalence of semidefinite programming and zero-sum semidefinite games
This provides a theoretical equivalence that could enable game-theoretic approaches to semidefinite programming, but the result is incremental as it builds on and extends existing work.
The authors prove that solving a semidefinite program is equivalent to finding optimal strategies in a zero-sum semidefinite game, under a constraint qualification. This extends previous results from linear programming to semidefinite programming, handling cases where prior reductions failed.
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.