Discrete mechanics and optimal control: An analysis
ESAIM: Control, Optimisation and Calculus of Variations, Volume 17 (2011) no. 2, p. 322-352

The optimal control of a mechanical system is of crucial importance in many application areas. Typical examples are the determination of a time-minimal path in vehicle dynamics, a minimal energy trajectory in space mission design, or optimal motion sequences in robotics and biomechanics. In most cases, some sort of discretization of the original, infinite-dimensional optimization problem has to be performed in order to make the problem amenable to computations. The approach proposed in this paper is to directly discretize the variational description of the system's motion. The resulting optimization algorithm lets the discrete solution directly inherit characteristic structural properties from the continuous one like symmetries and integrals of the motion. We show that the DMOC (Discrete Mechanics and Optimal Control) approach is equivalent to a finite difference discretization of Hamilton's equations by a symplectic partitioned Runge-Kutta scheme and employ this fact in order to give a proof of convergence. The numerical performance of DMOC and its relationship to other existing optimal control methods are investigated.

DOI : https://doi.org/10.1051/cocv/2010012
Classification:  49M25,  49N99,  65K10
Keywords: optimal control, discrete mechanics, discrete variational principle, convergence
@article{COCV_2011__17_2_322_0,
author = {Ober-Bl\"obaum, Sina and Junge, Oliver and Marsden, Jerrold E.},
title = {Discrete mechanics and optimal control: An analysis},
journal = {ESAIM: Control, Optimisation and Calculus of Variations},
publisher = {EDP-Sciences},
volume = {17},
number = {2},
year = {2011},
pages = {322-352},
doi = {10.1051/cocv/2010012},
mrnumber = {2801322},
language = {en},
url = {http://www.numdam.org/item/COCV_2011__17_2_322_0}
}

Ober-Blöbaum, Sina; Junge, Oliver; Marsden, Jerrold E. Discrete mechanics and optimal control: An analysis. ESAIM: Control, Optimisation and Calculus of Variations, Volume 17 (2011) no. 2, pp. 322-352. doi : 10.1051/cocv/2010012. http://www.numdam.org/item/COCV_2011__17_2_322_0/

[1] U. Ascher, J. Christiansen and R.D. Russell, A collocation solver for mixed order systems of boundary value problems. Math. Comput. 33 (1979) 659-679. | MR 521281 | Zbl 0407.65035

[2] V. Bär, Ein Kollokationsverfahren zur numerischen Lösung allgemeiner Mehrpunktrandwertaufgaben mit Schalt- und Sprungbedingungen mit Anwendungen in der Optimalen Steuerung und der Parameteridentifizierung. Diploma Thesis, Bonn, Germany (1983).

[3] J.T. Betts, Survey of numerical methods for trajectory optimization. AIAA J. Guid. Control Dyn. 21 (1998) 193-207. | Zbl 1158.49303

[4] J.T. Betts and W.P. Huffmann, Mesh refinement in direct transcription methods for optimal control. Optim. Control Appl. Meth. 19 (1998) 1-21. | MR 1623173

[5] A.I. Bobenko and Y.B. Suris, Discrete Lagrangian reduction, discrete Euler-Poincaré equations, and semidirect products. Lett. Math. Phys. 49 (1999) 79-93. | MR 1720528 | Zbl 0965.70025

[6] A.I. Bobenko and Y.B. Suris, Discrete time Lagrangian mechanics on Lie groups, with an application to the Lagrange top. Comm. Math. Phys. 204 (1999) 147-188. | MR 1705669 | Zbl 0945.70010

[7] H.G. Bock, Numerical solutions of nonlinear multipoint boundary value problems with applications to optimal control. Z. Angew. Math. Mech. 58 (1978) T407-T409. | MR 507663 | Zbl 0383.65053

[8] H.G. Bock and K.J. Plitt, A multiple shooting algorithm for direct solution of optimal control problems, in 9th IFAC World Congress, Budapest, Hungary, Pergamon Press (1984) 242-247.

[9] J.F. Bonnans and J. Laurent-Varin, Computation of order conditions for symplectic partitioned Runge-Kutta schemes with application to optimal control. Numer. Math. 103 (2006) 1-10. | MR 2207612 | Zbl 1112.65063

[10] N. Bou-Rabee and H. Owhadi, Stochastic variational integrators. IMA J. Numer. Anal. 29 (2008) 421-443. | MR 2491434 | Zbl 1171.37027

[11] A.E. Bryson and Y.C. Ho, Applied Optimal Control. Hemisphere (1975).

[12] R. Bulirsch, Die Mehrzielmethode zur numerischen Lösung von nichtlinearen Randwertproblemen und Aufgaben der optimalen Steuerung. Report of the Carl-Cranz-Gesellschaft e.V., DLR, Oberpfaffenhofen, Germany (1971).

[13] C. Büskens and H. Maurer, SQP-methods for solving optimal control problems with control and state constraints: adjoint variables, sensitivity analysis and real-time control. J. Comput. Appl. Math. 120 (2000) 85-108. | MR 1781710 | Zbl 0963.65070

[14] J.A. Cadzow, Discrete calculus of variations. Int. J. Control 11 (1970) 393-407. | Zbl 0193.07601

[15] J.A. Cadzow, Discrete-Time Systems: An Introduction With Interdisciplinary Applications. Prentice-Hall (1973). | MR 490243

[16] A.L. Cauchy, Méthode générale pour la résolution des systèmes d'équations simultanées. C. R. Acad. Sci. 25 (1847) 536-538.

[17] F.L. Chernousko and A.A. Luybushin, Method of successive approximations for optimal control problems (survey paper). Opt. Control Appl. Meth. 3 (1982) 101-114. | Zbl 0485.49003

[18] P. Deuflhard, A modified Newton method for the solution of ill-conditioned systems of nonlinear equations with application to multiple shooting. Numer. Math. 22 (1974) 289-315. | MR 351093 | Zbl 0313.65070

[19] E.D. Dickmanns and K.H. Well, Approximate solution of optimal control problems using third order hermite polynomial functions. Lect. Notes Comput. Sci. 27 (1975) 158-166.

[20] A.L. Dontchev and W.W. Hager, The Euler Approximation in State Constrained Optimal Control, in Mathematics of Computation 70, American Mathematical Society, USA (2001) 173-203. | MR 1681116 | Zbl 0987.49017

[21] A.L. Dontchev, W.W. Hager and V.M. Veliov, Second order Runge-Kutta approximations in control constrained optimal control. SIAM J. Numer. Anal. 38 (2000) 202-226. | MR 1770350 | Zbl 0968.49022

[22] R.C. Fetecau, J.E. Marsden, M. Ortiz and M. West, Nonsmooth Lagrangian mechanics and variational collision integrators. SIAM J. Appl. Dyn. Syst. 2 (2003) 381-416. | MR 2031279 | Zbl 1088.37045

[23] L. Flatto, Advanced calculus. Williams & Wilkins (1976). | MR 387501 | Zbl 0314.26002

[24] L. Fox, Some numerical experiments with eigenvalue problems in ordinary differential equations, in Boundary value problems in differential equations, R.E. Langer Ed. (1960). | MR 114302 | Zbl 0100.12602

[25] E. Frazzoli, M.A. Dahleh and E. Feron, Maneuver-based motion planning for nonlinear systems with symmetries. IEEE Trans. Robot. 21 (2005) 1077-1091.

[26] A. Griewank, Evaluating Derivatives: Principles and Techniques of Algorithmic Differentiation. SIAM (2000). | MR 1753583 | Zbl 1159.65026

[27] W.W. Hager, Convex control and dual approximations, in Constructive Approaches to Mathematical Models, Academic Press, New York, USA (1979) 189-202. | MR 641919 | Zbl 0443.49007

[28] W.W. Hager, Runge-Kutta methods in optimal control and the transformed adjoint system. Numer. Math. 87 (2000) 247-282. | MR 1804658 | Zbl 0991.49020

[29] W.W. Hager, Numerical analysis in optimal control, in International Series of Numerical Mathematics 139, Birkhäuser Verlag, Basel, Switzerland (2001) 83-93. | MR 1901632 | Zbl 1024.49026

[30] E. Hairer, C. Lubich and G. Wanner, Geometric numerical integration. Springer (2002). | MR 1904823 | Zbl 0994.65135

[31] S.P. Han, Superlinearly convergent variable-metric algorithms for general nonlinear programming problems. Math. Program. 11 (1976) 263-282. | MR 483440 | Zbl 0364.90097

[32] P. Hiltmann, Numerische Lösung von Mehrpunkt-Randwertproblemen und Aufgaben der optimalen Steuerung über endlichdimensionalen Räumen. Ph.D. Thesis, Fakultät für Mathematik und Informatik, Technische Universität München, Germany (1990).

[33] C.L. Hwang and L.T. Fan, A discrete version of Pontryagin's maximum principle. Oper. Res. 15 (1967) 139-146. | MR 205726 | Zbl 0155.42504

[34] B.W. Jordan and E. Polak, Theory of a class of discrete optimal control systems. J. Elec. Ctrl. 17 (1964) 697-711. | MR 179019

[35] O. Junge and S. Ober-Blöbaum, Optimal reconfiguration of formation flying satellites, in IEEE Conference on Decision and Control and European Control Conference ECC, Seville, Spain (2005).

[36] O. Junge, J.E. Marsden and S. Ober-Blöbaum, Discrete mechanics and optimal control, in 16th IFAC World Congress, Prague, Czech Republic (2005). | Zbl pre05908225

[37] O. Junge, J.E. Marsden and S. Ober-Blöbaum, Optimal reconfiguration of formation flying spacecraft - a decentralized approach, in IEEE Conference on Decision and Control and European Control Conference ECC, San Diego, USA (2006) 5210-5215.

[38] C. Kane, J.E. Marsden and M. Ortiz, Symplectic energy-momentum integrators. Math. Phys. 40 (1999) 3353-3371. | MR 1697008 | Zbl 0983.70014

[39] C. Kane, J.E. Marsden, M. Ortiz and M. West, Variational integrators and the Newmark algorithm for conservative and dissipative mechanical systems. Int. J. Numer. Meth. Eng. 49 (2000) 1295-1325. | MR 1805500 | Zbl 0969.70004

[40] E. Kanso and J.E. Marsden, Optimal motion of an articulated body in a perfect fluid, in IEEE Conference on Decision and Control and European Control Conference ECC, Seville, Spain (2005).

[41] W. Karush, Minima of functions of several variables with inequalities as side constraints. Master's thesis, Department of Mathematics, University of Chicago, USA (1939).

[42] H.B. Keller, Numerical methods for two-point boundary value problems. Blaisdell, Waltham, USA (1968). | MR 230476 | Zbl 0172.19503

[43] H.J. Kelley, Gradient theory of optimal flight paths. Journal of the American Rocket Society 30 (1960) 947-953. | Zbl 0096.42002

[44] L. Kharevych, P. Mullen, S. Leyendecker, Y. Tong, J.E. Marsden and M. Desbrun, Robust time-adaptive integrators for computer animation (in preparation).

[45] M. Kobilarov, Discrete geometric motion control of autonomous vehicles. Ph.D. Thesis, University of Southern California, USA (2008).

[46] M. Kobilarov and G.S. Sukhatme, Optimal control using nonholonomic integrators, in IEEE International Conference on Robotics and Automation (ICRA), Rome, Italy (2007) 1832-1837.

[47] M. Kobilarov, M. Desbrun, J.E. Marsden and G.S. Sukhatme, A discrete geometric optimal control framework for systems with symmetries. Robotics: Science and Systems 3 (2007) 1-8. | Zbl pre05501694

[48] D. Kraft, On converting optimal control problems into nonlinear programming problems, in Computational Mathematical Programming F15 of NATO ASI series, K. Schittkowsky Ed., Springer (1985) 261-280. | MR 820046 | Zbl 0572.49015

[49] H.W. Kuhn and A.W. Tucker, Nonlinear programming, in Proceedings of the Second Berkeley Symposium on Mathematical Statisics and Probability, J. Neyman Ed., University of California Press, Berkeley, USA (1951). | MR 47303 | Zbl 0044.05903

[50] T.D. Lee, Can time be a discrete dynamical variable? Phys. Lett. B 121 (1983) 217-220.

[51] T.D. Lee, Difference equations and conservation laws. J. Stat. Phys. 46 (1987) 843-860. | MR 893121

[52] T. Lee, N.H. Mcclamroch and M. Leok, Attitude maneuvers of a rigid spacecraft in a circular orbit, in American Control Conference, Minneapolis, USA (2006) 1742-1747.

[53] T. Lee, N.H. Mcclamroch and M. Leok, Optimal control of a rigid body using geometrically exact computations on SE(3), in IEEE CDC and ECC, San Diego, USA (2006) 2710-2715.

[54] D.B. Leineweber, Efficient reduced SQP methods for the optimization of chemical processes described by large sparse DAE models, in Fortschr.-Bericht VDI Reihe 3, Verfahrenstechnik 613, VDI-Verlag (1999). | Zbl 0997.65502

[55] A. Lew, J.E. Marsden, M. Ortiz and M. West, Asynchronous variational integrators. Arch. Ration. Mech. Anal. 167 (2003) 85-146. | MR 1971150 | Zbl 1055.74041

[56] S. Leyendecker, S. Ober-Blöbaum, J.E. Marsden and M. Ortiz, Discrete mechanics and optimal control for constrained multibody dynamics, in 6th International Conference on Multibody Systems, Nonlinear Dynamics, and Control, ASME International Design Engineering Technical Conferences, Las Vegas, USA (2007).

[57] S. Leyendecker, S. Ober-Blöbaum and J.E. Marsden, Discrete mechanics and optimal control for constrained systems. Optim. Contr. Appl. Meth. (2009) DOI: 10.1002/oca.912. | Zbl 1211.49039

[58] J.D. Logan, First integrals in the discrete calculus of variation. Aequ. Math. 9 (1973) 210-220. | MR 328397 | Zbl 0268.49022

[59] R. Mackay, Some aspects of the dynamics of Hamiltonian systems, in The dynamics of numerics and the numerics of dynamics, D.S. Broomhead and A. Iserles Eds., Clarendon Press, Oxford, UK (1992) 137-193. | MR 1173232 | Zbl 0764.58009

[60] S. Maeda, Canonical structure and symmetries for discrete systems. Math. Jap. 25 (1980) 405-420. | MR 594539 | Zbl 0446.70022

[61] S. Maeda, Extension of discrete Noether theorem. Math. Jap. 26 (1981) 85-90. | MR 613471 | Zbl 0458.70002

[62] S. Maeda, Lagrangian formulation of discrete systems and concept of difference space. Math. Jap. 27 (1981) 345-356. | MR 663162 | Zbl 0531.70020

[63] J.E. Marsden and S. Shkoller, Multisymplectic geometry, covariant Hamiltonians, and water waves. Math. Proc. Camb. Phil. Soc. 125 (1999) 553-575. | MR 1656833 | Zbl 0922.58029

[64] J.E. Marsden and M. West, Discrete mechanics and variational integrators. Acta Numer. 10 (2001) 357-514. | MR 2009697 | Zbl 1123.37327

[65] J.E. Marsden, G.W. Patrick and S. Shkoller, Multisymplectic geometry, variational integrators, and nonlinear PDEs. Commun. Math. Phys. 199 (1998) 351-395. | MR 1666871 | Zbl 0951.70002

[66] J.E. Marsden, S. Pekarsky and S. Shkoller, Discrete Euler-Poincaré and Lie Poisson equations. Nonlinearity 12 (1999) 1647-1662. | MR 1726670 | Zbl 0978.37045

[67] J.E. Marsden, S. Pekarsky and S. Shkoller, Symmetry reduction of discrete Lagrangian mechanics on Lie groups. Geometry and Physics 36 (1999) 140-151. | MR 1783688 | Zbl 0976.70011

[68] J. Martin, Discrete mechanics and optimal control. Master's Thesis, Department of Control and Dynamical Systems, California Institute of Technology, USA (2006).

[69] R.I. Mclachlan and S. Marsland, Discrete mechanics and optimal control for image registration, in Computational Techniques and Applications Conference (CTAC) (2006). | MR 2318548

[70] A. Miele, Gradient algorithms for the optimization of dynamic systems, in Control and Dynamic Systems 60, C.T. Leondes Ed. (1980) 1-52.

[71] S. Ober-Blöbaum, Discrete mechanics and optimal control. Ph.D. Thesis, University of Paderborn, Germany (2008). | Zbl pre05908225

[72] G.W. Patrick and C. Cuell, Error analysis of variational integrators of unconstrained lagrangian systems. Numer. Math. 113 (2009) 243-264. | MR 2529508 | Zbl 1177.65119

[73] D. Pekarek, A.D. Ames and J.E. Marsden, Discrete mechanics and optimal control applied to the compass gait biped, in IEEE Conference on Decision and Control and European Control Conference ECC, New Orleans, USA (2007). | Zbl pre05908225

[74] L.S. Pontryagin, V.G. Boltyanski, R.V. Gamkrelidze and E.F. Miscenko, The mathematical theory of optimal processes. John Wiley & Sons (1962). | MR 166037

[75] M.J.D. Powell, A fast algorithm for nonlinearly constrained optimization calculations, in Numerical Analysis Lecture Notes in Mathematics 630, G.A. Watson Ed., Springer (1978) 261-280. | MR 483447 | Zbl 0374.65032

[76] R. Pytlak, Numerical methods for optimal control problems with state constraints. Springer (1999). | MR 1713434 | Zbl 0928.49002

[77] L.B. Rall, Automatic Differentiation: Techniques and Applications, Lect. Notes Comput. Sci. 120. Springer Verlag, Berlin, Germany (1981). | Zbl 0473.68025

[78] S.D. Ross, Optimal flapping strokes for self-propulsion in a perfect fluid, in American Control Conference, Minneapolis, USA (2006) 4118-4122.

[79] B. Sendov and V.A. Popov, The averaged moduli of smoothness. John Wiley (1988). | MR 995672 | Zbl 0653.65002

[80] Y.B. Suris, Hamiltonian methods of Runge-Kutta type and their variational interpretation. Math. Model. 2 (1990) 78-87. | MR 1064467 | Zbl 0972.70500

[81] H. Tolle, Optimization methods. Springer (1975). | Zbl 0312.49001

[82] O. Von Stryk, Numerical solution of optimal control problems by direct collocation, in Optimal Control - Calculus of Variation, Optimal Control Theory and Numerical Methods, R. Bulirsch, A. Miele, J. Stoer and K.H. Well Eds., International Series of Numerical Mathematics 111, Birkhäuser (1993) 129-143. | MR 1298003 | Zbl 0790.49024

[83] O. Von Stryk, Numerical hybrid optimal control and related topics. Habilitation Thesis, TU München, Germany (2000).

[84] A. Walther, A. Kowarz and A. Griewank, ADOL-C: a package for the automatic differentiation of algorithms written in C/C++. ACM TOMS 22 (1996) 131-167. | Zbl 0884.65015

[85] J.M. Wendlandt and J.E. Marsden, Mechanical integrators derived from a discrete variational principle. Physica D 106 (1997) 223-246. | MR 1462313 | Zbl 0963.70507

[86] J.M. Wendlandt and J.E. Marsden, Mechanical systems with symmetry, variational principles and integration algorithms, in Current and Future Directions in Applied Mathematics, M. Alber, B. Hu and J. Rosenthal Eds., Birkhäuser (1997) 219-261. | MR 1445103 | Zbl 0936.70004

[87] R.E. Wengert, A simple automatic derivative evaluation program. Commun. ACM 7 (1964) 463-464. | Zbl 0131.34602