Skip to main content
main-content

Tipp

Weitere Kapitel dieses Buchs durch Wischen aufrufen

2022 | OriginalPaper | Buchkapitel

Codifferentials and Quasidifferentials of the Expectation of Nonsmooth Random Integrands and Two-Stage Stochastic Programming

verfasst von: M. V. Dolgopolik

Erschienen in: High-Dimensional Optimization and Probability

Verlag: Springer International Publishing

share
TEILEN

Abstract

This work is devoted to an analysis of exact penalty functions and optimality conditions for nonsmooth two-stage stochastic programming problems. To this end, we first study the co/quasidifferentiability of the expectation of nonsmooth random integrands and obtain explicit formulae for its co and quasidifferential under some natural assumptions on the integrand. Then, we analyse exact penalty functions for a variational reformulation of two-stage stochastic programming problems and obtain sufficient conditions for the global exactness of these functions with two different penalty terms. In the end of the chapter, we combine our results on the co/quasidifferentiability of the expectation of nonsmooth random integrands and exact penalty functions to derive optimality conditions for nonsmooth two-stage stochastic programming problems in terms of codifferentials.
Literatur
1.
Zurück zum Zitat J.P. Aubin, H. Frankowska, Set-Valued Analysis (Birkhäuser, Boston, 1990) MATH J.P. Aubin, H. Frankowska, Set-Valued Analysis (Birkhäuser, Boston, 1990) MATH
2.
Zurück zum Zitat G. Barbarosoǧlu, Y. Arda, A two-stage stochastic programming framework for transportation planning in disaster response. J. Oper. Res. Soc. 55, 43–53 (2004) G. Barbarosoǧlu, Y. Arda, A two-stage stochastic programming framework for transportation planning in disaster response. J. Oper. Res. Soc. 55, 43–53 (2004)
3.
Zurück zum Zitat J.R. Birge, F. Louveaux, Introduction to Stochastic Programming (Springer, New York, 2011) MATHCrossRef J.R. Birge, F. Louveaux, Introduction to Stochastic Programming (Springer, New York, 2011) MATHCrossRef
5.
Zurück zum Zitat J.V. Burke, The subdifferential of measurable composite max integrands and smoothing approximation. Math. Program. 181, 229–264 (2020) MathSciNetMATHCrossRef J.V. Burke, The subdifferential of measurable composite max integrands and smoothing approximation. Math. Program. 181, 229–264 (2020) MathSciNetMATHCrossRef
6.
Zurück zum Zitat X. Chen, M. Fukushima, Expected residual minimization method for stochastic linear complementarity problems. Math. Oper. Res. 30, 916–638 (2005) MathSciNetMATHCrossRef X. Chen, M. Fukushima, Expected residual minimization method for stochastic linear complementarity problems. Math. Oper. Res. 30, 916–638 (2005) MathSciNetMATHCrossRef
7.
Zurück zum Zitat X. Chen, R.J.-B. Wets, Y. Zhang, Stochastic variational inequalities: residual minimization smoothing sample average approximations. SIAM J. Optim. 22, 649–673 (2012) MathSciNetMATHCrossRef X. Chen, R.J.-B. Wets, Y. Zhang, Stochastic variational inequalities: residual minimization smoothing sample average approximations. SIAM J. Optim. 22, 649–673 (2012) MathSciNetMATHCrossRef
8.
Zurück zum Zitat S. Dempe, A. Zemkoho (eds.) Bilevel Optimization. Advances and Next Challenges (Springer, Cham, 2020) MATH S. Dempe, A. Zemkoho (eds.) Bilevel Optimization. Advances and Next Challenges (Springer, Cham, 2020) MATH
9.
Zurück zum Zitat S. Dempe, V. Kalashnikov, G.A. Pérez-Valdés, N. Kalashnykova (eds.), Bilevel Programming Problems. Theory, Algorithms and Applications to Energy Networks (Springer, Berlin, 2015) MATH S. Dempe, V. Kalashnikov, G.A. Pérez-Valdés, N. Kalashnykova (eds.), Bilevel Programming Problems. Theory, Algorithms and Applications to Energy Networks (Springer, Berlin, 2015) MATH
11.
Zurück zum Zitat V.F. Demyanov, Nonsmooth optimization, in Nonlinear Optimization, ed. by G. Di Pillo, F. Schoen. Lecture Notes in Mathematics, vol. 1989 (Springer, Berlin, 2010), pp. 55–163 V.F. Demyanov, Nonsmooth optimization, in Nonlinear Optimization, ed. by G. Di Pillo, F. Schoen. Lecture Notes in Mathematics, vol. 1989 (Springer, Berlin, 2010), pp. 55–163
12.
Zurück zum Zitat V.F. Demyanov, L.C.W. Dixon (eds.) Quasidifferential Calculus (Springer, Berlin, 1986) MATH V.F. Demyanov, L.C.W. Dixon (eds.) Quasidifferential Calculus (Springer, Berlin, 1986) MATH
13.
Zurück zum Zitat V.F. Dem’yanov, V.N. Malozemov, Introduction to Minimax (Dover Publications, New York, 2014) MATH V.F. Dem’yanov, V.N. Malozemov, Introduction to Minimax (Dover Publications, New York, 2014) MATH
14.
Zurück zum Zitat V.F. Demyanov, A.M. Rubinov, Constructive Nonsmooth Analysis (Peter Lang, Frankfurt am Main, 1995) MATH V.F. Demyanov, A.M. Rubinov, Constructive Nonsmooth Analysis (Peter Lang, Frankfurt am Main, 1995) MATH
15.
Zurück zum Zitat V.F. Demyanov, A.M. Rubinov (eds.) Quasidifferentiability and Related Topics (Kluwer Academic Publishers, Dordrecht, 2000) MATH V.F. Demyanov, A.M. Rubinov (eds.) Quasidifferentiability and Related Topics (Kluwer Academic Publishers, Dordrecht, 2000) MATH
16.
18.
Zurück zum Zitat M.V. Dolgopolik, Nonsmooth problems of calculus of variations via codifferentiation. ESAIM: Control Optim. Calc. Var. 20, 1153–1180 (2014) MathSciNetMATH M.V. Dolgopolik, Nonsmooth problems of calculus of variations via codifferentiation. ESAIM: Control Optim. Calc. Var. 20, 1153–1180 (2014) MathSciNetMATH
21.
22.
Zurück zum Zitat M.V. Dolgopolik, Constrained nonsmooth problems of the calculus of variations. ESAIM: Control, Optim. Calc. Var. 27, 1–35 (2021) M.V. Dolgopolik, Constrained nonsmooth problems of the calculus of variations. ESAIM: Control, Optim. Calc. Var. 27, 1–35 (2021)
23.
Zurück zum Zitat M.V. Dolgopolik, A. Fominyh, Exact penalty functions for optimal control problems I: main theorem and free-endpoint problems. Optim. Control Appl. Meth. 40, 1018–1044 (2019) MathSciNetMATHCrossRef M.V. Dolgopolik, A. Fominyh, Exact penalty functions for optimal control problems I: main theorem and free-endpoint problems. Optim. Control Appl. Meth. 40, 1018–1044 (2019) MathSciNetMATHCrossRef
24.
Zurück zum Zitat C.I. Fábián, Z. Szőke, Solving two-stage stochastic programming problems with level decomposition. Comput. Manag. Sci. 4, 313–353 (2007) C.I. Fábián, Z. Szőke, Solving two-stage stochastic programming problems with level decomposition. Comput. Manag. Sci. 4, 313–353 (2007)
25.
26.
Zurück zum Zitat E. Grass, K. Fischer, Two-stage stochastic programming in disaster management: a literature survey. Surv. Oper. Res. Manag. Sci. 21, 85–100 (2016) MathSciNet E. Grass, K. Fischer, Two-stage stochastic programming in disaster management: a literature survey. Surv. Oper. Res. Manag. Sci. 21, 85–100 (2016) MathSciNet
27.
Zurück zum Zitat J.B. Hiriart-Urruty, Conditions nécessaires d’optimalité pour un programme stochastique avec recours. SIAM J. Control Optim. 16, 317–329 (1978) MathSciNetMATHCrossRef J.B. Hiriart-Urruty, Conditions nécessaires d’optimalité pour un programme stochastique avec recours. SIAM J. Control Optim. 16, 317–329 (1978) MathSciNetMATHCrossRef
28.
Zurück zum Zitat G.H. Huang, D.P. Loucks, An inexact two-stage stochastic programming model for water resources management under uncertainty. Civ. Eng. Environ. Syst. 17, 95–118 (2000) CrossRef G.H. Huang, D.P. Loucks, An inexact two-stage stochastic programming model for water resources management under uncertainty. Civ. Eng. Environ. Syst. 17, 95–118 (2000) CrossRef
29.
Zurück zum Zitat H. Leövey, W. Römisch, Quasi-Monte Carlo methods for linear two-stage stochastic programming problems. Math. Program. 151, 315–345 (2015) MathSciNetMATHCrossRef H. Leövey, W. Römisch, Quasi-Monte Carlo methods for linear two-stage stochastic programming problems. Math. Program. 151, 315–345 (2015) MathSciNetMATHCrossRef
31.
Zurück zum Zitat C. Liu, Y. Fan, F. Ordóñez, A two-stage stochastic programming model for transportation network protection. Comput. Oper. Res. 36, 1582–1590 (2009) MathSciNetMATHCrossRef C. Liu, Y. Fan, F. Ordóñez, A two-stage stochastic programming model for transportation network protection. Comput. Oper. Res. 36, 1582–1590 (2009) MathSciNetMATHCrossRef
32.
Zurück zum Zitat A. Nemirovski, A. Juditsky, G. Lan, A. Shapiro, Robust stochastic approximation approach to stochastic programming. SIAM J. Optim. 19, 1574–1609 (2009) MathSciNetMATHCrossRef A. Nemirovski, A. Juditsky, G. Lan, A. Shapiro, Robust stochastic approximation approach to stochastic programming. SIAM J. Optim. 19, 1574–1609 (2009) MathSciNetMATHCrossRef
33.
Zurück zum Zitat W. Oliveira, C. Sagastizábal, S. Scheimberg, Inexact bundle methods for two-stage stochastic programming. SIAM J. Optim. 21, 517–544 (2011) MathSciNetMATHCrossRef W. Oliveira, C. Sagastizábal, S. Scheimberg, Inexact bundle methods for two-stage stochastic programming. SIAM J. Optim. 21, 517–544 (2011) MathSciNetMATHCrossRef
34.
Zurück zum Zitat A.V. Orlov, On a solving bilevel D.C.-convex optimization problems, in Mathematical Optimization Theory and Operations Research. MOTOR 2020, ed. by Y. Kochetov, I. Bukadorov, T. Gruzdeva (Springer, Cham, 2020), pp. 179–191 CrossRef A.V. Orlov, On a solving bilevel D.C.-convex optimization problems, in Mathematical Optimization Theory and Operations Research. MOTOR 2020, ed. by Y. Kochetov, I. Bukadorov, T. Gruzdeva (Springer, Cham, 2020), pp. 179–191 CrossRef
35.
36.
Zurück zum Zitat R.T. Rockafellar, R.J.-B. Wets, On the interchange of subdifferentiation and conditional expectation for convex functions. Stochastics 7, 173–182 (1982) MathSciNetMATHCrossRef R.T. Rockafellar, R.J.-B. Wets, On the interchange of subdifferentiation and conditional expectation for convex functions. Stochastics 7, 173–182 (1982) MathSciNetMATHCrossRef
37.
38.
Zurück zum Zitat A. Rubinov, X. Yang, Lagrange-Type Functions in Constrained Non-Convex Optimization (Kluwer Academic Publishers, Boston, 2003) MATHCrossRef A. Rubinov, X. Yang, Lagrange-Type Functions in Constrained Non-Convex Optimization (Kluwer Academic Publishers, Boston, 2003) MATHCrossRef
39.
Zurück zum Zitat A. Shapiro, T.H. de Mello, A simulation-based approach to two-stage stochastic programming with recourse. Math. Program. 81, 301–325 (1998) MathSciNetMATH A. Shapiro, T.H. de Mello, A simulation-based approach to two-stage stochastic programming with recourse. Math. Program. 81, 301–325 (1998) MathSciNetMATH
40.
Zurück zum Zitat A. Shapiro, D. Dentcheva, A. Ruszczǹski, Lectures on Stochastic Programming: Modeling and Theory (SIAM, Philadelphia, 2014) A. Shapiro, D. Dentcheva, A. Ruszczǹski, Lectures on Stochastic Programming: Modeling and Theory (SIAM, Philadelphia, 2014)
42.
Zurück zum Zitat A.S. Strekalovsky, A.V. Orlov, Global search for bilevel optimization with quadratic data, in Bilevel Optimization, ed. by S. Dempe, A. Zemkoho (eds.) (Springer, Cham, 2020), pp. 313–334 MATHCrossRef A.S. Strekalovsky, A.V. Orlov, Global search for bilevel optimization with quadratic data, in Bilevel Optimization, ed. by S. Dempe, A. Zemkoho (eds.) (Springer, Cham, 2020), pp. 313–334 MATHCrossRef
43.
44.
Zurück zum Zitat A. Uderzo, A strong metric subregularity analysis of nonsmooth mappings via steepest displacement rate. J. Optim. Theory Appl. 171, 573–599 (2016) MathSciNetMATHCrossRef A. Uderzo, A strong metric subregularity analysis of nonsmooth mappings via steepest displacement rate. J. Optim. Theory Appl. 171, 573–599 (2016) MathSciNetMATHCrossRef
45.
Zurück zum Zitat S. Vogel, Necessary optimality conditions for two-stage stochastic programming problems. SIAM J. Optim. 16, 607–616 (1985) MathSciNetMATH S. Vogel, Necessary optimality conditions for two-stage stochastic programming problems. SIAM J. Optim. 16, 607–616 (1985) MathSciNetMATH
46.
Zurück zum Zitat H. Xu, J.J. Ye, Necessary optimality conditions for two-stage stochastic programs with equilibrium constraints. SIAM J. Optim. 20, 1685–1715 (2010) MathSciNetMATHCrossRef H. Xu, J.J. Ye, Necessary optimality conditions for two-stage stochastic programs with equilibrium constraints. SIAM J. Optim. 20, 1685–1715 (2010) MathSciNetMATHCrossRef
47.
Zurück zum Zitat H. Xu, D. Zhang, Smooth sample average approximation of stationary points in nonsmooth stochastic optimization and applications. Math. Program. 119, 371–401 (2009) MathSciNetMATHCrossRef H. Xu, D. Zhang, Smooth sample average approximation of stationary points in nonsmooth stochastic optimization and applications. Math. Program. 119, 371–401 (2009) MathSciNetMATHCrossRef
48.
49.
Zurück zum Zitat Z. Zhou, J. Zhang, P. Liu, Z. Li, M.C. Georgiadis, E.N. Pistikopoulos, A two-stage stochastic programming model for the optimal design of distributed energy systems. Appl. Energy 103, 135–144 (2013) CrossRef Z. Zhou, J. Zhang, P. Liu, Z. Li, M.C. Georgiadis, E.N. Pistikopoulos, A two-stage stochastic programming model for the optimal design of distributed energy systems. Appl. Energy 103, 135–144 (2013) CrossRef
Metadaten
Titel
Codifferentials and Quasidifferentials of the Expectation of Nonsmooth Random Integrands and Two-Stage Stochastic Programming
verfasst von
M. V. Dolgopolik
Copyright-Jahr
2022
DOI
https://doi.org/10.1007/978-3-031-00832-0_5

Stellenausschreibungen

Anzeige

Premium Partner