Asymptotic behavior of solutions: An application to stochastic NLP
Authors: 
Arnab Sur, John R. BirgeAuthors Info & Claims
Pages 281 - 306
Abstract
In this article we study the consistency of optimal and stationary (KKT) points of a stochastic non-linear optimization problem involving expectation functionals, when the underlying probability distribution associated with the random variable is weakly approximated by a sequence of random probability measures. The optimization model includes constraints with expectation functionals those are not captured in direct application of the previous results on optimality conditions exist in the literature. We first study the consistency of stationary points of a general NLP problem with convex and locally Lipschitz data and then apply those results to the stochastic NLP problem and stochastic minimax problem. Moreover, we derive an exponential bound for such approximations using a large deviation principle.
References
[1]
Andrews DWK Consistency in nonlinear econometric models: a generic uniform law of large numbers Econometrica 1987 55 1465-1471
[2]
Artstein Z and Wets RJ-B Consistency of minimizers and the SLLN for stochastic programs J. Convex Anal. 1995 2 1-17
[3]
Attouch, H., Wets, R.J.-B.: Approximation and convergence in nonlinear optimization. In: Nonlinear Programming (Madison, Wis., 1980), vol. 4, pp. 367–394. Academic Press, New York (1981)
[4]
Aumann RJ Integrals of set-valued functions J. Math. Anal. Appl. 1965 12 1-12
[5]
Bastin F, Cirillo C, and Toint P Convergence theory for nonconvex stochastic programming with an application to mixed logit Math. Program., Ser. B 2006 108 207-234
[6]
Bayraksan G and Morton D Assessing solution quality in stochastic programs Math. Program. 2006 108 495-514
[7]
Billingsley, P.: Convergence of Probability Measures. Wiley Series in Probability and Statistics: Probability and Statistics, 2nd edn. Wiley, New York (1999)
[8]
Birge JR and Qi LQ Subdifferential convergence in stochastic programs SIAM J. Optim. 1995 2 436-453
[9]
Birge JR and Wets RJ-B Designing approximation schemes for stochastic problems, in particular for stochastic programs with recourse Math. Program. Stud. 1986 27 54-102
[10]
Borwein JM and Vanderwerff JD Epigraphical and uniform convergence of convex functions Trans. AMS 1996 348 1617-1631
[11]
Clarke FH Optimization and Nonsmooth Analysis 1983 New York Wiley
[12]
Czarnecki M-O and Rifford L Approximation and regularization of Lipschitz functions: convergence of the gradients Trans. AMS 2006 358 4467-4520
[13]
Dai L, Chen CH, and Birge JR Convergence properties of two-stage stochastic programming J. Optim. Theory Appl. 2000 106 489-509
[14]
Dupačová J Minimax approach to stochastic linear programming and the moment problem (in Czech) Ekon.-Matemat. Obzor. 1977 3 279-307
[15]
Dupačová J Stability and sensitivity analysis for stochastic programming Ann. Oper. Res. 1990 27 115-142
[16]
Dupačová J Uncertainties in minimax stochastic programs Optimization 2011 60 1235-1250
[17]
Dupac̆ová J and Wets RJ-B Asymptotic behaviour of statistical estimators and of optimal solutions of stochastic optimization problems Ann. Stat. 1988 16 1517-1549
[18]
Hess C Epi-convergence of sequences of normal integrands and strong consistency of the maximum likelihood estimator Ann. Stat. 1996 24 1298-1315
[19]
Hess C and Seri R Generic consistency for approximate stochastic programming and statistical problems SIAM J. Optim. 2019 29 290-317
[20]
Higle JL and Sen S On the convergence of algorithms with implications for stochastic and nondifferentiable optimization Math. Oper. Res. 1992 17 112-131
[21]
Homem-de-Mello T On rates of convergence for stochastic optimization problems under non-independent and identically distributed sampling SIAM J. Optim. 2008 19 524-551
[22]
Homem-de-Mello T and Bayraksan G Monte Carlo sampling-based methods for stochastic optimization Surv. Oper. Res. Manag. Sci. 2014 19 56-85
[23]
Huber, P.J.: The behaviour of maximum likelihood estimates under non-constant conditions. In: Proc. 5th Berkeley Symp. Math. Statist. Probab., vol. 1, pp. 221–233. University of California Press (1949)
[24]
Kall P Approximation to optimization problems: an elementary review Math. Oper. Res. 1986 11 9-18
[25]
Kall P et al. Guddat J et al. Stochastic programming with recourse: upper bounds and moment problems–a review Advances in Mathematical Optimization 1988 Berlin Akademie 86-103
[26]
Kaniovski YM, King AJ, and Wets RJ-B Probabilistic bounds (via large deviations) for the solutions of stochastic programming problems Ann. Oper. Res. 1995 56 189-208
[27]
Kaňková V Stability in the stochastic programming Kybernetika 1978 14 339-349
[28]
King AJ and Rockafellar RT Asymptotic theory for solutions in statistical estimation and stochastic programming Math. Oper. Res. 1993 18 148-162
[29]
Merkovsky RR and Ward DE General constraint qualifications in nondifferentiable programming Math. Program. 1990 47 389-405
[30]
Newey WK Semiparamertic efficiency bounds J. Appl. Econom. 1990 5 99-135
[31]
Newey WK Uniform convergence in probability and stochastic equicontinuity Econometrica 1991 59 1161-1167
[32]
Pflug, G.: Stochastic optimization and statistical inference. In: Ruszczyński, A., Shapiro, A. (eds.) Stochastic Programming. Handbooks in Operations Research and Management Science, vol. 10, pp. 427–482, Chapter 7. Elsevier, Amsterdam (2003)
[33]
Pflug G, Ruszczyński A, and Schultz R On the Glivenko-Cantelli problem in stochastic programming: linear recourse and extensions Math. Oper. Res. 1998 23 204-220
[34]
Pflug G and Wozabal D Ambiguity in portfolio selection Quant. Finance 2007 7 435-442
[35]
Polak, E.: Optimization, Algorithms and Consistent Approximations. Applied Mathematical Sciences, vol. 124. Springer, New York (1997)
[36]
Rassoul-Agha, F., Seppäläinen, T.: A course on large deviations with an introduction to Gibbs measures. Graduate Studies in Mathematics, vol. 162. American Mathematical Society, Providence (2015)
[37]
Riis M and Andersen KA Applying the minimax criterion in stochastic recourse programs Eur. J. Oper. Res. 2005 165 569-584
[38]
Robinson SM Analysis of sample-path optimization Math. Oper. Res. 1996 21 513-528
[39]
Rockafellar, R.T., Wets, R.J.-B.: Variational Analysis. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 317. Springer, Berlin (1998)
[40]
Römisch, W.: Stability of stochastic programming problems. In: Ruszczyński, A., Shapiro, A. (eds.) Stochastic Programming. Handbooks in Operations Research and Management Science, vol. 10, pp. 483–554, Chapter 8. Elsevier, Amsterdam (2003)
[41]
Römisch W and Schultz R Distribution sensitivity in stochastic programming Math. Program. 1991 50 197-226
[42]
Shapiro A Asymptotic properties of statistical estimators in stochastic programming Ann. Stat. 1989 17 841-858
[43]
Shapiro A Asymptotic analysis of stochastic programs Ann. Oper. Res. 1991 30 169-186
[44]
Shapiro A Asymptotic behavior of optimal solutions in stochastic programming Math. Oper. Res. 1993 18 829-845
[45]
Shapiro A Simulation-based optimization–convergence analysis and statistical inference Stoch. Models 1996 12 425-454
[46]
Shapiro A and Homem-de-Mello T On the rate of convergence of optimal solutions of Monte Carlo approximations of stochastic programs SIAM J. Optim. 2000 11 70-86
[47]
Shapiro, A.: Monte Carlo sampling methods. In: Ruszczyński, A., Shapiro, A. (eds.) Stochastic Programming. Handbooks in Operations Research and Management Science, vol. 10, pp. 353–425, Chapter 6. Elsevier, Amsterdam (2003)
[48]
Shapiro A and Kleywegt A Minimax analysis of stochastic programs Optim. Methods Softw. 2002 17 532-542
[49]
Vogel S Stability results for stochastic programming problems Optimization 1988 19 269-288
[50]
Vogel S A stochastic approach to stability in stochastic programming J. Comput. Appl. Math. 1994 56 65-96
[51]
Vogel, S., Lachout, P.: On continuous convergence and epi-convergence of random functions, part I: theory an relations, part II: sufficient conditions and applications. Kybernetika 39, 75–98 and 99-118 (2003)
[52]
Wald A Note on the consistency of the maximum likelihood estimate Ann. Math. Stat. 1949 20 595-601
[53]
Wang W and Ahmed S Sample average approximation of expected value constrained stochastic programs Oper. Res. Lett. 2008 36 515-519
[54]
Wets RJ-B Modelling and solution strategies for unconstrained stochastic optimization problems Ann. Oper. Res. 1984 1 3-22
[55]
Wolfowitz J On Wald’s proof of the consistency of the maximum likelihood estimate Ann. Math. Stat. 1949 20 601-602
[56]
Zervos M On the epiconvergence of stochastic optimization problems Math. Oper. Res. 1999 24 495-508
Index Terms
- Asymptotic behavior of solutions: An application to stochastic NLP
Index terms have been assigned to the content through auto-classification.
Recommendations
Two-stage stochastic variational inequalities: an ERM-solution procedure
We propose a two-stage stochastic variational inequality model to deal with random variables in variational inequalities, and formulate this model as a two-stage stochastic programming with recourse by using an expected residual minimization solution ...
Stochastic Dynamic Cutting Plane for Multistage Stochastic Convex Programs
AbstractWe introduce Stochastic Dynamic Cutting Plane (StoDCuP), an extension of the Stochastic Dual Dynamic Programming (SDDP) algorithm to solve multistage stochastic convex optimization problems. At each iteration, the algorithm builds lower bounding ...
Periodical Multistage Stochastic Programs
In some applications the considered multistage stochastic programs have a periodical behavior. We show that in such cases it is possible to drastically reduce the number of stages by introducing a periodical analogue of the so-called Bellman equations for ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
© Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society 2020.
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 01 January 2022
Accepted: 13 August 2020
Received: 22 October 2016
Author Tags
Author Tags
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 20 Jan 2025