An algorithm for approximating piecewise linear concave functions from sample gradients

Huseyin Topaloglu, Warren Buckler Powell

Research output: Contribution to journalArticle

22 Scopus citations

Abstract

An effective algorithm for solving stochastic resource allocation problems is to build piecewise linear, concave approximations of the recourse function based on sample gradient information. Algorithms based on this approach are proving useful in application areas such as the newsvendor problem, physical distribution and fleet management. These algorithms require the adaptive estimation of the approximations of the recourse function that maintain concavity at every iteration. In this paper, we prove convergence for a particular version of an algorithm that produces approximations from stochastic gradient information while maintaining concavity.

Original languageEnglish (US)
Pages (from-to)66-76
Number of pages11
JournalOperations Research Letters
Volume31
Issue number1
DOIs
StatePublished - Jan 2003

All Science Journal Classification (ASJC) codes

  • Software
  • Management Science and Operations Research
  • Industrial and Manufacturing Engineering
  • Applied Mathematics

Keywords

  • Almost sure convergence
  • Approximation
  • Concave functions
  • Stochastic gradient methods

Fingerprint Dive into the research topics of 'An algorithm for approximating piecewise linear concave functions from sample gradients'. Together they form a unique fingerprint.

  • Cite this