American Institute of Mathematical Sciences

Advanced
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

Walter Alt 1, , Robert Baier 2, , Matthias Gerdts 3, and  Frank Lempio 2,

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)$.
Keywords: discretization., bang-bang control, Linear-quadratic optimal control.
Mathematics Subject Classification: Primary: 49J15; Secondary: 49M25, 49N10, 49J3.
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 & 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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[7]

W. Alt and M. Seydenschwanz, Regularization and discretization of linear-quadratic control problems,, Control Cybernet., ().   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[10]

I. A. Chahma, Set-valued discrete approximation of state-constrained differential inclusions, Bayreuth. Math. Schr., 67 (2003), 3-161.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[13]

A. L. Dontchev and E. M. Farkhi, Error estimates for discretized differential inclusions, Computing, 41 (1989), 349-358. doi: 10.1007/BF02241223.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[17]

I. Ekeland and R. Temam, "Convex Analysis and Variational Problems," North Holland, Amsterdam-Oxford, 1976.  Google Scholar

[18]

U. Felgenhauer, On stability of bang-bang type controls, SIAM J. Control Optim., 41 (2003), 1843-1867. doi: 10.1137/S0363012901399271.  Google Scholar

[19]

U. Felgenhauer, The shooting approach in analyzing bang-bang extremals with simultaneous control switches, Control Cybernet., 37 (2008), 307-327.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[22]

M. R. Hestenes, "Calculus of Variations and Optimal Control Theory," Robert E. Krieger Publ. Co., 1980.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[29]

B. Sendov and V. A. Popov, "The Averaged Moduli of Smoothness," Wiley-Interscience, 1988.  Google Scholar

[30]

J. Stoer and R. Bulirsch, "Introduction to Numerical Analysis," Springer-Verlag, 1994. Google Scholar

[31]

V. M. Veliov, On the time-discretization of control systems, SIAM J. Control Optim., 35 (1997), 1470-1486. doi: 10.1137/S0363012995288987.  Google Scholar

[32]

V. M. Veliov, Error analysis of discrete approximations to bang-bang optimal control problems: the linear case, Control Cybernet., 34 (2005), 967-982.  Google Scholar

[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.  Google Scholar

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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[7]

W. Alt and M. Seydenschwanz, Regularization and discretization of linear-quadratic control problems,, Control Cybernet., ().   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[10]

I. A. Chahma, Set-valued discrete approximation of state-constrained differential inclusions, Bayreuth. Math. Schr., 67 (2003), 3-161.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[13]

A. L. Dontchev and E. M. Farkhi, Error estimates for discretized differential inclusions, Computing, 41 (1989), 349-358. doi: 10.1007/BF02241223.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[17]

I. Ekeland and R. Temam, "Convex Analysis and Variational Problems," North Holland, Amsterdam-Oxford, 1976.  Google Scholar

[18]

U. Felgenhauer, On stability of bang-bang type controls, SIAM J. Control Optim., 41 (2003), 1843-1867. doi: 10.1137/S0363012901399271.  Google Scholar

[19]

U. Felgenhauer, The shooting approach in analyzing bang-bang extremals with simultaneous control switches, Control Cybernet., 37 (2008), 307-327.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[22]

M. R. Hestenes, "Calculus of Variations and Optimal Control Theory," Robert E. Krieger Publ. Co., 1980.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[29]

B. Sendov and V. A. Popov, "The Averaged Moduli of Smoothness," Wiley-Interscience, 1988.  Google Scholar

[30]

J. Stoer and R. Bulirsch, "Introduction to Numerical Analysis," Springer-Verlag, 1994. Google Scholar

[31]

V. M. Veliov, On the time-discretization of control systems, SIAM J. Control Optim., 35 (1997), 1470-1486. doi: 10.1137/S0363012995288987.  Google Scholar

[32]

V. M. Veliov, Error analysis of discrete approximations to bang-bang optimal control problems: the linear case, Control Cybernet., 34 (2005), 967-982.  Google Scholar

[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.  Google Scholar

[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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & Continuous Dynamical Systems - B, 2015, 20 (3) : 889-914. doi: 10.3934/dcdsb.2015.20.889
[10]

Yadong Shu, Bo Li. Linear-quadratic optimal control for discrete-time stochastic descriptor systems. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021034
[11]

Jianhui Huang, Xun Li, Jiongmin Yong. A linear-quadratic optimal control problem for mean-field stochastic differential equations in infinite horizon. Mathematical Control & Related Fields, 2015, 5 (1) : 97-139. doi: 10.3934/mcrf.2015.5.97
[12]

Hanxiao Wang, Jingrui Sun, Jiongmin Yong. Weak closed-loop solvability of stochastic linear-quadratic optimal control problems. Discrete & Continuous Dynamical Systems, 2019, 39 (5) : 2785-2805. doi: 10.3934/dcds.2019117
[13]

Georg Vossen, Stefan Volkwein. Model reduction techniques with a-posteriori error analysis for linear-quadratic optimal control problems. Numerical Algebra, Control & Optimization, 2012, 2 (3) : 465-485. doi: 10.3934/naco.2012.2.465
[14]

Jingrui Sun, Hanxiao Wang. Mean-field stochastic linear-quadratic optimal control problems: Weak closed-loop solvability. Mathematical Control & Related Fields, 2021, 11 (1) : 47-71. doi: 10.3934/mcrf.2020026
[15]

Roberta Fabbri, Russell Johnson, Sylvia Novo, Carmen Núñez. On linear-quadratic dissipative control processes with time-varying coefficients. Discrete & 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 & 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 & 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 & 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 & 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: 

Tools

Metrics

  • PDF downloads (74)
  • HTML views (0)
  • Cited by (27)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences