×

Estimating arrival rate of nonhomogeneous Poisson processes with semidefinite programming. (English) Zbl 1274.90255

Summary: We present a summary of methods based on semidefinite programming for estimating arrival rate of nonhomogeneous Poisson processes from a finite set of observed data. Both one-dimensional time dependent, and multi-dimensional time and location dependent rates are considered. The arrival rate is a nonnegative function of time (or time and location). We also assume that it is a smooth function with continuous derivatives of up to certain order \(k\). We estimate the rate function by one or multi-dimensional splines, with the additional condition that the underlying rate function is nonnegative. This approach results in an optimization problem over nonnegative polynomials, which can be modeled and solved using semidefinite programming. We also describe a method which requires only linear constraints. Numerical results based on e-mail arrival and highway accidents are presented.

MSC:

90C22 Semidefinite programming
60G07 General theory of stochastic processes

Software:

NEOS; KNITRO; AMPL
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alizadeh, F., Eckstein, J., Noyan, N., & Rudolf, G. (2008). Arrival rate approximation by nonnegative cubic splines. Operations Research, 56(1), 140–156. · Zbl 1167.90436 · doi:10.1287/opre.1070.0443
[2] Alizadeh, F., & Goldfarb, D. (2003). Second-order cone programming. Mathematical Programming, 95(1), 3–51. · Zbl 1153.90522 · doi:10.1007/s10107-002-0339-5
[3] Ben-Tal, A., & Nemirovskiaei, A. S. (2001). Lectures on modern convex optimization: analysis, algorithms, and engineering applications. Philadelphia: Society for Industrial and Applied Mathematics. · Zbl 0986.90032
[4] Boros, E., & Hammer, P. L. (2002). Pseudo-Boolean optimization. Discrete Applied Mathematics, 123(1–3), 155–225. doi: 10.1016/S0166-218X(01)00341-9 . · Zbl 1076.90032 · doi:10.1016/S0166-218X(01)00341-9
[5] Byrd, R. M., Hribar, M. E., & Nocedal, J. (1999). An interior point method for large scale nonlinear programming. SIAM Journal on Optimization, 9(4), 877–900. · Zbl 0957.65057 · doi:10.1137/S1052623497325107
[6] Czyzyk, J., Mesnier, M., & Moré, J. (1998). The NEOS server. IEEE Journal of Computer Sciences and Engineering, 5(3), 68–75. · Zbl 05092192 · doi:10.1109/99.714603
[7] Dette, H., & Studden, W. J. (1997). The theory of canonical moments with applications in statistics, probability, and analysis. New York: Wiley. · Zbl 0886.62002
[8] Dolan, E. (2001). The NEOS server 4.0 administrative guide (Technical Report ANL/MCS-TM-250). Mathematics and Computer Science Division, Argonne National Laboratory, Argonne, IL.
[9] Fourer, R., Gay, D. M., & Kernighan, B. W. (2002). AMPL: a modeling language for mathematical programming (2nd ed.). Danvers: Boyd and Fraser. · Zbl 0701.90062
[10] Gropp, W., & Moré, J. (1997). Optimization environments and the NEOS server. In M. D. Buhman & A. Iserles (Eds.), Approximation theory and optimization (pp. 167–182). Cambridge: Cambridge University Press. · Zbl 1031.65075
[11] Karlin, S., & Studden, W. J. (1966). Tchebycheff systems, with applications in analysis and statistics. New York: Wiley. · Zbl 0153.38902
[12] Kuhl, M. E., & Bhairgond, P. S. (2000). New frontiers in input modeling: nonparametric estimation of nonhomogeneous Poisson process using wavelets. In Proc. 2000 winter simulation conf., Orlando, FL (pp. 562–571).
[13] Kuhl, M. E., Damerdji, H., & Wilson, J. R. (1997). Estimating and simulating Poisson processes with trends or asymmetric cyclic effects. In S. Andradoóttir, K. J. Healy, D. H. Withers, & B. L. Nelson (Eds.), Proceedings of the 1997 winter simulation conference.
[14] Kuhl, M. E., Sumant, S. G., & Wilson, J. R. (2006). An automated multiresolution procedure for modeling complex arrival processes. INFORMS Journal on Computing, 18(1), 3–18. · Zbl 1241.62133 · doi:10.1287/ijoc.1040.0113
[15] Motzkin, T. (1968). The arithmetic-geometric inequalities. In O. Sisha (Ed.), Inequalities: proc. symp. Wright-Patterson AFB (pp. 205–224).
[16] Nesterov, Y. (2000). Squared functional systems and optimization problems. In J. B. G. Frenk, C. Roos, T. Terlaky, & S. Zahng (Eds.), High performance optimization (pp. 405–440). Dordrecht: Kluwer Academic. · Zbl 0958.90090
[17] Nesterov, Y., & Nemirovski, A. (1994). Interior point polynomial methods in convex programming: theory and applications. Philadelphia: SIAM.
[18] Nocedal, J., & Waltz, R. A. (2003). KNITRO user’s manual (Technical Report OTC 2003/05). Optimization Technology Center, Northwestern University, Evanston, IL.
[19] Papp, D. (2011). Optimization models for shape constrained function estimation problems involving nonnegative polynomials and their restrictions. Ph.D. thesis, RUTCOR, Rutgers–State University of New Jersey, New Brunswick, NJ, USA.
[20] Papp, D., & Alizadeh, F. (2008). Linear and second order approaches to statistical estimation problems (Technical Report RRR 13-08). Rutgers Center for Operations Research, Rutgers University.
[21] Papp, D., & Alizadeh, F. (2011a). Multivariate arrival rate estimation by sum-of-squares polynomial splines and semidefinite programming (Technical Report RRR 5-11). Rutgers Center for Operations Research, Rutgers University.
[22] Papp, D., & Alizadeh, F. (2011b). Multivariate arrival rate estimation using semidefinite programming. In Proceedings of the 2011 winter simulation conference. · Zbl 1274.90255
[23] Papp, D., & Alizadeh, F. (2011c). Semidefinite characterization of sum-of-squares cones in algebras (Technical Report RRR 14-11). Rutgers Center for Operations Research, Rutgers University.
[24] Ruszczyński, A. (1995). On convergence of an augmented Lagrangian decomposition method for sparse convex optimization. Mathematics of Operations Research, 20, 634–656. doi: 10.1287/moor.20.3.634 . · Zbl 0845.90098 · doi:10.1287/moor.20.3.634
[25] Shao, J. (1993). Linear model selection by cross-validation. Journal of the American Statistical Association, 88, 486–494. · Zbl 0773.62051 · doi:10.1080/01621459.1993.10476299
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.