Abstract
The Forward-Backward Sweep Method is a numerical technique for solving optimal control problems. The technique is one of the indirect methods in which the differential equations from the Maximum Principle are numerically solved. After the method is briefly reviewed, two convergence theorems are proved for a basic type of optimal control problem. The first shows that recursively solving the system of differential equations will produce a sequence of iterates converging to the solution of the system. The second theorem shows that a discretized implementation of the continuous system also converges as the iteration and number of subintervals increases. The hypotheses of the theorem are a combination of basic Lipschitz conditions and the length of the interval of integration. An example illustrates the performance of the method.
Similar content being viewed by others
References
Ascher, U.M., Petzold, L.R.: Computer Methods for Ordinary Differential Equations and Differential-Algebraic Equations. SIAM, Philadelphia (1998)
Atkinson, K.: An Introduction to Numerical Analysis, 2nd edn. Wiley, New York (1989)
Atkinson, K., Han, W.: Theoretical Numerical Analysis: A Functional Analysis Framework, 3rd edn. Springer, New York (2009)
Bertolazzi, E., Biral, F., Da Lio, M.: Symbolic-numeric efficient solution of optimal control problems for multibody systems. J. Comput. Appl. Math. 185, 404–421 (2006)
Betts, J.T.: Survey of numerical methods for trajectory optimization. J. Guid. Control Dyn. 21, 193–207 (1998)
Betts, J.T., Campbell, S.L., Engelsone, A.: Direct transcription solution of optimal control problems with higher order state constraints: theory vs practice. Optim. Eng. 8, 1–19 (2007)
Betts, J.T.: Practical Methods for Optimal Control and Estimation Using Nonlinear Programming, 2nd edn. SIAM, Philadelphia (2010)
Birgin, E.G., Martínez, J.M.: Local convergence of an inexact-restoration method and numerical experiments. J. Optim. Theory Appl. 127, 229–247 (2005)
Bulirsch, R., Nerz, E., Pesch, H.J., von Stryk, O.: Combining direct and indirect methods in optimal control: range maximization of a hang glider. In: Bulirsch, R., Miele, A., Stoer, J., Well, K.H. (eds.) Optimal Control, Calculus of Variations, Optimal Control Theory and Numerical Methods. Papers from the Second Conference Held at the University of Freiburg, Freiburg, May 26–June 1, 1991. International Series of Numerical Mathematics, vol. 111. Birkhäuser, Basel (1993)
Chernousko, F.L., Lyubshin, A.A.: Method of successive approximations for solutions of optimal control problems. Optim. Control Appl. Methods 3, 101–114 (1982)
Chryssoverghi, I., Coletsos, I., Kokkinis, B.: Discretization methods for optimal control problems with state constraints. J. Comput. Appl. Math. 191, 1–31 (2006)
Darby, C.L., Hager, W.W., Rao, A.V.: Direct trajectory optimization using a variable low-order adaptive pseudospectral method. J. Spacecr. Rockets 48, 433–445 (2011)
Dontchev, A.L.: Error estimates for a discrete approximation to constrained control problems. SIAM J. Numer. Anal. 18, 500–514 (1981)
Dontchev, A.L., Hager, W.W., Malanowski, K.: Error bounds for the Euler approximation of a state and control constrained optimal control problem. Numer. Funct. Anal. Optim. 21, 653–682 (2000)
Dontchev, A.L., Hager, W.W., Veliov, V.M.: Second-order Runge-Kutta approximations in control constrained optimal control. SIAM J. Numer. Anal. 38, 202–226 (2000)
Dontchev, A.L., Hager, W.W.: The Euler approximation in state constrained optimal control. Math. Comput. 70, 173–203 (2000)
Elnagar, G., Kazemi, M.A., Razzaghi, M.: The pseudospectral Legendre method for discretizing optimal control problems. IEEE Trans. Autom. Control 40, 1793–1796 (1995)
Elnagar, G., Kazemi, M.A.: Pseudospectral Chebyshev optimal control of constrained nonlinear dynamical systems. Comput. Optim. Appl. 11, 195–217 (1998)
Elnagar, G., Kazemi, M.A.: Nonlinear periodic optimal control: a pseudospectral Fourier approach. Numer. Funct. Anal. Optim. 25, 707–724 (2004)
Enright, W.H., Muir, P.H.: Efficient classes of Runge-Kutta methods for two-point boundary value problems. Computing 37, 315–334 (1986)
Garg, D., Patterson, M., Hager, W.W., Rao, A.V., Benson, D.A., Huntington, G.T.: A unified framework for the numerical solution of optimal control problems using pseudospectral methods. Automatica 46, 1843–1851 (2010)
Garg, D., Hager, W.W., Rao, A.V.: Pseudospectral methods for solving infinite-horizon optimal control problems. Automatica 47, 829–837 (2011)
Garg, D., Darby, C.L., Huntington, G.T., Hager, W.W., Rao, A.V.: Direct trajectory optimization and costate estimation of finite-horizon and infinite-horizon optimal control problems using a Radau pseudospectral method. Comput. Optim. Appl. 49, 335–358 (2011)
Gong, Q., Kang, W., Ross, I.M.: A pseudospectral method for the optimal control of constrained feedback linearizable systems. IEEE Trans. Autom. Control 51, 1115–1129 (2006)
Hackbusch, W.: A numerical method for solving parabolic equations with opposite orientations. Computing 20, 229–240 (1978)
Hager, W.W.: Rates of convergence for discrete approximations to unconstrained control problems. SIAM J. Numer. Anal. 13, 449–472 (1976)
Hairer, E., Wanner, G.: Solving Ordinary Differential Equations II: Stiff and Differential-Algebraic Problems. Springer, Berlin (1996)
Iserles, A.: A First Course in the Numerical Analysis of Differential Equations. Cambridge University Press, Cambridge (2009)
Keller, H.B.: Numerical Methods for Two-Point Boundary-Value Problems. Blaisdell, Waltham (1968)
Kunkel, P., Mehrmann, V.: Differential-Algebraic Equations: Analysis and Numerical Solution. Eur. Math. Soc., Zürich (2006)
Kameswaran, S., Biegler, L.T.: Convergence rates for direct transcription of optimal control problems using collocation at Radau points. Comput. Optim. Appl. 41, 81–126 (2008)
Kameswaran, S., Biegler, L.T.: Advantages of nonlinear-programming-based methodologies for inequality path-constrained optimal control problems—a numerical study. SIAM J. Sci. Comput. 30, 957–981 (2008)
Kang, W., Ross, I.M., Gong, Q.: Pseudospectral optimal control and its convergence theorems. In: Astolfi, A., Marconi, L. (eds.) Analysis and Design of Nonlinear Control Systems, pp. 109–124. Springer, Berlin (2008)
Kaya, C.Y., Noakes, J.L.: Computational method for time-optimal switching control. J. Optim. Theory Appl. 117, 69–92 (2003)
Kaya, C.Y., Lucas, S.K., Simakov, S.T.: Computations for bang-bang constrained optimal control using a mathematical programming formulation. Optim. Control Appl. Methods 25, 295–308 (2004)
Kaya, C.Y., Martínez, J.M.: Euler discretization and inexact restoration for optimal control. J. Optim. Theory Appl. 134, 191–206 (2007)
Kaya, C.Y.: Inexact restoration for Runge-Kutta discretization of optimal control problems. SIAM J. Numer. Anal. 48, 1492–1517 (2010)
Lenhart, S., Workman, J.T.: Optimal Control Applied to Biological Models. Chapman & Hall/CRC Press, Boca Raton (2007)
Mitter, S.K.: The successive approximation method for the solution of optimal control problems. Automatica 3, 135–149 (1966)
Quarteroni, A., Valli, A.: Numerical Approximation of Partial Differential Equations. Springer, Berlin (2008)
Ross, I.M., Fahroo, F.: Legendre pseudospectral approximations of optimal control problems. In: Kang, W., Xiao, M., Borges, C. (eds.) New Trends in Nonlinear Dynamics and Control, and Their Applications. Lecture Notes in Control and Inform. Sci., vol. 295, pp. 327–342. Springer, Berlin (2003)
Ross, I.M., Fahroo, F.: Pseudospectral methods for optimal motion planning of differentially flat systems. IEEE Trans. Autom. Control 49, 1410–1413 (2004)
Seierstad, A., Sydsaeter, K.: Optimal Control with Economic Applications. North-Holland, Amsterdam (1987)
Sirisena, H.R., Chou, F.S.: Convergence of the control parameterization Ritz method for nonlinear optimal control problems. J. Optim. Theory Appl. 29, 369–382 (1979)
Teo, K.L., Goh, C.J., Wong, K.H.: A Unified Computational Approach to Optimal Control Problems. Pitman Monographs and Surveys in Pure and Applied Mathematics, vol. 55. Longman, Harlow (1991)
Vlassenbroeck, J., Van Dooren, R.: A Chebyshev technique for solving nonlinear optimal control problems. IEEE Trans. Autom. Control 33, 333–349 (1988)
Walther, A.: Automatic differentiation of explicit Runge-Kutta methods for optimal control. Comput. Optim. Appl. 36, 83–108 (2007)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
McAsey, M., Mou, L. & Han, W. Convergence of the forward-backward sweep method in optimal control. Comput Optim Appl 53, 207–226 (2012). https://doi.org/10.1007/s10589-011-9454-7
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10589-011-9454-7