×

Method of outer approximations and adaptive approximations for a class of matrix games. (English) Zbl 1350.49032

Summary: 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°\), 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.

MSC:

49M25 Discrete approximations in optimal control
49M37 Numerical methods based on nonlinear programming
49K35 Optimality conditions for minimax problems
91A80 Applications of game theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Isaacs, R.: Differential Games. Wiley, New York (1967) · Zbl 0152.38407
[2] Lee, S., Polak, E., Walrand, J.: A receding horizon control law for harbor defense. In: Proceedings 51th Annual Allerton Conference on Communication, Control, and Computing (2013)
[3] Walrand, J., Polak, E., Chung, H.: Harbor attack: a pursuit-evasion game. In: Proceedings 49th Annual Allerton Conference on Communication, Control, and Computing (2011)
[4] Polak, E.: Optimization: Algorithms and Consistent Approximations. Springer, New York (1997) · Zbl 0899.90148 · doi:10.1007/978-1-4612-0663-7
[5] Newell, A., Simon, H.: Computer science as empirical inquiry: symbols and search. Commun. ACM 19(3), 113-126 (1976) · doi:10.1145/360018.360022
[6] Pearl, J.: Scout: A simple game-searching algorithm with proven optimal properties. In: Proceedings, AAAI National Conference, pp. 143-145 (1980) · Zbl 0861.49002
[7] Pearl, J.: Asymptotic properties of minimax trees and game-searching procedures. Artif. Intell. 14(2), 113-138 (1980) · Zbl 0445.68048 · doi:10.1016/0004-3702(80)90037-5
[8] Plaat, A., Schaeffer, J., Pijls, W., Bruin, A.: Best-first fixed-depth minimax algorithms. Artif. Intell. 87(1), 255-293 (1996) · Zbl 1506.68127 · doi:10.1016/0004-3702(95)00126-3
[9] Bhattacharjee, B., Lemonidis, P., Green, W.H., Barton, P.I.: Global solution of semi-infinite programs. Math. Program. 103(2), 283-307 (2005) · Zbl 1090.90188 · doi:10.1007/s10107-005-0583-6
[10] Gonzaga, C., Polak, E.: On constraint dropping schemes and optimality functions for a class of outer approximations algorithms. SIAM J. Control Optim. 17(4), 477-493 (1979) · Zbl 0412.90059 · doi:10.1137/0317034
[11] Polak, E.: On a class of numerical methods with an adaptive integration subprocedure for optimal control problems. In: Proceedings of Fourth IFIP Colloquium on Optimization (1971)
[12] Royset, J.O., Kiureghian, A.D., Polak, E.: Successive approximations for the solution of optimal design problems with probabilistic objective and constraints. In: Proceedings of the 9th International Conference on Applications of Statistics and Probability in Civil Engineering (2003) · Zbl 1042.49033
[13] Polak, E., Wetter, M.: Generalized pattern search algorithms with adaptive precision function evaluations. SIAM 16(3), 650-669 (2006) · Zbl 1113.90148 · doi:10.1137/040605527
[14] Mayne, D.Q., Rawlings, J.B., Rao, C.V., Scokaert, P.O.M.: Constrained model predictive control: stability and optimality. Automatica 36(6), 789-814 (2000) · Zbl 0949.93003 · doi:10.1016/S0005-1098(99)00214-9
[15] Sprinkle, J., Eklund, J., Kim, H., Sastry, S.: Encoding aerial pursuit/evasion games with fixed wing aircraft into a nonlinear model predictive tracking controller. In: 43rd IEEE Conference on Decision and Control (2004)
[16] Lee, S., Polak, E., Walrand, J.: On the use of min-max algorithms in receding horizon control laws for harbor defense. In: Rodrigues, H., Herskovits, J. (eds). Engineering Optimization, pp. 211-216. CRC Press (2014)
[17] Xu, S.: Smoothing method for minimax problems. Comput. Optim. Appl. 20, 267-279 (2001) · Zbl 1054.90087 · doi:10.1023/A:1011211101714
[18] Jamil, M., Yang, X.: A literature survey of benchmark functions for global optimization problems. Int. J. Math. Model. Numer. Optim. 4(2), 150-194 (2013) · Zbl 1280.65053
[19] Whitley, D., Mathias, K., Rana, R., Dzubera, J.: Evaluating evolutionary algorithms. Artif. Intell. 85, 245-276 (2001) · doi:10.1016/0004-3702(95)00124-7
[20] Schwartz, A., Polak, E.: Consistent approximations for optimal control problems based on Runge-Kutta integration. SIAM J. Control Optim. 34(4), 235-269 (1996) · Zbl 0861.49002 · doi:10.1137/S0363012994267352
[21] Hager, W.: Runge-Kutta methods in optimal control and the transformed adjoint system. Numer. Math. 87(2), 247-282 (2000) · Zbl 0991.49020 · doi:10.1007/s002110000178
[22] Kaya, C.Y., Martinez, J.M.: Euler discretization and inexact restoration for optimal control. J. Optim. Theory Appl. 134(2), 191-206 (2007) · Zbl 1135.49019 · doi:10.1007/s10957-007-9217-x
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.