A Provable Semi-Infinite Programming Approach for Solving Constrained Dynamic Games

Many engineering problems must account for the non-cooperative decisions and actions of multiple players. These problems can be modeled within a game-theoretic framework. The approach herein is to model such problems as mathematical games, convert them to semi-infinite programs, and utilize a semi-infinite program solver whose output is provably an ϵ -optimal Nash equilibrium. The approach is successfully benchmarked on two low-dimensional problems. Two types of higher-dimensional linear quadratic dynamic games are then investigated: ones where each player’s problem is convex and ones where at least one player’s problem is nonconvex. Within each type, variations based on information structure, control constraints, number of players, and semi-infinite objective are considered. The algorithm is tested with different internal solvers, and it successfully solves all test problems using MATLAB’s fmincon. The numerical solutions approximate analytical solutions (when they are known) within approximately one percent. For a three-player game with input saturation constraints, hundreds of variables, and no analytical solution, the computational time is approximately five minutes.