Online surrogate problem methodology for stochastic discrete resource allocation problems


Gokbayrak K. , Cassandras C.

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS, cilt.108, ss.349-376, 2001 (SCI İndekslerine Giren Dergi) identifier identifier

  • Cilt numarası: 108 Konu: 2
  • Basım Tarihi: 2001
  • Doi Numarası: 10.1023/a:1026490318131
  • Dergi Adı: JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS
  • Sayfa Sayıları: ss.349-376

Özet

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.