Parallel indirect solution of optimal control problems. (English) Zbl 1290.49054

Summary: This paper presents an algorithm for the indirect solution of optimal control problems that contain mixed state and control variable inequality constraints. Necessary conditions for optimality lead to an inequality constrained two-point BVP with index-1 differential-algebraic equations (BVP-DAEs). These BVP-DAEs are solved using a multiple shooting method where the DAEs are approximated using a single-step linearly implicit Runge–Kutta (Rosenbrock–Wanner) method. An interior-point Newton method is used to solve the residual equations associated with the multiple shooting discretization. The elements of the residual equations, and the Jacobian of the residual equations, are constructed in parallel. The search direction for the interior-point method is computed by solving a sparse Bordered Almost Block Diagonal (BABD) linear system. Here, a parallel-structured orthogonal factorization algorithm is used to solve the BABD system. Examples are presented to illustrate the efficiency of the parallel algorithm. It is shown that an American National Standards Institute C implementation of the parallel algorithm achieves significant speedup with the increase in the number of processors used.


49M15 Newton-type methods
49K15 Optimality conditions for problems involving ordinary differential equations
49K21 Optimality conditions for problems involving relations other than differential equations
90C51 Interior-point methods
Full Text: DOI


[1] Betts, Survey of numerical methods for trajectory optimization, AIAA Journal Guidance, Control, and Dynamics 21 pp 193– (1998) · Zbl 1158.49303
[2] Bock HG Plitt KJ A multiple shooting algorithm for direct solution of optimal control problems IFAC 9-th Triennial World Congress 1984 1603 1608
[3] Hargraves, Direct trajectory optimization using nonlinear programming and collocation, AIAA Journal Guidance, Control and Dynamics 10 pp 338– (1987) · Zbl 0634.65052
[4] Cuthrell, On the optimization of differential-algebraic process systems, AIChE Journal 33 pp 1257– (1987)
[5] Goh, MISER: a FORTRAN program for solving optimal control problems, Advances in Engineering Software 10 pp 319– (1998)
[6] Kraft, Algorithm 733: TOMP-Fortran modules for optimal control calculations, ACM Transactions on Mathematical Software 20 pp 262– (1994) · Zbl 0888.65079
[7] Fabien, Some tools for the direct solution of optimal control problems, Advances in Engineering Software 29 pp 45– (1998) · Zbl 05467437
[8] Fabien, Direct optimization of dynamic systems described by differential-algebraic equations, Optimal Control Applications and Methods 29 pp 445– (2008)
[9] Agrawal, Optimization of Dynamic Systems (1999)
[10] Bock, Numerical solution of nonlinear multipoint boundary value problems with application to optimal control, ZAMM 58 pp T407-T409– (1978)
[11] Maurer, Numerical solution f singular control problems using multiple shooting techniques, Journal Optimization Theory and Applications 18 pp 235– (1976) · Zbl 0302.65063
[12] Maurer, Application of multiple shooting to the numerical solution of optimal control problems with bounded state variables, Computing 15 pp 105– (1975) · Zbl 0318.49024
[13] Bock HG Eich E Schloder J Bock numerical solution of constrained least squares boundary value problems in differential algebraic equations Proceedings Halle Conference on Numerical Treatment of Differential Equations, 104 1987 269 280
[14] Fabien, Indirect numerical solution of constrained optimal control problems with parameters, Applied Mathematics and Computation 80 pp 43– (1996) · Zbl 0871.65055
[15] Schulz, Exploiting invariants in the numerical solution of multipoint boundary value problems for DAEs, SIAM Journal on Scientific Computing 19 pp 440– (1998) · Zbl 0947.65096
[16] Gerdts, Global convergence of a nonsmooth Newton’s method for control-state constrained optimal control problems, SIAM Journal on Optimization 19 pp 326– (2008) · Zbl 1158.49031
[17] Keller, Accurate difference methods for nonlinear two-point boundary value problems, SIAM Journal on Numerical Analysis 11 pp 305– (1974) · Zbl 0282.65065
[18] Ascher, Numerical Solution of Boundary Value Problems for Ordinary Differential Equations (1995) · Zbl 0843.65054
[19] Cash, A deferred correction method for nonlinear two-point boundary value problems: implementation and numerical evaluation, SIAM Journal on Scientific and Statistical Computing 12 pp 971– (1991) · Zbl 0727.65070
[20] Muir, PMIRKDC: a parallel mono-implicit Runge-Kutta code with defect control for boundary value ODEs, Journal Parallel Computing 29 pp 711– (2003) · Zbl 1243.65093
[21] Ascher, Collocation software for boundary value ODEs, ACM Transactions on Mathematical Software 7 pp 209– (1981) · Zbl 0455.65067
[22] Kierzenka, A BVP solver based on residual control and the MATLAB PSE, ACM Transactions on Mathematical Software 27 pp 299– (2001) · Zbl 1070.65555
[23] Fabien BC MSHOOT: a program for solving BVP-DAEs in optimal control 4-th IASTED International Conference in Robotics and Manufacturing 1996 217 220
[24] England, Multiple shooting using dichotomically stable integrator for solving differential-algebraic equations, Applied Numerical Mathematics 42 pp 117– (2002) · Zbl 0999.65082
[25] Ascher, Collocation software for boundary value differential algebraic equations, SIAM Journal on Scientific Computing 15 pp 938– (1994) · Zbl 0804.65080
[26] Kunkel, Symmetric collocation for unstructured nonlinear differential-algebraic equations with arbitrary index, Numerical Mathematics 98 pp 277– (2004) · Zbl 1061.65075
[27] Amodio, Almost block diagonal linear systems: sequential and parallel solution techniques, and applications, Numerical Linear Algebra with Applications 7 pp 275– (2000) · Zbl 1051.65018
[28] Hartl, A survey of the maximum principles for optimal control problems with state constraints, SIAM Review 37 pp 181– (1995) · Zbl 0832.49013
[29] El-Bakry, On the formulation and theory of the Newton interior-point method for nonlinear programming, Journal of Optimization Theory and Applications 89 pp 507– (1996) · Zbl 0851.90115
[30] Bertsekas, Constrained Optimization and Lagrange Multiplier Methods (1982)
[31] Hairer, Solving Ordinary Differential Equations II: Stiff and Differential-algebraic Problems, 2. ed. (1996) · Zbl 1192.65097
[32] Novati, Some secant approximations for Rosenbrock W-methods, Journal Applied Numerical Mathematics 58 pp 195– (2008) · Zbl 1135.65343
[33] Wright, Stable parallel algorithms for two-point boundary value problems, SIAM Journal on Scientific Computing 13 pp 742– (1992) · Zbl 0757.65095
[34] Amodio, Algorithm 859: BABDCR-a Fortran 90 package for the solution of bordered ABD linear systems, ACM Transactions on Mathematical Software 32 pp 597– (2006) · Zbl 1230.65038
[35] Golub, Matrix Computations (1989)
[36] Karp, Measuring parallel processor performance, Communications of the ACM 33 pp 539– (1990)
[37] Junkins, Optimal continuous torque attitude maneuvers, Journal of Guidance, Control, and Dynamics 3 pp 210– (1980)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.