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

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.