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.     

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.     

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.     

Piecewise-Linear Pathways to the Optimal Solution Set in Linear Programming

An optimal control problem with four linear controls describing a sophisticated concern model is investigated. The numerical solution of this problem by combination of a direct collocation and an indirect multiple shooting method is presented and discussed. The approximation provided by the direct method is used to estimate the switching structure caused by the four controls occurring linearly. The optimal controls have bang-bang subarcs as well as constrained and singular subarcs. The derivation of necessary conditions from optimal control theory is aimed at the subsequent application of an indirect multiple shooting method but is also interesting from a mathematical point of view. Due to the linear occurrence of the controls, the minimum principle leads to a linear programming problem. Therefore, the Karush–Kuhn–Tucker conditions can be used for an optimality check of the solution obtained by the indirect method.     

Relaxation of Minimax Optimal Control Problems with Infinite Horizon

A minimax optimal control problem with infinite horizon is studied. We analyze a relaxation of the controls, which allows us to consider a generalization of the original problem that not only has existence of an optimal control but also enables us to approximate the infinite-horizon problem with a sequence of finite-horizon problems. We give a set of conditions that are sufficient to solve directly, without relaxation, the infinite-horizon problem as the limit of finite-horizon problems.     

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.     

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.     

Variable-metric technique for the solution of affinely parametrized nondifferentiable optimal design problems

The composite functions which appear in various optimal feedback system design problems, as well as in open-loop optimal control problems, can lead to severely ill-conditioned minimax problems. This ill-conditioning can cause first-order minimax algorithms to converge very slowly. We propose a variable-metric technique which substantially mitigates this ill-conditioning. The technique does not require the evaluation of second derivatives and can be used to speed the convergence of any first-order minimax algorithm which produces estimates of the optimal multipliers. Numerical experiments are presented which show that the variable-metric technique increases the speed of two algorithms.     

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.     

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.      

Bounded knapsack sharing

A bounded knapsack sharing problem is a maximin or minimax mathematical programming problem with one or more linear inequality constraints, an objective function composed of single variable continuous functions called tradeoff functions, and lower and upper bounds on the variables. A single constraint problem which can have negative or positive constraint coefficients and any type of continuous tradeoff functions (including multi-modal, multiple-valued and staircase functions) is considered first. Limiting conditions where the optimal value of a variable may be plus or minus infinity are explicitly considered. A preprocessor procedure to transform any single constraint problem to a finite form problem (an optimal feasible solution exists with finite variable values) is developed. Optimality conditions and three algorithms are then developed for the finite form problem. For piecewise linear tradeoff functions, the preprocessor and algorithms are polynomially bounded. The preprocessor is then modified to handle bounded knapsack sharing problems with multiple constraints. An optimality condition and algorithm is developed for the multiple constraint finite form problem. For multiple constraints, the time needed for the multiple constraint finite form algorithm is the time needed to solve a single constraint finite form problem multiplied by the number of constraints. Some multiple constraint problems cannot be transformed to multiple constraint finite form problems.     

Relaxation-based algorithms for minimax optimization problems with resource allocation applications

We consider minimax optimization problems where each term in the objective function is a continuous, strictly decreasing function of a single variable and the constraints are linear. We develop relaxation-based algorithms to solve such problems. At each iteration, a relaxed minimax problem is solved, providing either an optimal solution or a better lower bound. We develop a general methodology for such relaxation schemes for the minimax optimization problem. The feasibility tests and formulation of subsequent relaxed problems can be done by using Phase I of the Simplex method and the Farkas multipliers provided by the final Simplex tableau when the corresponding problem is infeasible. Such relaxation-based algorithms are particularly attractive when the minimax optimization problem exhibits additional structure. We explore special structures for which the relaxed problem is formulated as a minimax problem with knapsack type constraints; efficient algorithms exist to solve such problems. The relaxation schemes are also adapted to solve certain resource allocation problems with substitutable resources. There, instead of Phase I of the Simplex method, a max-flow algorithm is used to test feasibility and formulate new relaxed problems.Corresponding author.Work was partially done while visiting AT&T Bell Laboratories.     

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.     

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.     

Numerical solution of minimax problems of optimal control,part 2

In a previous paper (Part 1), we presented general transformation techniques useful to convert minimax problems of optimal control into the Mayer-Bolza problem of the calculus of variations [Problem (P)]. We considered two types of minimax problems: minimax problems of Type (Q), in which the minimax function depends on the state and does not depend on the control; and minimax problems of Type (R), in which the minimax function depends on both the state and the control. Both Problem (Q) and Problem (R) can be reduced to Problem (P).In this paper, the transformation techniques presented in Part 1 are employed in conjunction with the sequential gradient-restoration algorithm for solving optimal control problems on a digital computer. Both the single-subarc approach and the multiple-subarc approach are employed. Three test problems characterized by known analytical solutions are solved numerically.It is found that the combination of transformation techniques and sequential gradient-restoration algorithm yields numerical solutions which are quite close to the analytical solutions from the point of view of the minimax performance index. The relative differences between the numerical values and the analytical values of the minimax performance index are of order 10^–3 if the single-subarc approach is employed. These relative differences are of order 10^–4 or better if the multiple-subarc approach is employed.This research was supported by the National Science Foundation, Grant No. ENG-79-18667, and by Wright-Patterson Air Force Base, Contract No. F33615-80-C3000. This paper is a condensation of the investigations reported in Refs. 1–7. The authors are indebted to E. M. Coker and E. M. Sims for analytical and computational assistance.     

A general sufficiency theorem for minimax control

This paper considers optimal control problems where there is uncertainty in the differential equations describing the system. A minimax optimality criterion is used, and sufficient conditions for a control to be a minimax control are presented. These conditions are more general than those given in Refs. 1 and 2.This research was supported by AFOSR under Grant No. 76-2923.     

Numerical solution of minimax problems of optimal control,part 1

This paper contains general transformation techniques useful to convert minimax problems of optimal control into the Mayer-Bolza problem of the calculus of variations [Problem (P)]. We consider two types of minimax problems: minimax problems of Type (Q), in which the minimax function depends on the state and does not depend on the control; and minimax problems of Type (R), in which the minimax function depends on both the state and the control. Both Problem (Q) and Problem (R) can be reduced to Problem (P).For Problem (Q), we exploit the analogy with a bounded-state problem in combination with a transformation of the Jacobson type. This requires the proper augmentation of the state vectorx(t), the control vectoru(t), and the parameter vector , as well as the proper augmentation of the constraining relations. As a result of the transformation, the unknown minimax value of the performance index becomes a component of the parameter vector being optimized.For Problem (R), we exploit the analogy with a bounded-control problem in combination with a transformation of the Valentine type. This requires the proper augmentation of the control vectoru(t) and the parameter vector , as well as the proper augmentation of the constraining relations. As a result of the transformation, the unknown minimax value of the performance index becomes a component of the parameter vector being optimized.In a subsequent paper (Part 2), the transformation techniques presented here are employed in conjunction with the sequential gradient-restoration algorithm for solving optimal control problems on a digital computer; both the single-subarc approach and the multiple-subarc approach are discussed.This research was supported by the National Science Foundation, Grant No. ENG-79-18667, and by Wright-Patterson Air Force Base, Contract No. F33615-80-C3000. This paper is a condensation of the investigations reported in Refs. 1–7. The authors are indebted to E. M. Coker and E. M. Sims for analytical and computational assistance.     

Optimal Control and Applications to Aerospace: Some Results and Challenges

This article surveys the usual techniques of nonlinear optimal control such as the Pontryagin Maximum Principle and the conjugate point theory, and how they can be implemented numerically, with a special focus on applications to aerospace problems. In practice the knowledge resulting from the maximum principle is often insufficient for solving the problem, in particular because of the well-known problem of initializing adequately the shooting method. In this survey article it is explained how the usual tools of optimal control can be combined with other mathematical techniques to improve significantly their performances and widen their domain of application. The focus is put onto three important issues. The first is geometric optimal control, which is a theory that has emerged in the 1980s and is combining optimal control with various concepts of differential geometry, the ultimate objective being to derive optimal synthesis results for general classes of control systems. Its applicability and relevance is demonstrated on the problem of atmospheric reentry of a space shuttle. The second is the powerful continuation or homotopy method, consisting of deforming continuously a problem toward a simpler one and then of solving a series of parameterized problems to end up with the solution of the initial problem. After having recalled its mathematical foundations, it is shown how to combine successfully this method with the shooting method on several aerospace problems such as the orbit transfer problem. The third one consists of concepts of dynamical system theory, providing evidence of nice properties of the celestial dynamics that are of great interest for future mission design such as low-cost interplanetary space missions. The article ends with open problems and perspectives.     

Optimal Infinite-Horizon Multicriteria Feedback Control of Stationary Systems with Minimax Objectives and Bounded Disturbances

This article presents a methodology for exploring the solution surface in a class of multicriteria infinite-horizon closed-loop optimal control problems with bounded disturbances and minimax objectives. The maximum is taken with respect to both time and all sequences of disturbances; that is, the value of a criterion is the maximal stage cost for the worst possible sequence of disturbances. It is assumed that the system and the cost functions are stationary. The proposed solution method is based on reference point approach and inverse mapping from the space of objectives into the space of control policies and their domains in state space.     

Solution differentiability for parametric nonlinear control problems with control-state constraints

This paper considers parametric nonlinear control problems subject to mixed control-state constraints. The data perturbations are modeled by a parameterp of a Banach space. Using recent second-order sufficient conditions (SSC), it is shown that the optimal solution and the adjoint multipliers are differentiable functions of the parameter. The proof blends numerical shooting techniques for solving the associated boundary-value problem with theoretical methods for obtaining SSC. In a first step, a differentiable family of extremals for the underlying parameteric boundary-value problem is constructed by assuming the regularity of the shooting matrix. Optimality of this family of extremals can be established in a second step when SSC are imposed. This is achieved by building a bridge between the variational system corresponding to the boundary-value problem, solutions of the associated Riccati ODE, and SSC.Solution differentiability provides a theoretical basis for performing a numerical sensitivity analysis of first order. Two numerical examples are worked out in detail that aim at reducing the considerable deficit of numerical examples in this area of research.This paper is dedicated to Professor J. Stoer on the occasion of his 60th birthday.The authors are indebted to K. Malanowski for helpful discussions.