Jonathan Eckstein, Rutgers University

Two Optimization Problems Arising from Polling and Nonhomogeneous Poisson Processes
Oct 18, 2006, 4:30 pm5:30 pm
E219 - Engineering Quadrangle
Event Description

Abstract: This talk presents two optimization problems arising from the same applied probability application, in which we monitor an information source to which data are added at times modelled by a nonhomogeneous Poisson process.

In the first application, we suppose that the arrival rate function is known and we may poll the information source a limited number of times over some planning horizon. We develop an objective function for evaluating the quality of a polling schedule, and approximately optimize it by a combination of dynamic programming and local search. The dynamic programming algorithm uses a discrete time approximation for which we are able to prove quality guarantees.

The second application addresses the more fundamental problem of estimating the arrival rate function of a nonhomogeneous Poisson process. We argue that nonnegative splines constitute an attractive class of functions over which to search, and show that max- imum likelihood estimation over this class reduces to convex optimization over semidefinite cone and linear constraints. In particular, estimation by cubic splines reduces to convex nonlinear programming. We present numerical results in which we use a cross-validation procedure to set the number of spline knots. Our general approach can easily be adapted to density estimation and other related problems.

Various portions of this work joint with: Farid Alizadeh, Avigdor Gal, Nilay Noyan, Gabor Rudolf

Event Category
ORFE Department Colloquia