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

2006 2006

Other formats: Order a copy

Abstract (summary)

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.

Indexing (details)

Operations research
0796: Operations research
Identifier / keyword
Applied sciences; Discrete optimization; Fictitious play; Game theory; Joint strategy
Sampled joint strategy fictitious play: A new approach to discrete optimization via simulation
Sinha, Kaushik
Number of pages
Publication year
Degree date
School code
DAI-B 67/07, Dissertation Abstracts International
Place of publication
Ann Arbor
Country of publication
United States
Garcia, Alfredo; Patek, Stephen D.
University of Virginia
University location
United States -- Virginia
Source type
Dissertations & Theses
Document type
Dissertation/thesis number
ProQuest document ID
Database copyright ProQuest LLC; ProQuest does not claim copyright in the individual underlying works.
Document URL
Access the complete full text

You can get the full text of this document if it is part of your institution's ProQuest subscription.

Try one of the following:

  • Connect to ProQuest through your library network and search for the document from there.
  • Request the document from your library.
  • Go to the ProQuest login page and enter a ProQuest or My Research username / password.