Mathematics – Optimization and Control
Scientific paper
2008-10-17
Mathematics
Optimization and Control
21 pages
Scientific paper
We introduce two min-max problems: the first problem is to minimize the supremum of finitely many rational functions over a compact basic semi-algebraic set whereas the second problem is a 2-player zero-sum polynomial game in randomized strategies and with compact basic semi-algebraic pure strategy sets. It is proved that their optimal solution can be approximated by solving a hierarchy of semidefinite relaxations, in the spirit of the moment approach developed in Lasserre. This provides a unified approach and a class of algorithms to approximate all Nash equilibria and min-max strategies of many static and dynamic games. Each semidefinite relaxation can be solved in time which is polynomial in its input size and practice from global optimization suggests that very often few relaxations are needed for a good approximation (and sometimes even finite convergence).
Laraki Rida
Lasserre Jean B.
No associations
LandOfFree
Semidefinite Programming for Min-Max Problems and Games does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Semidefinite Programming for Min-Max Problems and Games, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Semidefinite Programming for Min-Max Problems and Games will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-352414