A stochastic algorithm using one sample point per iteration and diminishing stepsizes

A stochastic algorithm for finding stationary points of real-valued functions defined on a Euclidean space is analyzed. It is based on the Robbins-Monro stochastic approximation procedure. Gradient evaluations are done by means of Monte Carlo simulations. At each iteratex _i , one sample point is drawn from an underlying probability space, based on which the gradient is approximated. The descent direction is against the approximation of the gradient, and the stepsize is 1/i. It is shown that, under broad conditions, w.p.1 if the sequence of iteratesx ₁,x ₂,...generated by the algorithm is bounded, then all of its accumulation points are stationary.     

Stochastic algorithms with armijo stepsizes for minimization of functions

Stochastic algorithms for optimization problems, where function evaluations are done by Monte Carlo simulations, are presented. At each iteratex _i, they draw a predetermined numbern(i) of sample points from an underlying probability space; based on these sample points, they compute a feasible-descent direction, an Armijo stepsize, and the next iteratex _i+1. For an appropriate optimality function , corresponding to an optimality condition, it is shown that, ifn(i) , then (x _i) 0, whereJ is a set of integers whose upper density is zero. First, convergence is shown for a general algorithm prototype: then, a steepest-descent algorithm for unconstrained problems and a feasible-direction algorithm for problems with inequality constraints are developed. A numerical example is supplied.     

Stochastic approximation algorithm for minimax problems

A stochastic approximation algorithm for minimax optimization problems is analyzed. At each iterate, it performs one random experiment, based on which it computes a direction vector. It is shown that, under suitable conditions, it a.s. converges to the set of points satisfying necessary optimality conditions. The algorithm and its analysis bring together ideas from stochastic approximation and nondifferentiable optimization.     

A Nondifferentiable Optimization Algorithm for Structural Problems with Eigenvalue Inequality Constraints*

This paper presents a nondifferentiable optimization algorithm for solution of structural optimal design problems with eigenvalue inequality constraints. The algorithm is shown to be convergent both in the L _∞ and in the sequence space topologies.     

Optimal Release Times in Single-Stage Manufacturing Systems with Blocking: Optimal Control Perspective

This paper concerns a due-date matching problem in a single-stage manufacturing system. Given a finite sequence of jobs and their service order, and given the delivery due date of each job, the problem is to choose the jobs release (arrival) times so as to match as closely as possible their completion times to their respective due dates. The system is modelled as a deterministic single-server FIFO queue with an output buffer for storing jobs whose service is completed prior to their due dates. The output buffer has a finite capacity; when it is full, the server is being blocked. Associated with each job there is a convex cost function penalizing its earliness as well as tardiness. The due-date matching problem is cast as an optimal control problem, whose objective is to minimize the sum of the above cost functions by the choice of the jobs arrival (release) times. Time-box upper-bound and lower-bound constraints are imposed on the jobs output (delivery) times. The optimal-control setting brings to bear on the development of fast and efficient algorithms having intuitive geometric appeal and potential for online implementation.Communicated by W. B. GongResearch supported in part by the National Science Foundation under Grant ECS-9979693 and by the Georgia Tech Manufacturing Research Center under Grant B01-D06.     

Online IPA Gradient Estimators in Stochastic Continuous Fluid Models

This paper applies infinitesimal perturbation analysis (IPA) to loss-related and workload-related metrics in a class of stochastic flow models (SFM). It derives closed-form formulas for the gradient estimators of these metrics with respect to various parameters of interest, such as buffer size, service rate, and inflow rate. The IPA estimators derived are simple and fast to compute, and are further shown to be unbiased and nonparametric, in the sense that they can be computed directly from the observed data without any knowledge of the underlying probability law. These properties hold out the promise of utilizing IPA gradient estimates as ingredients of online management and control of telecommunications networks. While this paper considers single-node SFMs, the analysis method developed is amenable to extensions to networks of SFM nodes with more general topologies.     

Consistency of perturbation analysis for a queue with finite buffer space and loss policy

The subject of discrete-event dynamical systems has taken on a new direction with the advent of perturbation analysis (PA), an efficient method for estimating the gradients of a steady-state performance measure, by analyzing data obtained from a single-simulation experiment in the time domain. A crucial issue is whether PA gives strongly consistent estimates, namely, whether average time-domain-based gradients converge, over infinite horizon, to the steady-state gradients. In this paper, we investigate this issue for a queue with a finite buffer capacity and a loss policy. The performance measure in question is the average amount of lost customers, as a function of the buffer's capacity, which is assumed to be continuous in our work. It is shown that PA gives strongly consistent estimates. The analysis uses a new technique, based on busy period-dependent inequalities. This technique may have possible extensions to analyses of consistency of PA for more general queueing systems.     

IPA derivatives for a discrete model of make-to-stock production-inventory systems with backorders

We consider a class of single-stage, single-product Make-to-Stock production-inventory system (MTS system) with backorders. The system employs a continuous-review base-stock policy which strives to maintain a prescribed base-stock level of inventory. In a previous paper of Zhao and Melamed (Methodology and Computing in Applied Probability 8:191–222, 2006), the Infinitesimal Perturbation Analysis (IPA) derivatives of inventory and backorders time averages with respect to the base-stock level and a parameter of the production-rate process were computed in Stochastic Fluid Model (SFM) setting, where the demand stream at the inventory facility and its replenishment stream from the production facility are modeled by stochastic rate processes. The advantage of the SFM abstraction is that the aforementioned IPA derivatives can be shown to be unbiased. However, its disadvantages are twofold: (1) on the modeling side, the highly abstracted SFM formulation does not maintain the identity of transactions (individual demands, orders and replenishments) and has no notion of lead times, and (2) on the applications side, the aforementioned IPA derivatives are brittle in that they contain instantaneous rates at certain hitting times which are rarely known, and consequently, need to be estimated. In this paper, we remedy both disadvantages by using a discrete setting, where transaction identity is maintained, and order fulfillment from inventory following demand arrivals and inventory restocking following replenishment arrivals are modeled as discrete jumps in the inventory level. We then compute the aforementioned IPA derivatives with respect to the base-stock level and a parameter of the lead-time process in the discrete setting under any initial system state. The formulas derived are shown to be unbiased and directly computable from sample path observables, and their computation is both simple and computationally robust.     

Convergence analysis of gradient descent stochastic algorithms

This paper proves convergence of a sample-path based stochastic gradient-descent algorithm for optimizing expected-value performance measures in discrete event systems. The algorithm uses increasing precision at successive iterations, and it moves against the direction of a generalized gradient of the computed sample performance function. Two convergence results are established: one, for the case where the expected-value function is continuously differentiable; and the other, when that function is nondifferentiable but the sample performance functions are convex. The proofs are based on a version of the uniform law of large numbers which is provable for many discrete event systems where infinitesimal perturbation analysis is known to be strongly consistent.