Generalized surrogate problem methodology for online stochastic discrete optimization


Gokbayrak K. , Cassandras C.

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS, cilt.114, sa.1, ss.97-132, 2002 (SCI İndekslerine Giren Dergi) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 114 Konu: 1
  • Basım Tarihi: 2002
  • Doi Numarası: 10.1023/a:1015464105071
  • Dergi Adı: JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS
  • Sayfa Sayıları: ss.97-132

Özet

We consider stochastic discrete optimization problems where the decision variables are nonnegative integers and propose a generalized surrogate problem methodology that modifies and extends previous work in Ref. 1. Our approach is based on 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. In contrast to Ref. 1, the proposed methodology applies to arbitrary constraint sets. It is shown that, under certain conditions, the solution of the original problem is recovered from the optimal surrogate state. Applications of this approach include solutions to multicommodity resource allocation problems; in these problems, exploiting the convergence speed of the method, one can overcome the obstacle posed by the presence of local optima.