Online Sequential Optimization with Biased Gradients: Theory and Applications to Censored Demand

摘要

In this paper, we study a class of stochastic optimization problems, where although the objective functions may not be convex, they satisfy a generalization of convexity called the sequentially convex property. We focus on a setting where the distribution of the underlying uncertainty is unknown and the manager must make a decision in real time based on historical data. Because sequentially convex functions are not necessarily convex, they pose difficulties in applying standard adaptive methods for convex optimization. We propose a nonparametric algorithm based on a gradient descent method and show that the T-season average expected cost differs from the minimum cost by at most O(1/T~(1/2)). Our analysis is based on a careful quantification of the bias that is inherent in gradient estimation because of the adaptive nature of the problem. We demonstrate the usefulness of the concept of sequential convexity by applying it to three canonical problems in inventory control, capacity allocation, and the lifetime buy decision, under the assumption that the manager does not know the demand distributions and has access only to historical sales (censored demand) data.