Semidefinite programming for min-max problems and games

• 成果类型: Article
• 署名作者: Laraki, R.; Lasserre, J. B.
• 署名单位: Institut Polytechnique de Paris; Ecole Polytechnique; Centre National de la Recherche Scientifique (CNRS); Sorbonne Universite; Centre National de la Recherche Scientifique (CNRS); Universite de Toulouse; Centre National de la Recherche Scientifique (CNRS); Universite de Toulouse; Universite Toulouse III - Paul Sabatier
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-010-0353-y
• 发表日期: 2012
• 页码: 305-332
• 关键词: polynomial optimization problems; global optimization; complexity; computation; relaxations; equilibria; algorithm; moments; squares; sums

摘要

We consider two min-max problems (1) minimizing the supremum of finitely many rational functions over a compact basic semi-algebraic set and (2) solving a 2-player zero-sum polynomial game in randomized strategies with compact basic semi-algebraic sets of pure strategies. In both problems the optimal value can be approximated by solving a hierarchy of semidefinite relaxations, in the spirit of the moment approach developed in Lasserre (SIAM J Optim 11:796-817, 2001; Math Program B 112:65-92, 2008). This provides a unified approach and a class of algorithms to compute Nash equilibria and min-max strategies of several static and dynamic games. Each semidefinite relaxation can be solved in time which is polynomial in its input size and practice on a sample of experiments reveals that few relaxations are needed for a good approximation (and sometimes even for finite convergence), a behavior similar to what was observed in polynomial optimization.