Sampled joint strategy fictitious play: A new approach to discrete optimization via simulation

The increasing complexity of modern systems is reflected in the usage of high-fidelity simulations for decision making. This environment provides incentive for the development of decentralized algorithms for the optimization of complex systems using techniques that directly incorporate performance estimates obtained via simulation.;Simulation-based optimization has been an active area of research in the recent past---though this moniker is usually applied to problems with a continuous flavor. Real world problems are often associated with decisions that involve discrete quantities, and accordingly, this dissertation attempts to address the problem of discrete optimization via simulation. As high-fidelity simulations of complex systems are both time-consuming and resource intensive there is a need to develop optimization via simulation algorithms that leverage the increasing availability of distributed computational infrastructure (for instance, through computing grids). In this dissertation, we propose the idea of Decentralized-Search/Decentralized-Evaluation (DSDE) as a means of leveraging the power of computing grids for the optimization of large-scale systems. The DSDE model breaks away from the implicit CentralizedSearch/Distributed-Evaluation (CSDE) paradigm in use today, where performance estimates obtained from a round of distributed evaluations of candidate operating points are used, by a central entity, to decide the future operating point of a complex system. In contrast, the central premise of DSDE based optimization is the representation of individual decision-making components in a system as players taking part in an artificial game with the overall (common) aim of enhancing system performance. Consequently, decentralized algorithms based on DSDE have the promise of scalability and allow for the use of game theoretic solution concepts.;In this dissertation, we develop a decentralized DSDE based algorithm inspired by the Fictitious Play algorithm, applied to games of identical interests, called Sampled Joint Strategy Fictitious Play (SJSFP). SJSFP, in conjunction with simulation, can be used to explore the decision space of a complex system in order to arrive at the set of "optimal" operating points. The main contributions of the research embodied in this dissertation are (1) the development of a practical algorithm for discrete optimization via simulation under the new DSDE model of optimization and (2) rigorous analytic characterization of the convergence properties of SJSFP for unconstrained optimization, under both noise-free and noisy (simulation-based) evaluation of cost. Finally, the SJSFP algorithm has been used to solve constrained and unconstrained non-linear integer programs that appear in the context of an Internet Traffic Engineering problem with results that compare favorably to algorithms deployed on the publicly accessible NEOS Server for Optimization.