Method of Outer Approximations and Adaptive Approximations for a Class of Matrix Games

Elijah Polak (), Seungho Lee, Ismail Bustany and Akshay Madhan
Additional contact information
Elijah Polak: University of California
Seungho Lee: University of Illinois, Urbana-Champaign
Ismail Bustany: Mentor Graphics
Akshay Madhan: University of California

Journal of Optimization Theory and Applications, 2016, vol. 170, issue 3, No 10, 876-899

Abstract: Abstract We present a novel technique for obtaining global solutions to discrete min-max problems that arise naturally in the receding horizon control of unmanned craft in which the controls can be adjusted only in notches, e.g., stop, half forward, full forward, left or right $$60^{\circ }$$ 60 ∘ , and in the finite precision global solution of certain classes of semi-infinite min-max problems. The technique consists of a method for transcribing min-max problems over discrete sets into a matrix game and matrix game-specific adaptations of the Method of Outer Approximations and the Method of Adaptive Approximations, which are normally used for solving optimal control and semi-infinite min-max problems. The efficiency of the Method of Outer Approximations depends on having a good initial approximation to a solution. To this end, we make use of adaptive approximation techniques to decompose a large matrix game into a sequence of lower dimensional games, the solution of each giving rise to a very good initial approximation to a solution for the next game. We show that a basic approach for solving a min-max matrix game, in which one maximizes over the elements of columns and minimizes over the elements of the rows of a matrix, requires a number of function evaluations which is equal to the product of the number of rows and the number of columns of the matrix, while with our new approach our experimental results require only a number of function evaluations which is the product of the number rows and a number ranging from 2 to 20, shortening computing times from years to fractions of a minute.

Keywords: Method of Outer Approximations; Adaptive discretization; Discrete min-max problems; Receding horizon control; Global optimization; 49K35; 49M25; 49M37; 91A80 (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10957-016-0953-7 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joptap:v:170:y:2016:i:3:d:10.1007_s10957-016-0953-7

Ordering information: This journal article can be ordered from
http://www.springer. ... cs/journal/10957/PS2

DOI: 10.1007/s10957-016-0953-7

Access Statistics for this article

Journal of Optimization Theory and Applications is currently edited by Franco Giannessi and David G. Hull

More articles in Journal of Optimization Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().