More Web Proxy on the site http://driver.im/

article

Sample-path optimization of convex stochastic performance functions

Authors:

Erica L. Plambeck,

Stephen M. Robinson,

Rajan SuriAuthors Info & Claims

Mathematical Programming: Series A and B, Volume 75, Issue 2

Pages 137 - 176

Published: 01 November 1996 Publication History

Abstract

In this paper we propose a method for optimizing convex performance functions in stochastic systems. These functions can include expected performance in static systems and steady-state performance in discrete-event dynamic systems; they may be nonsmooth. The method is closely related to retrospective simulation optimization; it appears to overcome some limitations of stochastic approximation, which is often applied to such problems. We explain the method and give computational results for two classes of problems: tandem production lines with up to 50 machines, and stochastic PERT (Program Evaluation and Review Technique) problems with up to 70 nodes and 110 arcs.

References

[1]

H. Attouch, Variational Convergence for Functions and Operators (Pitman, Boston, MA, 1984).

[2]

S.P. Bradley, A.C. Hax, and T.L. Magnanti, Applied Mathematical Programming (Addison-Wesley, Reading, MA, 1977).

[3]

R. Correa and C. Lemaréchal, "Convergence of some algorithms for convex minimization", Mathematical Programming 62 (1993) 261-275.

Digital Library

[4]

Y.M. Ermoliev and A.A. Gaivoronski, "Stochastic quasigradient methods for optimization of discrete event systems", Annals of Operations Research 39 (1992) 1-39.

Digital Library

[5]

B.-R. Fu, "Modeling and analysis of discrete tandem production lines using continuous flow models", Ph.D. Dissertation (Department of Industrial Engineering, University of Wisconsin-Madison (Madison, WI, 1996).

[6]

A.A. Gaivoronski, "Interactive program SQG-PC for solving stochastic programming problems on IBM PC/XT/AT compatibles, user guide", Working Paper WP-88-11, International Institute for Applied Systems Analysis (Laxenburg, Austria, 1988).

[7]

A.A. Gaivoronski, E. Messina, and A. Sciomachen, "A statistical generalized programming algorithm for stochastic optimization problems", Annals of Operations Research 58 (1995) 297-321.

[8]

A.A. Gaivoronski and L. Nazareth, "Combining generalized programming and sampling techniques for stochastic programs with recourse", in: G. Dantzig and P. Glynn, eds., Resource Planning under Uncertainty for Electric Power Systems (Stanford University, 1989).

[9]

S.B. Gershwin and I.C. Schick, "Continuous model of an unreliable two-stage material flow system with a finite interstage buffer", Technical Report LIDS-R-1039, Massachusetts Institute of Technology (Cambridge, MA, 1980).

[10]

S.B. Gershwin and I.C. Schick, "Modeling and analysis of three-stage transfer lines with unreliable machines and finite buffers", Operations Research 31 (1983) 354-380.

Digital Library

[11]

P. Glasserman, Gradient Estimation Via Perturbation Analysis (Kluwer Academic Publishers, Boston, MA, 1991).

[12]

P.W. Glynn, "Likelihood ratio gradient estimation: an overview", in:Proceedings of the 1987 Winter Simulation Conference (IEEE, Piscataway, NJ, 1987), pp. 366-374.

[13]

P.W. Glynn, "Optimization of stochastic systems via simulation", in:Proceedings of the 1989 Winter Simulation Conference (IEEE, Piscataway, NJ, 1989), pp. 90-105.

[14]

K. Healy and L.W. Schruben, "Retrospective simulation response optimization".Proceedings of the 1991 Winter Simulation Conference (1991) 901-907.

[15]

M. Held, P. Wolfe, and H.P. Crowder, "Validation of subgradient optimization", Mathematical Programming 6 (1974) 62-88.

Digital Library

[16]

J.L. Higle and S. Sen, "Statistical verification of optimality conditions for stochastic programs with recourse", Annals of Operations Research 30 (1991) pp. 215-240.

Digital Library

[17]

J.L. Higle and S. Sen, "Stochastic decomposition: an algorithm for two-stage linear programs with recourse", Mathematics of Operations Research 16 (1991) pp. 650-669.

[18]

Y.C. Ho, "Performance evaluation and perturbation analysis of discrete event dynamic systems", IEEE Transactions on Automatic Control 32 (1987) 563-572.

[19]

Y.C. Ho and X.R. Cao, Perturbation Analysis of Discrete Event Dynamic Systems (Kluwer Academic Publishers, Boston, MA 1991).

[20]

J.-Q. Hu, "Convexity of sample path performance and strong consistency of infinitesimal perturbation analysis estimates", IEEE Transactions on Automatic Control 37 (1992) 258-262.

[21]

P. Kall, "Approximation to optimization problems: an elementary review", Mathematics of Operations Research 11 (1986) 9-18.

Digital Library

[22]

K.C. Kiwiel, "Proximity control in bundle methods for convex nondifferentiable minimization", Mathematical Programming 46 (1990) 105-122.

Digital Library

[23]

P. L'Ecuyer, "Efficient and portable combined random number generators", Communications of the ACM 31 (1988) 742-774.

Digital Library

[24]

P. L'Ecuyer and P.W. Glynn, "Stochastic optimization by simulation: convergence proofs for the GI/G/1 queue in steady state", Management Science 40 (1994) 1562-1578.

Digital Library

[25]

P. L'Ecuyer, N. Giroux and P.W. Glynn, "Stochastic optimization by simulation: numerical experiments with the M/M/I queue in steady state", Management Science 40 (1994) 1245-1261.

Digital Library

[26]

D.G. Malcolm, J.H. Roseboom, C.E. Clark and W. Fazar, "Application of a technique for research and development program evaluation", Operations Research 7 (1959) 646-669.

Digital Library

[27]

M.S. Meketon, "A tutorial on optimization in simulations", Unpublished tutorial presented at the 1983 Winter Simulation Conference.

[28]

A. Mongalo and J. Lee, "A comparative study of methods for probabilistic project scheduling", Computers in Industrial Engineering 19 (1990) 505-509.

Digital Library

[29]

G.L. Nemhauser and L.A. Wolsey, Integer and Combinatorial Optimization (Wiley, New York, 1988).

Digital Library

[30]

E. Nummelin, "Regeneration in tandem queues", Advances in Applied Probability 13 (1981) 221-230.

[31]

E.L. Plambeck, B.-R. Fu, S.M. Robinson and R. Suri, "Throughput optimization in tandem production lines via nonsmooth programming", in: J. Schoen, ed., Proceedings of the 1993 Summer Computer Simulation Conference (Society for Computer Simulation. San Diego, CA, 1993) pp. 70-75.

[32]

H. Robbins and S. Monro, "A stochastic approximation method", Annals of Mathematical Statistics 22 (1951) 400-407.

[33]

S.M. Robinson, "Analysis of sample-path optimization", accepted by Mathematics of Operations Research.

[34]

R.T. Rockafellar, Convex Analysis (Princeton University Press, Princeton, NJ, 1970).

[35]

R.Y. Rubinstein and A. Shapiro, Discrete Event Systems: Sensitivity Analysis and Stochastic Optimization by the Score Function Method (Wiley, Chichester, 1993).

[36]

H. Schramm and J. Zowe, A version of the bundle idea for minimizing a nonsmooth function: conceptual idea, convergence analysis, numerical results, Technical Report 209, Mathematisches Institut, Universität Bayreuth (Bayreuth, Germany, 1990).

[37]

J.G. Shanthikumar and D.D. Yao, "Second-order stochastic properties in queueing systems", Proceedings of the IEEE 77 (1989) 162-170.

[38]

J.G. Shanthikumar and D.D. Yao, "Strong stochastic convexity: closure properties and applications", Journal of Applied Probability 28 (1991) 131-145.

[39]

A. Shapiro and Y. Wardi, "Nondifferentiability of the steady-state function in discrete event dynamic systems", IEEE Transactions on Automatic Control 39 (1994) 1707-1711.

[40]

R. Suri, "Perturbation analysis: the state of the art and research issues explained via the GI/G/l queue", Proceedings of the IEEE 77 (1989) 114-137.

[41]

R. Suri and B.-R. Fu. "On using continuous flow lines for performance estimation of discrete production lines", in: Proceedings of the 1991 Winter Simulation Conference (IEEE. Piscataway, NJ, 1991), pp. 968-977.

[42]

R. Suri and B.-R. Fu, "On using continuous flow lines to model discrete production lines", Discrete Event Dynamic Systems 4 (1994) 129-169.

[43]

R. Suri and B.-R. Fu, "Using continuous flow models to enable rapid analysis and optimization of discrete production lines--a progress report", in: Proceedings of the 19th Annual NSF Grantees Conference on Design and Manufacturing Systems Research (Charlotte, NC. 1993), pp. 1229-1238.

[44]

R. Suri and Y.T. Leung, "Single run optimization of discrete event simulations--an empirical study using the M/M/l queue", IIE Transactions 34 (1989) 35-49.

[45]

R. Suri and M. Zazanis, "Perturbation analysis gives strongly consistent sensitivity estimates for the M/G/1 queue", Management Science 34 (1988) 39-64.

Digital Library

[46]

R.M. Van Slyke, "Monte Carlo Methods and the PERT problem", Operations Research 11 (1963) 839-860.

Digital Library

[47]

R.M. Van Slyke and R.J.-B. Wets, "L-shaped linear programs with applications to optimal control and stochastic programming", SIAM Journal on Applied Mathematics 17 (1969) 638-663.

[48]

S.W. Wallace, "Bounding the expected time-cost curve for a stochastic PERT network from below", Operations Research Letters 8 (1989) 89-94.

Digital Library

[49]

K.C. Wei, Q.Q. Tsao and N.C. Otto, "Determining buffer size requirements using stochastic approximation methods", Technical Report SR-89-73, Manufacturing Systems Department. Ford Motor Company, Dearborn, MI, 1989).

[50]

R.D. Wollmer, "Critical path planning under uncertainty", Mathematical Programming Study 25 (1985) 164-171.

[51]

J. Zowe, "The BT-algorithm for minimizing a nonsmooth functional subject to linear constraints", in: F.H. Clarke et al., eds., Nonsmooth Optimization and Related Topics (Plenum Press, New York, 1989).

Cited By

Eckman DPlumlee MNelson B(2022)Plausible Screening Using Functional Properties for Simulations with Large Solution SpacesOperations Research10.1287/opre.2021.220670:6(3473-3489)Online publication date: 1-Nov-2022
https://dl.acm.org/doi/10.1287/opre.2021.2206
Yang HMorton D(2022)Optimal crashing of an activity network with disruptionsMathematical Programming: Series A and B10.1007/s10107-021-01670-x194:1-2(1113-1162)Online publication date: 1-Jul-2022
https://dl.acm.org/doi/10.1007/s10107-021-01670-x
Eckman DPlumlee MNelson B(2021)Flat chance!Proceedings of the Winter Simulation Conference10.5555/3522802.3523013(1-12)Online publication date: 13-Dec-2021
https://dl.acm.org/doi/10.5555/3522802.3523013
Show More Cited By

Index Terms

Sample-path optimization of convex stochastic performance functions
1. Mathematics of computing
2. Theory of computation
  1. Design and analysis of algorithms
    1. Mathematical optimization
  2. Models of computation
    1. Probabilistic computation

Recommendations

Optimal Threshold Levels in Stochastic Fluid Models via Simulation-based Optimization

A number of important problems in production and inventory control involve optimization of multiple threshold levels or hedging points. We address the problem of finding such levels in a stochastic system whose dynamics can be modelled using generalized ...
Stochastic Block Mirror Descent Methods for Nonsmooth and Stochastic Optimization

In this paper, we present a new stochastic algorithm, namely, the stochastic block mirror descent (SBMD) method for solving large-scale nonsmooth and stochastic optimization problems. The basic idea of this algorithm is to incorporate block coordinate ...
Markov Decision Processes with Sample Path Constraints: The Communicating Case

We consider time-average Markov Decision Processes MDPs, which accumulate a reward and cost at each decision epoch. A policy meets the sample-path constraint if the time-average cost is below a specified value with probability one. The optimization ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Mathematical Programming: Series A and B

Mathematical Programming: Series A and B Volume 75, Issue 2

November 1996

234 pages

ISSN:0025-5610

Issue’s Table of Contents

Copyright © Copyright © 1996 The Mathematical Programming Society, Inc.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 November 1996

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

36
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 01 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Eckman DPlumlee MNelson B(2022)Plausible Screening Using Functional Properties for Simulations with Large Solution SpacesOperations Research10.1287/opre.2021.220670:6(3473-3489)Online publication date: 1-Nov-2022
https://dl.acm.org/doi/10.1287/opre.2021.2206
Yang HMorton D(2022)Optimal crashing of an activity network with disruptionsMathematical Programming: Series A and B10.1007/s10107-021-01670-x194:1-2(1113-1162)Online publication date: 1-Jul-2022
https://dl.acm.org/doi/10.1007/s10107-021-01670-x
Eckman DPlumlee MNelson B(2021)Flat chance!Proceedings of the Winter Simulation Conference10.5555/3522802.3523013(1-12)Online publication date: 13-Dec-2021
https://dl.acm.org/doi/10.5555/3522802.3523013
Fu MHenderson S(2017)History of seeking better solutions, aka simulation optimizationProceedings of the 2017 Winter Simulation Conference10.5555/3242181.3242192(1-27)Online publication date: 3-Dec-2017
https://dl.acm.org/doi/10.5555/3242181.3242192
Razaviyayn MSanjabi MLuo Z(2016)A Stochastic Successive Minimization Method for Nonsmooth Nonconvex Optimization with Applications to Transceiver Design in Wireless Communication NetworksMathematical Programming: Series A and B10.1007/s10107-016-1021-7157:2(515-545)Online publication date: 1-Jun-2016
https://dl.acm.org/doi/10.1007/s10107-016-1021-7
Pedrielli GMatta AAlfieri A(2015)Discrete event optimizationProceedings of the 2015 Winter Simulation Conference10.5555/2888619.2889098(3557-3568)Online publication date: 6-Dec-2015
https://dl.acm.org/doi/10.5555/2888619.2889098
Higle JZhao L(2012)Adaptive and nonadaptive approaches to statistically based methods for solving stochastic linear programsComputational Optimization and Applications10.1007/s10589-010-9366-y51:2(509-532)Online publication date: 1-Mar-2012
https://dl.acm.org/doi/10.1007/s10589-010-9366-y
Ralph DXu H(2011)Convergence of Stationary Points of Sample Average Two-Stage Stochastic ProgramsMathematics of Operations Research10.1287/moor.1110.050636:3(568-592)Online publication date: 1-Aug-2011
https://dl.acm.org/doi/10.1287/moor.1110.0506
Pasupathy RKim S(2011)The stochastic root-finding problemACM Transactions on Modeling and Computer Simulation10.1145/1921598.192160321:3(1-23)Online publication date: 4-Feb-2011
https://dl.acm.org/doi/10.1145/1921598.1921603
Fliege JXu H(2011)Stochastic Multiobjective OptimizationJournal of Optimization Theory and Applications10.1007/s10957-011-9859-6151:1(135-162)Online publication date: 1-Oct-2011
https://dl.acm.org/doi/10.1007/s10957-011-9859-6
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents