Adjoint Estimation from a Direct Multiple Shooting Method

To solve the multipoint boundary-value problem (MPBVP) associated with a constrained optimal control problem, one needs a good guess not only for the state but also for the costate variables. A direct multiple shooting method is described, which yields approximations of the optimal state and control histories. The Kuhn–Tucker conditions for the optimal parametric control are rewritten using adjoint variables. From this representation, estimates for the adjoint variables at the multiple shooting nodes are derived. The estimates are proved to be consistent, in the sense that they converge toward the MPBVP solution if the parametrization is refined. An optimal aircraft maneuver demonstrates the transition from the direct to the indirect method.     

Existence and Multiple Solutions of the Minimum-Fuel Orbit Transfer Problem

In this paper, the well-known problem of piloting a rocket with a low thrust propulsion system in an inverse square law field (say from Earth orbit to Mars orbit or from Earth orbit to Mars) is considered. By direct methods, it is shown that the existence of a fuel-optimal solution of this problem can be guaranteed, if one restricts the admissible transfer times by an arbitrarily prescribed upper bound. Numerical solutions of the problem with different numbers of thrust subarcs are presented which are obtained by multiple shooting techniques. Further, a general principle for the construction of such solutions with increasing numbers of thrust subarcs is given. The numerical results indicate that there might not exist an overall optimal solution of the Earth-orbit problem with unbounded free transfer time.     

Abort landing in the presence of windshear as a minimax optimal control problem,part 2: Multiple shooting and homotopy

In Part 1 of the paper (Ref. 2), we have shown that the necessary conditions for the optimal control problem of the abort landing of a passenger aircraft in the presence of windshear result in a multipoint boundary-value problem. This boundary-value problem is especially well suited for numerical treatment by the multiple shooting method. Since this method is basically a Newton iteration, initial guesses of all variables are needed and assumptions about the switching structure have to be made. These are big obstacles, but both can be overcome by a so-called homotopy strategy where the problem is imbedded into a one-parameter family of subproblems in such a way that (at least) the first problem is simple to solve. The solution data to the first problem may serve as an initial guess for the next problem, thus resulting in a whole chain of problems. This process is to be continued until the objective problem is reached.Techniques are presented here on how to handle the various changes of the switching structure during the homotopy run. The windshear problem, of great interest for safety in aviation, also serves as an excellent benchmark problem: Nearly all features that can arise in optimal control appear when solving this problem. For example, the candidate for an optimal trajectory of the minimax optimal control problem shows subarcs with both bang-bang and singular control functions, boundary arcs and touch points of two state constraints, one being of first order and the other being of third order, etc. Therefore, the results of this paper may also serve as some sort of user's guide for the solution of complicated real-life optimal control problems by multiple shooting.The candidate found for an optimal trajectory is discussed and compared with an approximate solution already known (Refs. 3–4). Besides the known necessary conditions, additional sharp necessary conditions based on sign conditions of certain multipliers are also checked. This is not possible when using direct methods.An extended abstract of this paper was presented at the 8th IFAC Workshop on Control Applications of Nonlinear Programming and Optimization, Paris, France, 1989 (see Ref. 1).This paper is dedicated to Professor Hans J. Stetter on the occasion of his 60th birthday.     

Numerical Computation of Optimal Feed Rates for a Fed-Batch Fermentation Model

In this paper, we consider a model for a fed-batch fermentation process which describes the biosynthesis of penicillin. First, we solve the problem numerically by using a direct shooting method. By discretization of the control variable, we transform the basic optimal control problem to a finite-dimensional nonlinear programming problem, which is solved numerically by a standard SQP method. Contrary to earlier investigations (Luus, 1993), we consider the problem as a free final time problem, thus obtaining an improved value of the penicillin output. The results indicate that the assumption of a continuous control which underlies the discretization scheme seems not to be valid. In a second step, we apply classical optimal control theory to the fed-batch fermentation problem. We derive a boundary-value problem (BVP) with switching conditions, which can be solved numerically by multiple shooting techniques. It turns out that this BVP is sensitive, which is due to the rigid behavior of the specific growth rate functions. By relaxation of the characteristic parameters, we obtain a simpler BVP, which can be solved by using the predicted control structure (Lim et al., 1986). Now, by path continuation methods, the parameters are changed up to the original values. Thus, we obtain a solution which satisfies all first-order and second-order necessary conditions of optimal control theory. The solution is similar to the one obtained by direct methods, but in addition it contains certain very small bang-bang subarcs of the control. Earlier results on the maximal output of penicillin are improved.     

Numerical computation of singular control problems with application to optimal heating and cooling by solar energy

The method presented here is an extension of the multiple shooting algorithm in order to handle multipoint boundary-value problems and problems of optimal control in the special situation of singular controls or constraints on the state variables. This generalization allows a direct treatment of (nonlinear) conditions at switching points. As an example a model of optimal heating and cooling by solar energy is considered. The model is given in the form of an optimal control problem with three control functions appearing linearly and a first order constraint on the state variables. Numerical solutions of this problem by multiple shooting techniques are presented.     

Direct Shooting Method for the Numerical Solution of Higher-Index DAE Optimal Control Problems

A method for the numerical solution of state-constrained optimal control problems subject to higher-index differential-algebraic equation (DAE) systems is introduced. For a broad and important class of DAE systems (semiexplicit systems with algebraic variables of different index), a direct multiple shooting method is developed. The multiple shooting method is based on the discretization of the optimal control problem and its transformation into a finite-dimensional nonlinear programming problem (NLP). Special attention is turned to the mandatory calculation of consistent initial values at the multiple shooting nodes within the iterative solution process of (NLP). Two different methods are proposed. The projection method guarantees consistency within each iteration, whereas the relaxation method achieves consistency only at an optimal solution. An illustrative example completes this article.     

Abort landing in the presence of windshear as a minimax optimal control problem,part 1: Necessary conditions

The landing of a passenger aircraft in the presence of windshear is a threat to aviation safety. The present paper is concerned with the abort landing of an aircraft in such a serious situation. Mathematically, the flight maneuver can be described by a minimax optimal control problem. By transforming this minimax problem into an optimal control problem of standard form, a state constraint has to be taken into account which is of order three. Moreover, two additional constraints, a first-order state constraint and a control variable constraint, are imposed upon the model. Since the only control variable appears linearly, the Hamiltonian is not regular. Thus, well-known existence theorems about the occurrence of boundary arcs and boundary points cannot be applied. Numerically, this optimal control problem is solved by means of the multiple shooting method in connection with an appropriate homotopy strategy. The solution obtained here satisfies all the sharp necessary conditions including those depending on the sign of certain multipliers. The trajectory consists of bang-bang and singular subarcs, as well as boundary subarcs induced by the two state constraints. The occurrence of boundary arcs is known to be impossible for regular Hamiltonians and odd-ordered state constraints if the order exceeds two. Additionally, a boundary point also occurs where the third-order state constraint is active. Such a situation is known to be the only possibility for odd-ordered state constraints to be active if the order exceeds two and if the Hamiltonian is regular. Because of the complexity of the optimal control, this single problem combines many of the features that make this kind of optimal control problems extremely hard to solve. Moreover, the problem contains nonsmooth data arising from the approximations of the aerodynamic forces and the distribution of the wind velocity components. Therefore, the paper can serve as some sort of user's guide to solve inequality constrained real-life optimal control problems by multiple shooting.An extended abstract of this paper was presented at the 8th IFAC Workshop on Control Applications of Nonlinear Programming and Optimization, Paris, France, 1989 (see Ref. 1).This paper is dedicated to Professor Hans J. Stetter on the occasion of his 60th birthday.     

Direct methods with maximal lower bound for mixed-integer optimal control problems

Many practical optimal control problems include discrete decisions. These may be either time-independent parameters or time-dependent control functions as gears or valves that can only take discrete values at any given time. While great progress has been achieved in the solution of optimization problems involving integer variables, in particular mixed-integer linear programs, as well as in continuous optimal control problems, the combination of the two is yet an open field of research. We consider the question of lower bounds that can be obtained by a relaxation of the integer requirements. For general nonlinear mixed-integer programs such lower bounds typically suffer from a huge integer gap. We convexify (with respect to binary controls) and relax the original problem and prove that the optimal solution of this continuous control problem yields the best lower bound for the nonlinear integer problem. Building on this theoretical result we present a novel algorithm to solve mixed-integer optimal control problems, with a focus on discrete-valued control functions. Our algorithm is based on the direct multiple shooting method, an adaptive refinement of the underlying control discretization grid and tailored heuristic integer methods. Its applicability is shown by a challenging application, the energy optimal control of a subway train with discrete gears and velocity limits.      

Distributed optimal control of the viscous Burgers equation via a Legendre pseudo‐spectral approach

This paper presents a computational technique based on the pseudo‐spectral method for the solution of distributed optimal control problem for the viscous Burgers equation. By using pseudo‐spectral method, the problem is converted to a classical optimal control problem governed by a system of ordinary differential equations, which can be solved by well‐developed direct or indirect methods. For solving the resulting optimal control problem, we present an indirect method by deriving and numerically solving the first‐order optimality conditions. Numerical tests involving both unconstrained and constrained control problems are considered. Copyright © 2015 John Wiley & Sons, Ltd.     

Direct and indirect methods for trajectory optimization

This paper gives a brief list of commonly used direct and indirect efficient methods for the numerical solution of optimal control problems. To improve the low accuracy of the direct methods and to increase the convergence areas of the indirect methods we suggest a hybrid approach. For this a special direct collocation method is presented. In a hybrid approach this direct method can be used in combination with multiple shooting. Numerical examples illustrate the direct method and the hybrid approach.     

An extended quasilinearization algorithm

The quasilinearization algorithm for the solution of two-point boundary-value problems is extended to handle a general class of multipoint boundary value problems involving multiple subarcs, state and/or control variable inequality constraints, and discontinuous state and/or adjoint variables. The corner and final times are unspecified since they are implicitly defined by the satisfaction of subarc stopping conditions. The inequality constraints are handled directly without the use of penalty functions. The extended algorithm is applied to a discontinuous version of the brachistochrone problem, and good convergence properties are obtained.This research was supported in part by AFOSR Grant No. 72–2166.     

Optimal Evasion from a Pursuer with Delayed Information

A class of prescribed duration pursuit–evasion problems with first-order acceleration dynamics and bounded controls is considered. In this class, the pursuer has delayed information on the lateral acceleration of the evader, but knows perfectly the other state variables. Moreover, the pursuer applies a strategy derived from the perfect information pursuit–evasion game solution. Assuming that the evader has perfect information on all the state variables as well as on the delay of the pursuer and its strategy, an optimal evasion problem is formulated. The necessary optimality conditions indicate that the evader optimal control has a bang–bang structure. Based on this result, two particular cases of the pursuer strategy (continuous and piecewise continuous in the state variables) are considered for the solution of the optimal evasion problem. In the case of the continuous pursuer strategy, the switch point of the optimal control can be obtained as a root of the switch function. However, in the case of the piecewise continuous (bang–bang) pursuer strategy, this method fails, because of the discontinuity of the switch function at this very point. In this case, a direct method for obtaining the switch point, based on the structure of the solution, is proposed. Numerical results illustrating the theoretical analysis are presented leading to a comparison of the two cases.     

The Lie-Group Shooting Method for Solving Multi-dimensional Nonlinear Boundary Value Problems

This paper presents a Lie-group shooting method for the numerical solutions of multi-dimensional nonlinear boundary-value problems, which may exhibit multiple solutions. The Lie-group shooting method is a powerful technique to search unknown initial conditions through a single parameter, which is determined by matching the multiple targets through a minimum of an appropriately defined measure of the mis-matching error to target equations. Several numerical examples are examined to show that the novel approach is highly efficient and accurate. The number of solutions can be identified in advance, and all possible solutions can be numerically integrated by using the fourth-order Runge–Kutta method. We also apply the Lie-group shooting method to a numerical solution of an optimal control problem of the Duffing oscillator.     

A time-domain decomposition iterative method for the solution of distributed linear quadratic optimal control problems

We study a class of time-domain decomposition-based methods for the numerical solution of large-scale linear quadratic optimal control problems. Our methods are based on a multiple shooting reformulation of the linear quadratic optimal control problem as a discrete-time optimal control (DTOC) problem. The optimality conditions for this DTOC problem lead to a linear block tridiagonal system. The diagonal blocks are invertible and are related to the original linear quadratic optimal control problem restricted to smaller time-subintervals. This motivates the application of block Gauss–Seidel (GS)-type methods for the solution of the block tridiagonal systems. Numerical experiments show that the spectral radii of the block GS iteration matrices are larger than one for typical applications, but that the eigenvalues of the iteration matrices decay to zero fast. Hence, while the GS method is not expected to convergence for typical applications, it can be effective as a preconditioner for Krylov-subspace methods. This is confirmed by our numerical tests.A byproduct of this research is the insight that certain instantaneous control techniques can be viewed as the application of one step of the forward block GS method applied to the DTOC optimality system.     

Exploiting the Special Structure for Real‐Time Control of Optimal Control Problems with Linear Controls: Numerical Experience

Often optimal control problems possess control variables appearing linearly in the dynamics, the objective function and the constraints. The special bang‐bang and singular structure of the optimal control is exploited to formulate a nonlinear programming problem (NLP)w ith variables in the switching points and singular subarcs of the controls. This method has several advantages: The dimension of the resulting NLP problem is considerably reduced compared to usual direct optimization methods, several constraints can be neglected, and a parametric sensitivity analysis and real‐time control with respect to the switching points can be performed.     

Singular Arcs in the Generalized Goddard’s Problem

We investigate variants of Goddard’s problems for nonvertical trajectories. The control is the thrust force, and the objective is to maximize a certain final cost, typically, the final mass. In this article, performing an analysis based on the Pontryagin maximum principle, we prove that optimal trajectories may involve singular arcs (along which the norm of the thrust is neither zero nor maximal), that are computed and characterized. Numerical simulations are carried out, both with direct and indirect methods, demonstrating the relevance of taking into account singular arcs in the control strategy. The indirect method that we use is based on our previous theoretical analysis and consists in combining a shooting method with an homotopic method. The homotopic approach leads to a quadratic regularization of the problem and is a way to tackle the problem of nonsmoothness of the optimal control. Support from the French Space Agency CNES (Centre National d’Etudes Spatial) is gratefully acknowledged.     

Numerical solution of singular control problems using multiple shooting techniques

Algorithms for calculating the junction points between optimal nonsingular and singular subarcs of singular control problems are developed. The algorithms consist in formulating appropriate initialvalue and boundary-value problems; the boundary-value problems are solved with the method of multiple shooting. Two examples are detailed to illustrate the proposed numerical methods.The author would like to thank Professor Dr. R. Bulirsch, who stimulated and encouraged this work, which is part of the author's dissertation.     

Multiple shooting methods for parabolic optimal control problems with control constraints

In the context of ordinary differential equations, shooting techniques are a state-of-the-art solver component, whereas their application in the framework of partial differential equations (PDE) is still at an early stage. We present two multiple shooting approaches for optimal control problems (OCP) governed by parabolic PDE. Direct and indirect shooting for PDE optimal control stem from the same extended problem formulation. Our approach reveals that they are structurally similar but show major differences in their algorithmic realizations. In the presented numerical examples we cover a nonlinear parabolic optimal control problem with additional control constraints. (© 2015 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Numerical solution of minimax optimal control problems by multiple shooting technique

This paper presents the application of the multiple shooting technique to minimax optimal control problems (optimal control problems with Chebyshev performance index). A standard transformation is used to convert the minimax problem into an equivalent optimal control problem with state variable inequality constraints. Using this technique, the highly developed theory on the necessary conditions for state-restricted optimal control problems can be applied advantageously. It is shown that, in general, these necessary conditions lead to a boundary-value problem with switching conditions, which can be treated numerically by a special version of the multiple shooting algorithm. The method is tested on the problem of the optimal heating and cooling of a house. This application shows some typical difficulties arising with minimax optimal control problems, i.e., the estimation of the switching structure which is dependent on the parameters of the problem. This difficulty can be overcome by a careful application of a continuity method. Numerical solutions for the example are presented which demonstrate the efficiency of the method proposed.     

Maximin Approach to the Ship Collision Avoidance Problem via Multiple-Subarc Sequential Gradient-Restoration Algorithm

The ideal strategy for ship collision avoidance under emergency conditions is to maximize wrt the controls the timewise minimum distance between a host ship and an intruder ship. This is a maximin problem or Chebyshev problem of optimal control in which the performance index being maximinimized is the distance between the two ships. Based on the multiple-subarc sequential gradient-restoration algorithm, a new method for solving the maximin problem is developed.Key to the new method is the observation that, at the maximin point, the time derivative of the performance index must vanish. With the zero derivative condition being treated as an inner boundary condition, the maximin problem can be converted into a Bolza problem in which the performance index, evaluated at the inner boundary, is being maximized wrt the controls. In turn, the Bolza problem with an added inner boundary condition can be solved via the multiple-subarc sequential gradient-restoration algorithm (SGRA).The new method is applied to two cases of the collision avoidance problem: collision avoidance between two ships moving along the same rectilinear course and collision avoidance between two ships moving along orthogonal courses. For both cases, we are basically in the presence of a two-subarc problem, the first subarc corresponding to the avoidance phase of the maneuver and the second subarc corresponding to the recovery phase. For stiff systems, the robustness of the multiple-subarc SGRA can be enhanced via increase in the number of subarcs. For the ship collision avoidance problem, a modest increase in the number of subarcs from two to three (one subarc in the avoidance phase, two subarcs in the recovery phase) helps containing error propagation and achieving better convergence results.