Generalized surrogate problem methodology for online stochastic discrete optimization


Gokbayrak K. , Cassandras C.

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS, vol.114, no.1, pp.97-132, 2002 (Journal Indexed in SCI) identifier identifier

  • Publication Type: Article / Article
  • Volume: 114 Issue: 1
  • Publication Date: 2002
  • Doi Number: 10.1023/a:1015464105071
  • Title of Journal : JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS
  • Page Numbers: pp.97-132

Abstract

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.