Stochastic programming, progressive hedging, and projective splitting methods

Jonathan Eckstein, Rutgers University
EQuad - E219

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 maximum 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