Online surrogate problem methodology for stochastic discrete resource allocation problems


Gokbayrak K. , Cassandras C.

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS, vol.108, no.2, pp.349-376, 2001 (Journal Indexed in SCI) identifier identifier

  • Publication Type: Article / Article
  • Volume: 108 Issue: 2
  • Publication Date: 2001
  • Doi Number: 10.1023/a:1026490318131
  • Title of Journal : JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS
  • Page Numbers: pp.349-376

Abstract

We consider stochastic discrete optimization problems where the decision variables are nonnegative integers. We propose and analyze an online control scheme which transforms the problem into a surrogate continuous optimization problem and proceeds to solve the latter using standard gradient-based approaches, while simultaneously updating both the actual and surrogate system states. It is shown that the solution of the original problem is recovered as an element of the discrete state neighborhood of the optimal surrogate state. For the special case of separable cost functions, we show that this methodology becomes particularly efficient. Finally, convergence of the proposed algorithm is established under standard technical conditions; numerical results are included in the paper to illustrate the fast convergence of this approach.