Applying Metric Regularity to Compute a Condition Measure of a Smoothing Algorithm for Matrix Games
Authors:
- Boris S. MordukhovichBMBoris S. Mordukhovich
- Javier F. PeñaJPJavier F. Peña
- Vera RoshchinaVRVera Roshchina
- 1 January 2010
- journal article
- research article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Optimization
- Vol. 20 (6) , 3490-3511
Abstract
We develop an approach of variational analysis and generalized differentiation to conditioning issues for two-person zero-sum matrix games. Our major results establish precise relationships between a certain condition measure of the smoothing first-order algorithm proposed by Gilpin, Peña, and Sandholm [Proceedings of the 23rd Conference on Artificial Intelligence, 2008, pp. 75–82] and the exact bound of metric regularity for an associated set-valued mapping. In this way we compute the aforementioned condition measure in terms of the initial matrix game data.Keywords
All Related Versions
This publication has 17 references indexed in Scilit:
- Local Linear Convergence for Alternating and Averaged Nonconvex ProjectionsFoundations of Computational Mathematics, 2008
- Optimization methods and stability of inclusions in Banach spacesMathematical Programming, 2007
- Convergence of the Proximal Point Method for Metrically Regular MappingsESAIM: Proceedings, 2007
- Excessive Gap Technique in Nonsmooth Convex MinimizationSIAM Journal on Optimization, 2005
- Smooth minimization of non-smooth functionsMathematical Programming, 2004
- Computing approximate solutions for convex conic systems of constraintsMathematical Programming, 2000
- Efficient Computation of Behavior StrategiesGames and Economic Behavior, 1996
- Incorporating Condition Measures into the Complexity Theory of Linear ProgrammingSIAM Journal on Optimization, 1995
- Complete characterization of openness, metric regularity, and Lipschitzian properties of multifunctionsTransactions of the American Mathematical Society, 1993
- Maximum principle in the problem of time optimal response with nonsmooth constraintsJournal of Applied Mathematics and Mechanics, 1976