# American Institute of Mathematical Sciences

2012, 2(3): 547-570. doi: 10.3934/naco.2012.2.547

## Error bounds for Euler approximation of linear-quadratic control problems with bang-bang solutions

 1 Institut für Angewandte Mathematik, Friedrich-Schiller-Universität Jena, 07740 Jena, Germany 2 Mathematisches Institut, Universität Bayreuth, 95440 Bayreuth, Germany, Germany 3 Institut für Mathematik und Rechneranwendung, Fakultät für Luft- und Raumfahrttechnik, Universität der Bundeswehr, 85577 Neubiberg/München, Germany

Received  July 2011 Revised  May 2012 Published  August 2012

We analyze the Euler discretization to a class of linear-quadratic optimal control problems. First we show convergence of order $h$ for the optimal values of the objective function, where $h$ is the mesh size. Under the additional assumption that the optimal control has bang-bang structure we show that the discrete and the continuous controls coincide except on a set of measure $O(\sqrt{h})$. Under a slightly stronger assumption on the smoothness of the coefficients of the system equation we obtain an error estimate of order $O(h)$.
Citation: Walter Alt, Robert Baier, Matthias Gerdts, Frank Lempio. Error bounds for Euler approximation of linear-quadratic control problems with bang-bang solutions. Numerical Algebra, Control and Optimization, 2012, 2 (3) : 547-570. doi: 10.3934/naco.2012.2.547
##### References:
 [1] W. Alt, On the approximation of infinite optimization problems with an application to optimal control problems, Appl. Math. Optim., 12 (1984), 15-27. doi: 10.1007/BF01449031. [2] W. Alt, Local stability of solutions to differentiable optimization problems in Banach spaces, J. Optim. Theory Appl., 70 (1991), 443-466. doi: 10.1007/BF00941297. [3] W. Alt, Discretization and mesh-independence of Newton's method for generalized equations, in "Mathematical Programming with Data Perturbations V" (ed. A. V. Fiacco), Lecture Notes in Pure and Applied Mathematics 195, Marcel Dekker, (1997), 1-30. [4] W. Alt, R. Baier, M. Gerdts and F. Lempio, Approximations of linear control problems with bang-bang solutions, Optimization, DOI: 10.1080/02331934.2011.568619, (2011). doi: 10.1080/02331934.2011.568619. [5] W. Alt and N. Bräutigam, Finite-difference discretizations of quadratic control problems governed by ordinary elliptic differential equations, Comp. Optim. Appl., 43 (2009), 133-150. doi: 10.1007/s10589-007-9129-6. [6] W. Alt and U. Mackenroth, Convergence of finite element approximations to state constrained convex parabolic boundary control problems, SIAM J. Control Optim., 27 (1989), 718-736. doi: 10.1137/0327038. [7] W. Alt and M. Seydenschwanz, Regularization and discretization of linear-quadratic control problems,, Control Cybernet., (). [8] R. Baier, I. A. Chahma and F. Lempio, Stability and convergence of Euler's method for state-constrained differential inclusions, SIAM J. Optim., 18 (2007), 1004-1026. doi: 10.1137/060661867. [9] W. J. Beyn and J. Rieger, Numerical fixed grid methods for differential inclusions, Computing, 81 (2007), 91-106. doi: 10.1007/s00607-007-0240-4. [10] I. A. Chahma, Set-valued discrete approximation of state-constrained differential inclusions, Bayreuth. Math. Schr., 67 (2003), 3-161. [11] K. Deckelnick and M. Hinze, A note on the approximation of elliptic control problems with bang-bang controls, Comp. Optim. Appl., DOI: 10.1007/s10589-010-9365-z, (2010). doi: 10.1007/s10589-010-9365-z. [12] V. Dhamo and F. Tröltzsch, Some aspects of reachability for parabolic boundary control problems with control constraints, Comp. Optim. Appl., DOI: 10.1007/s10589-009-9310-1, (2010). doi: 10.1007/s10589-009-9310-1. [13] A. L. Dontchev and E. M. Farkhi, Error estimates for discretized differential inclusions, Computing, 41 (1989), 349-358. doi: 10.1007/BF02241223. [14] A. L. Dontchev and W. W. Hager, Lipschitzian stability in nonlinear control and optimization, SIAM J. Control Optim., 31 (1993), 569-603. doi: 10.1137/0331026. [15] A. L. Dontchev and W. W. Hager, The Euler approximation in state constrained optimal control, Math. Comp., 70 (2001), 173-203. doi: 10.1090/S0025-5718-00-01184-4. [16] A. L. Dontchev, W. W. Hager and K. Malanowski, Error bounds for Euler approximation of a state and control constrained optimal control problem, Numer. Funct. Anal. Optim., 21 (2000), 653-682. doi: 10.1080/01630560008816979. [17] I. Ekeland and R. Temam, "Convex Analysis and Variational Problems," North Holland, Amsterdam-Oxford, 1976. [18] U. Felgenhauer, On stability of bang-bang type controls, SIAM J. Control Optim., 41 (2003), 1843-1867. doi: 10.1137/S0363012901399271. [19] U. Felgenhauer, The shooting approach in analyzing bang-bang extremals with simultaneous control switches, Control Cybernet., 37 (2008), 307-327. [20] U. Felgenhauer, Directional sensitivity differentials for parametric bang-bang control problems, in "Lecture Notes Comp. Sci., Vol. 5910" (eds. I. Lirkov et al.), Springer-Verlag, (2010), 264-271. [21] U. Felgenhauer, L. Poggiolini and G. Stefani, Optimality and stability result for bang-bang optimal controls with simple and double switch behaviour, Control Cybernet., 38 (2009), 1305-1325. [22] M. R. Hestenes, "Calculus of Variations and Optimal Control Theory," Robert E. Krieger Publ. Co., 1980. [23] M. Hinze, A variational discretization concept in control constrained optimization: The linear-quadratic case, Comp. Optim. Appl., 30 (2005), 45-61. doi: 10.1007/s10589-005-4559-5. [24] K. Malanowski, C. Büskens and H. Maurer, Convergence of approximations to nonlinear optimal control problems, in "Mathematical Programming with Data Perturbations V" (ed. A. V. Fiacco), Lecture Notes in Pure and Applied Mathematics 195, Marcel Dekker, (1997), 253-284. [25] H. Maurer, C. Büskens, J.-H. R. Kim and C. Y. Kaya, Optimization methods for the verification of second-order sufficient conditions for bang-bang controls, Optimal Control Appl. Methods, 26 (2005), 129-156. doi: 10.1002/oca.756. [26] H. Maurer and N. P. Osmolovskii, Second order sufficient conditions for time optimal bang-bang control, SIAM J. Control Optim., 42 (2004), 2239-2263. doi: 10.1137/S0363012902402578. [27] P. Merino, F. Tröltzsch and B. Vexler, Error estimates for the finite element approximation of a semilinear elliptic control problem with state constraints and finite dimensional control space, ESAIM, Math. Model. Numer. Anal., 44 (2010), 167-188. doi: 10.1051/m2an/2009045. [28] C. Meyer and A. Rösch, Superconvergence properties of optimal control problems, SIAM J. Contr. Optim., 43 (2004), 970-985. doi: 10.1137/S0363012903431608. [29] B. Sendov and V. A. Popov, "The Averaged Moduli of Smoothness," Wiley-Interscience, 1988. [30] J. Stoer and R. Bulirsch, "Introduction to Numerical Analysis," Springer-Verlag, 1994. [31] V. M. Veliov, On the time-discretization of control systems, SIAM J. Control Optim., 35 (1997), 1470-1486. doi: 10.1137/S0363012995288987. [32] V. M. Veliov, Error analysis of discrete approximations to bang-bang optimal control problems: the linear case, Control Cybernet., 34 (2005), 967-982. [33] P. R. Wolenski, The exponential formula for the reachable set of a Lipschitz differential inclusion, SIAM J. Control Optim., 28 (1990), 1148-1161. doi: 10.1137/0328062.

show all references

##### References:
 [1] W. Alt, On the approximation of infinite optimization problems with an application to optimal control problems, Appl. Math. Optim., 12 (1984), 15-27. doi: 10.1007/BF01449031. [2] W. Alt, Local stability of solutions to differentiable optimization problems in Banach spaces, J. Optim. Theory Appl., 70 (1991), 443-466. doi: 10.1007/BF00941297. [3] W. Alt, Discretization and mesh-independence of Newton's method for generalized equations, in "Mathematical Programming with Data Perturbations V" (ed. A. V. Fiacco), Lecture Notes in Pure and Applied Mathematics 195, Marcel Dekker, (1997), 1-30. [4] W. Alt, R. Baier, M. Gerdts and F. Lempio, Approximations of linear control problems with bang-bang solutions, Optimization, DOI: 10.1080/02331934.2011.568619, (2011). doi: 10.1080/02331934.2011.568619. [5] W. Alt and N. Bräutigam, Finite-difference discretizations of quadratic control problems governed by ordinary elliptic differential equations, Comp. Optim. Appl., 43 (2009), 133-150. doi: 10.1007/s10589-007-9129-6. [6] W. Alt and U. Mackenroth, Convergence of finite element approximations to state constrained convex parabolic boundary control problems, SIAM J. Control Optim., 27 (1989), 718-736. doi: 10.1137/0327038. [7] W. Alt and M. Seydenschwanz, Regularization and discretization of linear-quadratic control problems,, Control Cybernet., (). [8] R. Baier, I. A. Chahma and F. Lempio, Stability and convergence of Euler's method for state-constrained differential inclusions, SIAM J. Optim., 18 (2007), 1004-1026. doi: 10.1137/060661867. [9] W. J. Beyn and J. Rieger, Numerical fixed grid methods for differential inclusions, Computing, 81 (2007), 91-106. doi: 10.1007/s00607-007-0240-4. [10] I. A. Chahma, Set-valued discrete approximation of state-constrained differential inclusions, Bayreuth. Math. Schr., 67 (2003), 3-161. [11] K. Deckelnick and M. Hinze, A note on the approximation of elliptic control problems with bang-bang controls, Comp. Optim. Appl., DOI: 10.1007/s10589-010-9365-z, (2010). doi: 10.1007/s10589-010-9365-z. [12] V. Dhamo and F. Tröltzsch, Some aspects of reachability for parabolic boundary control problems with control constraints, Comp. Optim. Appl., DOI: 10.1007/s10589-009-9310-1, (2010). doi: 10.1007/s10589-009-9310-1. [13] A. L. Dontchev and E. M. Farkhi, Error estimates for discretized differential inclusions, Computing, 41 (1989), 349-358. doi: 10.1007/BF02241223. [14] A. L. Dontchev and W. W. Hager, Lipschitzian stability in nonlinear control and optimization, SIAM J. Control Optim., 31 (1993), 569-603. doi: 10.1137/0331026. [15] A. L. Dontchev and W. W. Hager, The Euler approximation in state constrained optimal control, Math. Comp., 70 (2001), 173-203. doi: 10.1090/S0025-5718-00-01184-4. [16] A. L. Dontchev, W. W. Hager and K. Malanowski, Error bounds for Euler approximation of a state and control constrained optimal control problem, Numer. Funct. Anal. Optim., 21 (2000), 653-682. doi: 10.1080/01630560008816979. [17] I. Ekeland and R. Temam, "Convex Analysis and Variational Problems," North Holland, Amsterdam-Oxford, 1976. [18] U. Felgenhauer, On stability of bang-bang type controls, SIAM J. Control Optim., 41 (2003), 1843-1867. doi: 10.1137/S0363012901399271. [19] U. Felgenhauer, The shooting approach in analyzing bang-bang extremals with simultaneous control switches, Control Cybernet., 37 (2008), 307-327. [20] U. Felgenhauer, Directional sensitivity differentials for parametric bang-bang control problems, in "Lecture Notes Comp. Sci., Vol. 5910" (eds. I. Lirkov et al.), Springer-Verlag, (2010), 264-271. [21] U. Felgenhauer, L. Poggiolini and G. Stefani, Optimality and stability result for bang-bang optimal controls with simple and double switch behaviour, Control Cybernet., 38 (2009), 1305-1325. [22] M. R. Hestenes, "Calculus of Variations and Optimal Control Theory," Robert E. Krieger Publ. Co., 1980. [23] M. Hinze, A variational discretization concept in control constrained optimization: The linear-quadratic case, Comp. Optim. Appl., 30 (2005), 45-61. doi: 10.1007/s10589-005-4559-5. [24] K. Malanowski, C. Büskens and H. Maurer, Convergence of approximations to nonlinear optimal control problems, in "Mathematical Programming with Data Perturbations V" (ed. A. V. Fiacco), Lecture Notes in Pure and Applied Mathematics 195, Marcel Dekker, (1997), 253-284. [25] H. Maurer, C. Büskens, J.-H. R. Kim and C. Y. Kaya, Optimization methods for the verification of second-order sufficient conditions for bang-bang controls, Optimal Control Appl. Methods, 26 (2005), 129-156. doi: 10.1002/oca.756. [26] H. Maurer and N. P. Osmolovskii, Second order sufficient conditions for time optimal bang-bang control, SIAM J. Control Optim., 42 (2004), 2239-2263. doi: 10.1137/S0363012902402578. [27] P. Merino, F. Tröltzsch and B. Vexler, Error estimates for the finite element approximation of a semilinear elliptic control problem with state constraints and finite dimensional control space, ESAIM, Math. Model. Numer. Anal., 44 (2010), 167-188. doi: 10.1051/m2an/2009045. [28] C. Meyer and A. Rösch, Superconvergence properties of optimal control problems, SIAM J. Contr. Optim., 43 (2004), 970-985. doi: 10.1137/S0363012903431608. [29] B. Sendov and V. A. Popov, "The Averaged Moduli of Smoothness," Wiley-Interscience, 1988. [30] J. Stoer and R. Bulirsch, "Introduction to Numerical Analysis," Springer-Verlag, 1994. [31] V. M. Veliov, On the time-discretization of control systems, SIAM J. Control Optim., 35 (1997), 1470-1486. doi: 10.1137/S0363012995288987. [32] V. M. Veliov, Error analysis of discrete approximations to bang-bang optimal control problems: the linear case, Control Cybernet., 34 (2005), 967-982. [33] P. R. Wolenski, The exponential formula for the reachable set of a Lipschitz differential inclusion, SIAM J. Control Optim., 28 (1990), 1148-1161. doi: 10.1137/0328062.
 [1] M. S. Lee, H. G. Harno, B. S. Goh, K. H. Lim. On the bang-bang control approach via a component-wise line search strategy for unconstrained optimization. Numerical Algebra, Control and Optimization, 2021, 11 (1) : 45-61. doi: 10.3934/naco.2020014 [2] Karl Kunisch, Lijuan Wang. The bang-bang property of time optimal controls for the Burgers equation. Discrete and Continuous Dynamical Systems, 2014, 34 (9) : 3611-3637. doi: 10.3934/dcds.2014.34.3611 [3] Karl Kunisch, Lijuan Wang. Bang-bang property of time optimal controls of semilinear parabolic equation. Discrete and Continuous Dynamical Systems, 2016, 36 (1) : 279-302. doi: 10.3934/dcds.2016.36.279 [4] Gengsheng Wang, Yubiao Zhang. Decompositions and bang-bang properties. Mathematical Control and Related Fields, 2017, 7 (1) : 73-170. doi: 10.3934/mcrf.2017005 [5] Galina Kurina, Sahlar Meherrem. Decomposition of discrete linear-quadratic optimal control problems for switching systems. Conference Publications, 2015, 2015 (special) : 764-774. doi: 10.3934/proc.2015.0764 [6] Mohamed Aliane, Mohand Bentobache, Nacima Moussouni, Philippe Marthon. Direct method to solve linear-quadratic optimal control problems. Numerical Algebra, Control and Optimization, 2021, 11 (4) : 645-663. doi: 10.3934/naco.2021002 [7] Helmut Maurer, Tanya Tarnopolskaya, Neale Fulton. Computation of bang-bang and singular controls in collision avoidance. Journal of Industrial and Management Optimization, 2014, 10 (2) : 443-460. doi: 10.3934/jimo.2014.10.443 [8] Shigeaki Koike, Hiroaki Morimoto, Shigeru Sakaguchi. A linear-quadratic control problem with discretionary stopping. Discrete and Continuous Dynamical Systems - B, 2007, 8 (2) : 261-277. doi: 10.3934/dcdsb.2007.8.261 [9] Russell Johnson, Carmen Núñez. Remarks on linear-quadratic dissipative control systems. Discrete and Continuous Dynamical Systems - B, 2015, 20 (3) : 889-914. doi: 10.3934/dcdsb.2015.20.889 [10] Jianhui Huang, Xun Li, Jiongmin Yong. A linear-quadratic optimal control problem for mean-field stochastic differential equations in infinite horizon. Mathematical Control and Related Fields, 2015, 5 (1) : 97-139. doi: 10.3934/mcrf.2015.5.97 [11] Hanxiao Wang, Jingrui Sun, Jiongmin Yong. Weak closed-loop solvability of stochastic linear-quadratic optimal control problems. Discrete and Continuous Dynamical Systems, 2019, 39 (5) : 2785-2805. doi: 10.3934/dcds.2019117 [12] Georg Vossen, Stefan Volkwein. Model reduction techniques with a-posteriori error analysis for linear-quadratic optimal control problems. Numerical Algebra, Control and Optimization, 2012, 2 (3) : 465-485. doi: 10.3934/naco.2012.2.465 [13] Jingrui Sun, Hanxiao Wang. Mean-field stochastic linear-quadratic optimal control problems: Weak closed-loop solvability. Mathematical Control and Related Fields, 2021, 11 (1) : 47-71. doi: 10.3934/mcrf.2020026 [14] Yadong Shu, Bo Li. Linear-quadratic optimal control for discrete-time stochastic descriptor systems. Journal of Industrial and Management Optimization, 2022, 18 (3) : 1583-1602. doi: 10.3934/jimo.2021034 [15] Roberta Fabbri, Russell Johnson, Sylvia Novo, Carmen Núñez. On linear-quadratic dissipative control processes with time-varying coefficients. Discrete and Continuous Dynamical Systems, 2013, 33 (1) : 193-210. doi: 10.3934/dcds.2013.33.193 [16] Nguyen Thi Hoai. Asymptotic approximation to a solution of a singularly perturbed linear-quadratic optimal control problem with second-order linear ordinary differential equation of state variable. Numerical Algebra, Control and Optimization, 2021, 11 (4) : 495-512. doi: 10.3934/naco.2020040 [17] M. Soledad Aronna, J. Frédéric Bonnans, Andrei V. Dmitruk, Pablo A. Lotito. Quadratic order conditions for bang-singular extremals. Numerical Algebra, Control and Optimization, 2012, 2 (3) : 511-546. doi: 10.3934/naco.2012.2.511 [18] Hongyan Yan, Yun Sun, Yuanguo Zhu. A linear-quadratic control problem of uncertain discrete-time switched systems. Journal of Industrial and Management Optimization, 2017, 13 (1) : 267-282. doi: 10.3934/jimo.2016016 [19] Jiongmin Yong. A deterministic linear quadratic time-inconsistent optimal control problem. Mathematical Control and Related Fields, 2011, 1 (1) : 83-118. doi: 10.3934/mcrf.2011.1.83 [20] Ying Hu, Shanjian Tang. Mixed deterministic and random optimal control of linear stochastic systems with quadratic costs. Probability, Uncertainty and Quantitative Risk, 2019, 4 (0) : 1-. doi: 10.1186/s41546-018-0035-x

Impact Factor: