Abstract
In this paper we present two techniques for analysis of discrete approximations in optimal control. In Section 2 we study convergence properties of the optimal value and optimal solutions. In Section 3 we obtain an estimate for the optimal control error in the case when the Euler discretization scheme is used for solving the first-order optimality conditions. Section 4 contains a survey on related results.
This research was supported in part by the Institute for Mathematics and its Applications with funds provided by the National Science Foundation.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
W. ALT, On the approximation of infinite optimization problems with an application to optimal control problems, Appl. Math. Optim. 12 (1984), 15–27.
H. ATTOUCH, R.J.-B. WETS, Approximation and convergence in nonlinear optimization, Nonlinear Programming 4, (edited by) O. MANGASARIAN, R. MEYER, S. ROBINSON, Academic Press, New York, 1981, pp. 367–394.
E.R. AVAKOV, F.P. VASIL’EV, Difference approximation of a maximin problem of optimal control with phase constraints, Vestnik Moscov. Univ., Ser XV, Vychisl. Mat. Kibernet. (Russian) 2 (1982), 11–17.
M. BARDI, M. FALCONE, An approximationscheme for the minimum time function, SIAM J. Control Optim. 28 (1990), 950–965.
J.M. BORWEIN, A.S. LEWIS, Duality relationship for entropy-like minimization problems, SIAM J. Control Optim. 29 (1991), 325–338.
J.M. BORWEIN, A.S. LEWIS, Partially finite convex programming, Part I: quasi relative interiors and duality theory, Mathematical Programming 57 (1992), 15–48.
B.M. BUDAK, E.M. BERKOVICH, E.N. SOLOV’EVA, Difference approximations in optimal control problems, SIAM J. Control 7 (1969), 18–31. (originally published in Russian in Vestnik Mosk. Univ. Seriya I: Matemat. Mekhanika 2 (1968), 41–55).
B.M. BUDAK, E.M. BERKOVICH, E.N. SOLOV’EVA, The convergence of difference approximations in optimal control, Zh. Vychisl. Mat. i Math. Fiz. (Russian) 59 (1969), 533–547.
B.M. BUDAK, F.P. VASIL’EV, Some Computational Aspects of Optimal Control Problems, Moscow University Press, Moscow (Russian), 1975.
I. CAPUZZO DOLCETTA, On a discrete approximation of the Hamilton-Jacobi equation of dynamic programming, Appl. Math. Optim. 10 (1983), 367–377.
I. CHRYSSOVERGHI, A. BACOPOULOS, Discrete approximation of relaxed optimal control problems, J. Optim. Theory Appl. 65 (1990), 395–407.
M.G. CRANDALL, P.L. LIONS, TWO approximations of solutions of Hamilton-Jacobi equations, Math. of Comp. 43 (1984), 1–19.
J. CULLUM, Discrete approximations to continuous optimal control problems, SIAM J. Control 7 (1969), 32–49.
J. CULLUM, An explicit procedure for discretizingcontinuous, optimal control problems, Journ. of Optim. Theory and Appl. 8 (1971), 15–34.
J. CULLUM, Finite-dimensional approximations of state constrained continuous optimal control problems, SIAM J. Control 10 (1972), 649–670.
J.W. DANIEL, On the approximate minimization of functionals, Math. Computation 23 (1969), 573–581.
J.W. DANIEL, On the convergence of a numerical method in optimal control, J. Optim. Theory and Appl. 4 (1969), 330–342.
J.W. DANIEL, The Approximate Minimization of Functionals, Wiley-Interscience, New York, 1983.
A.L. DONTCHEV, Error estimates for a discrete approximation to constrained control problems, SIAM J. Numer. Anal. 18 (1981), 500–514.
A.L. DONTCHEV, Perturbations, Approximations and Sensitivity Analysis of Optimal Control Systems, Lecture Notes in Contr. Inf. Sci. 52, Springer, Berlin, 1983.
A.L. DONTCHEV, Equivalent perturbations and approximations in optimal control, International Series Numer. Math. 84, Birkhäuser, 1988, pp. 43–54.
A.L. DONTCHEV, Duality methods in constrained best interpolation, Mathematica Balkanica 1 (1987), 96–105.
A.L. DONTCHEV, Best interpolation in a strip, J. Approx. Theory, 73 (1993), 334–342.
A.L. DONTCHEV, E.M. FARHI, Error estimates for discretized differential inclusions, Computing 41 (1989), 349–358.
A.L. DONTCHEV, W.W. HAGER, Lipschitz stability in nonlinear control and optimization, SIAM J. Control Optim. 31 (1993), 569–603.
A.L. DONTCHEV, W.W. HAGER, An inverse mapping theorem for set-valued maps, Proc. Amer. Math. Soc. 121 (1994), 481–489.
A.L. DONTCHEV, W.W. HAGER, Euler approximation to the feasible set, Num. Funct. Anal. Optim. 15 (1994), 245–262.
A.L. DONTCHEV, RL. KALCHEV, Duality and well-posedness in convex interpolation, Num. Funct. Anal. Optim. 10 (1989), 673–690.
A.L. DONTCHEV, F. LEMPIO, Difference methods for differential inclusions—a survey, SIAM Review 34 (1992), 263–294.
A.L. DONTCHEV, T. ZOLEZZI, Well-posed Optimization Problems, Lecture Notes in Math. 1543 Springer, Berlin, 1993.
J.C. DUNN, Diagonally modified conditional gradient method for input constrained optimal control problems, SIAM J. Control Optim. 24 (1986), 1177–1191.
Y.M. ERMOL’EV, V.P. GULENKO, T.I. TSARENKO, Finite Element Methods in Optimal Control, Naukova Dumka, Kiev (Russian), 1978.
M. FALCONE, A numerical approach to the infinite horizon problem of deterministic control theory, Appl. Math. Optim. 15 (1987), 1–13. Corrigenda: Appl. Math. Optim. 23 (1991), 213–214.
R.P. FEDORENKO, Approximate Solution of Optimal Control Problems, Nauka, Moscow (Russian), 1971.
R. GONZALES, E. ROFMAN, On deterministic control problems: an approximation procedure for the optimal cost. Part I: the stationary problem. Part II: the nonstationary case., SIAM J. Control Optim. 23 (1985), 242–265, 267–285.
W.W. HAGER, The Ritz-Trefftz method for state and control constrained optimal control problems, SIAM J. Numer. Anal. 12 (1975), 854–867.
W.W. HAGER, Rate ofconvergence for discrete approximations to unconstrained control problems, SIAM J. Numer. Anal. 13 (1976), 449–471.
W.W. HAGER, Convex control and dual approximations. Part 1. Part 2, Control & Cybern. 8 (1979), 5–12, 321–338.
W.W. HAGER, Multiplier method for nonlinear optimal control, SIAM J. Numer. Anal. 27 (1990), 1061–1080.
W.W. HAGER, G.D. IANCULESCU, Dual approximations in optimal control, SIAM J. Control Optim. 22 (1984), 423–465.
U. HORNUNG, Interpolations by smooth functions under restrictions in the derivatives, J. Approx. Theory 28 (1980), 227–237.
C.T. KELLEY, E.W. SACHS, Mesh independence of the gradient projection method for optimal control problems, SIAM J. Control Optim. 30 (1992), 477–493.
A.A. LEVIKOV, Error estimate for solution of the linear optimal control problem, Avtomat. i Telemekh. 3 (Russian) (1982), 71–78.
K.C.P. MACHIELSEN, Numerical solution of optimal control problems with state constraints by sequential quadratic programming in function space, (dissertation) Technische Hogeschool Eindhoven, Eindhoven, 1987.
K. MALANOWSKI, On convergence of finite-difference approximations to control and state constrained optimal control problems, Archiwum Aut. i Telem. 24 (1979), 319–337.
K. MALANOWSKI, On convergence of finite-difference approximations to optimal control problems for systems with control appearing linearly, Archiwum Aut. i Telem. 24 (1979), 319–337.
K. MALANOWSKI, Convergence of approximations vs. regularity of solutions for convex control-constrained optimal control problems, Appl. Math. Optim. 8 (1981), 69–95.
C.A. MLCHELLI, P.W. SMITH, J. SWETITS, J.D. WARD, Constrained L p approximation, Constr. Approx. 1 (1985), 93–102.
B. MORDUKHOVICH, On difference approximations of optimal control systems, Appl. Math. Mech. 42 (1978), 452–461.
B. MORDUKHOVICH, Discrete approximations and refined Euler-Lagrange conditions for nonconvex differential inclusions, IMA preprint Series 1115, March 1993. (also in) SIAM J. Control Optim. 33 (1995), 882–915.
E. POLAK, Computational Methods in Optimization: A Unified Approach, Academic Press, New York, 1971.
E. POLAK, An historical survey of computations methods in optimal control, SIAM Review 15 (1973), 548–553.
E. POLAK, On the use of consistent approximations in the solution of semi-infinite optimization and optimal control problems, Dept. of Electr. Eng. and Comp. Sc., University of California, Berkeley (preprint).
E. POLAK, LIMIN HE, Rate-preserving strategies for semi-infinite programming and optimal control, SIAM J. Control Optim. 30 (1992), 543–572.
E. POLAK, T.H. YANG, D.Q. MAYNE, A method of centers based on barrier functions for solving optimal control problems with continuous state and control constraints, SIAM J. Control Optim. 31 (1993), 159–179.
G.W. REDDIEN, Collocation at gauss points as a discretization in optimal control, SIAM J. Control Optim. 17 (1979), 298–316.
BL. SENDOV, V.A. POPOV, The Averaged Moduli of Smoothness, J. Wiley & Sons, New York 1988.
K.L. TEO, C.J. GOH, K.H. WANG, A Unified Computational Approach to Optimal Control Problems, Longman Sci. Tech., Harlow, 1991.
F.P. VASIL’EV, Methods for Solving Extremum Problems, Nauka, Moscow (Russian) 1981.
V.V. VASIN, Discrete approximation and stability in extremal problems, Zh. Vy-chisl. Mat. i Mat. Fiz. 22 (1982), 824–839.
V.M. VELIOV, Second order discrete approximations to strongly convex differential inclusions, Systems & Control Letters, 13 (1989), 263–269.
V.M. VELIOV, Second order discrete approximations to linear differential inclusions, SIAM J. Numer. Anal. 29 (1992), 439–451.
V.M. VELIOV, Best approximations of control/uncertain differential systems by means of discrete-time systems, IIASA WP-91–45, November 1991.
J. WARGA, Relaxed variational problems, J. Math. Anal. Appl. 4 (1962), 111–145.
R.A. WIJSMAN, Convergence of sequences of convex sets, cones and functions, Bull. Amer. Math. Soc. 70 (1964), 186–188.
P.R. WOLENSKI, The exponential formula for the reachable set of aLipschitz differential inclusion, SIAM J. Control Optim. 28 (1990), 1148–1161.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1996 Springer-Verlag New York, Inc.
About this paper
Cite this paper
Dontchev, A.L. (1996). Discrete Approximations in Optimal Control. In: Mordukhovich, B.S., Sussmann, H.J. (eds) Nonsmooth Analysis and Geometric Methods in Deterministic Optimal Control. The IMA Volumes in Mathematics and its Applications, vol 78. Springer, New York, NY. https://doi.org/10.1007/978-1-4613-8489-2_3
Download citation
DOI: https://doi.org/10.1007/978-1-4613-8489-2_3
Publisher Name: Springer, New York, NY
Print ISBN: 978-1-4613-8491-5
Online ISBN: 978-1-4613-8489-2
eBook Packages: Springer Book Archive