We consider the numerical approximation of an optimal control problem for an elliptic Partial Differential Equation (PDE) with random coefficients. Specifically, the control function is a deterministic, distributed forcing term that minimizes the expected squared L2 misfit between the state (i.e. solution to the PDE) and a target function, subject to a regularization for well posedness. For the numerical treatment of this risk-averse Optimal Control Problem (OCP) we consider a Finite Element discretization of the underlying PDE, a Monte Carlo sampling method, and gradient-type iterations to obtain the approximate optimal control. We provide full error and complexity analyses of the proposed numerical schemes. In particular we investigate the complexity of a conjugate gradient method applied to the fully discretized OCP (so called Sample Average Approximation), in which the Finite Element discretization and Monte Carlo sample are chosen in advance and kept fixed over the iterations. This is compared with a Stochastic Gradient method on a fixed or varying Finite Element discretization, in which the expectation in the computation of the steepest descent direction is approximated by Monte Carlo estimators, independent across iterations, with small sample sizes. We show in particular that the second strategy results in an improved computational complexity. The theoretical error estimates and complexity results are confirmed by numerical experiments.
Accepté le :
Publié le :
DOI : 10.1051/m2an/2021025
Keywords: PDE constrained optimization, risk-averse optimal control, optimization under uncertainty, PDE with random coefficients, sample average approximation, stochastic approximation, stochastic gradient, Monte Carlo
@article{M2AN_2021__55_4_1599_0,
author = {Martin, Matthieu and Krumscheid, Sebastian and Nobile, Fabio},
title = {Complexity {Analysis} of stochastic gradient methods for {PDE-constrained} optimal {Control} {Problems} with uncertain parameters},
journal = {ESAIM: Mathematical Modelling and Numerical Analysis },
pages = {1599--1633},
year = {2021},
publisher = {EDP-Sciences},
volume = {55},
number = {4},
doi = {10.1051/m2an/2021025},
mrnumber = {4294188},
language = {en},
url = {https://www.numdam.org/articles/10.1051/m2an/2021025/}
}
TY - JOUR AU - Martin, Matthieu AU - Krumscheid, Sebastian AU - Nobile, Fabio TI - Complexity Analysis of stochastic gradient methods for PDE-constrained optimal Control Problems with uncertain parameters JO - ESAIM: Mathematical Modelling and Numerical Analysis PY - 2021 SP - 1599 EP - 1633 VL - 55 IS - 4 PB - EDP-Sciences UR - https://www.numdam.org/articles/10.1051/m2an/2021025/ DO - 10.1051/m2an/2021025 LA - en ID - M2AN_2021__55_4_1599_0 ER -
%0 Journal Article %A Martin, Matthieu %A Krumscheid, Sebastian %A Nobile, Fabio %T Complexity Analysis of stochastic gradient methods for PDE-constrained optimal Control Problems with uncertain parameters %J ESAIM: Mathematical Modelling and Numerical Analysis %D 2021 %P 1599-1633 %V 55 %N 4 %I EDP-Sciences %U https://www.numdam.org/articles/10.1051/m2an/2021025/ %R 10.1051/m2an/2021025 %G en %F M2AN_2021__55_4_1599_0
Martin, Matthieu; Krumscheid, Sebastian; Nobile, Fabio. Complexity Analysis of stochastic gradient methods for PDE-constrained optimal Control Problems with uncertain parameters. ESAIM: Mathematical Modelling and Numerical Analysis , Tome 55 (2021) no. 4, pp. 1599-1633. doi: 10.1051/m2an/2021025
[1] , and , Multilevel Monte Carlo analysis for optimal control of elliptic PDEs with random coefficients. SIAM/ASA J. Uncertain. Quantif. 5 (2017) 466–492. | MR | DOI
[2] , , and , Mean-variance risk-averse optimal control of systems governed by PDEs with random parameter fields using quadratic approximations. SIAM/ASA J. Uncertain. Quantif. 5 (2017) 1166–1192. | MR | DOI
[3] , and , Galerkin finite element approximations of stochastic elliptic partial differential equations. SIAM J. Numer. Anal. 42 (2004) 800–825. | MR | Zbl | DOI
[4] , and , A stochastic collocation method for elliptic partial differential equations with random input data. SIAM review 52 (2010) 317–355. | MR | Zbl | DOI
[5] , and , Computing VaR and CVaR using stochastic approximation and adaptive unconstrained importance sampling. Monte Carlo Methods Appl. 15 (2009) 173–210. | MR | Zbl | DOI
[6] , and , Block-diagonal preconditioning for optimal control problems constrained by PDEs with uncertain inputs. SIAM J. Matrix Anal. Appl. 37 (2016) 491–518. | MR | DOI
[7] and , A POD framework to determine robust controls in PDE optimization. Comput. Vis. Sci. 14 (2011) 91–103. | MR | Zbl | DOI
[8] and , Computational optimization of systems governed by partial differential equations. Soc. Ind. Appl. Math. (SIAM). Philadelphia, PA (2010). | MR | Zbl
[9] , , and , On the treatment of distributed uncertainties in PDE-constrained optimization. GAMM-Mitteilungen 33 (2010) 230–246. | MR | Zbl | DOI
[10] and , Weighted reduced basis method for stochastic optimal control problems with elliptic PDE constraint. SIAM/ASA J. Uncertain. Quantif. 2 (2014) 364–396. | MR | Zbl | DOI
[11] and , Approximation of high dimensional parametric PDEs. Acta Numerica 24 (2015) 1–159. | MR | DOI
[12] , , and , Better mini-batch algorithms via accelerated gradient methods, edited by , , , and , In: Advances in Neural Information Processing Systems 24, Curran Associates, Inc. (2011) 1647–1655.
[13] , Numerical PDE-Constrained optimization, SpringerBriefs in Optimization. Springer, Cham (2015). | MR | Zbl
[14] and , Averaged least-mean-squares: Bias-variance trade-offs and optimal sampling distributions. Artificial Intelligence and Statistics 38 (2015) 205–213.
[15] , , and , Optimal distributed online prediction using mini-batches. J. Mach. Learn. Res. 13 (2012) 165–202. | MR | Zbl
[16] and , Nonparametric stochastic approximation with large step-sizes. The Ann. Stat. 44 (2016) 1363–1399. | MR | DOI
[17] and , Efficient online and batch learning using forward backward splitting. J. Mach. Learn. Res. 10 (2009) 2899–2934. | MR | Zbl
[18] , Partial differential equations, Graduate studies in mathematics. Am. Math. Soc. (1998). | MR | Zbl
[19] and , From averaging to acceleration, there is only a step-size. Conference on Learning Theory (2015) 658–695.
[20] , , A stochastic gradient method with mesh refinement for PDE constrained optimization under uncertainty. SIAM J. Sci. Comput. 42 (2020) A2750–A2772. | MR | DOI
[21] , Elliptic problems in nonsmooth domains, Reprint of the 1985 original [MR0775683], With a foreword by . Classics in Applied Mathematics, Society for Industrial and Applied Mathematics (SIAM). Philadelphia, PA, 69 (2011). | MR | Zbl
[22] , and , Error estimates of stochastic optimal Neumann boundary control problems. SIAM J. Numer. Anal. 49 (2011) 1532–1552. | MR | Zbl | DOI
[23] , and , Stochastic finite element methods for partial differential equations with random input data. Acta Numerica 23 (2014) 521–650. | MR | DOI
[24] , , , and , A quasi-Monte Carlo method for optimal control under uncertainty. SIAM-ASA J. Uncertain. Quantif. 9 (2021) 354–383. | MR | DOI
[25] , Large-scale PDE-constrained optimization in applications. Springer-Verlag, Berlin (2010). | MR | Zbl | DOI
[26] , New development in freefem++. J. Numer. Math. 20 (2012) 251–265. | MR | Zbl | DOI
[27] , , and , Optimization with PDE Constraints, Mathematical Modelling: Theory and Applications 23. Springer, New York (2009). | MR | Zbl
[28] , An Approach for the Adaptive Solution of Optimization Problems Governed by Partial Differential Equations with Uncertain Coefficients, ProQuest LLC, Ann Arbor, MI, Ph.D. thesis. Rice University (2012). | MR
[29] , , and , A trust-region algorithm with adaptive stochastic collocation for PDE optimization under uncertainty. SIAM J. Sci. Comput. 35 (2013) A1847–A1879. | MR | Zbl | DOI
[30] and , Risk-averse PDE-constrained optimization using the conditional value-at-risk. SIAM J. Optim. 26 (2016) 365–396. | MR | DOI
[31] and , Existence and optimality conditions for risk-averse PDE-constrained optimization. SIAM/ASA J. Uncertain. Quantif. 6 (2018) 787–815. | MR | DOI
[32] and , Analytic regularity and GPC approximation for control problems constrained by linear parametric elliptic and parabolic PDEs. SIAM J. Control Optim. 51 (2013) 2442–2471. | MR | Zbl | DOI
[33] and , Stochastic approximation algorithms and applications, Applications of Mathematics (New York). Springer-Verlag, New York (1997). | MR | Zbl | DOI
[34] , , , , , , and (eds.), Trends in PDE constrained optimization. Birkhäuser/Springer, Cham (2014). | MR | Zbl | DOI
[35] , and , An introduction to computational stochastic PDEs, Cambridge Texts in Applied Mathematics. Cambridge University Press (2014). | MR | Zbl
[36] , Stochastic approximation methods for PDE constrained optimal control problems with uncertain parameters, Ph.D. thesis, École Polytechnique Fédérale de Lausanne, Thesis 7233 (2019).
[37] , , PDE-Constrained Optimal Control Problems with Uncertain Parameters using SAGA. SIAM-ASA J. Uncertain. Quantif. 9 (2021) 979–1012. | MR | DOI
[38] , and , A multilevel stochastic gradient method for PDE-constrained optimal control problems with uncertain parameters. Preprint arXiv: 1912.11900 (2019).
[39] , , and , Robust stochastic approximation approach to stochastic programming. SIAM J. Optim. 19 (2009) 1574–1609. | MR | Zbl | DOI
[40] and , Acceleration of stochastic approximation by averaging. SIAM J. Control Optim. 30 (1992) 838–855. | MR | Zbl | DOI
[41] and , A stochastic approximation method. Ann. Math. Statist. 22 (1951) 400–407. | MR | Zbl | DOI
[42] and , Conditional value-at-risk for general loss distributions. J. Bank. Financ. 26 (2002) 1443–1471. | DOI
[43] and , Optimal control with stochastic PDE constraints and uncertain controls. Comput. Methods Appl. Mech. Engrg. 213/216 (2012) 152–167. | MR | Zbl | DOI
[44] , Efficient estimations from a slowly convergent Robbins-Monro process. Tech. Report Cornell Uni. Oper. Res. Ind. Eng. (1988).
[45] , and , Efficient shape optimization for certain and uncertain aerodynamic design. Computers & Fluids. 10th ICFD Conference Series on Numerical Methods for Fluid Dynamics (ICFD 2010) 46 (2011) 78–87. | MR | Zbl
[46] , and , Minimizing finite sums with the stochastic average gradient. Math. Program. 162 (2017) 83–112. | MR | DOI
[47] , and , Lectures on stochastic programming, 2nd ed., Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA; Mathematical Optimization Society, Philadelphia, PA, Modeling and theory (2014). | MR | Zbl
[48] , , and , Stochastic collocation for optimal control problems with stochastic PDE constraints. SIAM J. Control Optim. 50 (2012) 2659–2682. | MR | Zbl | DOI
[49] and , Robust optimization of PDEs with random coefficients using a multilevel Monte Carlo method. SIAM/ASA J. Uncertain. Quantif. 7 (2019) 174–202. | MR | DOI
[50] , Probability with martingales. Cambridge mathematical textbooks. Cambridge University Press (1991). | MR | Zbl
Cité par Sources :
