Multiple-Subarc Gradient-Restoration Algorithm, Part 2: Application to a Multistage Launch Vehicle Design

In Part 1 (see Ref. 2), a multiple-subarc gradient-restoration algorithm (MSGRA) was developed with the intent of enhancing the robustness of gradient-restoration algorithms and also enlarging the field of applications. Indeed, MSGRA can be applied to optimal control problems involving multiple subsystems as well as discontinuities in the state and control variables at the interface between contiguous subsystems.In Part 2 (this paper), MSGRA is applied to compute the optimal trajectory for a multistage launch vehicle design, specifically, a rocket-powered spacecraft ascending from the Earth surface to a low Earth orbit (LEO). Single-stage, double-stage, and triple-stage configurations are considered. For multistage configurations, discontinuities in the mass occur at the interfaces between consecutive stages.The numerical results show that, given the current levels of the engine specific impulse and spacecraft structural factor, the single-stage version is not feasible at this time, while the double-stage and triple-stage versions are feasible. Further increases in the specific impulse and decreases in the structural factor are needed if the single-stage configuration has to become feasible.Also, the numerical results show that the optimal trajectory requires initially maximum thrust, followed by modulated thrust so as to satisfy the maximum acceleration constraint, followed by nearly zero thrust for coasting flight, followed by a final burst with moderate thrust so as to increase the spacecraft velocity to the circular velocity needed for LEO insertion. The above properties of the optimal thrust time history are useful for developing the guidance scheme approximating in real time the optimal trajectory for a launch vehicle design.     

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.     

Supplementary optimality properties of the restoration phase of sequential gradient-restoration algorithms for optimal control problems

In this paper, sequential gradient-restoration algorithms for optimal control problems are considered, and attention is focused on the restoration phase. It is shown that the Lagrange multipliers associated with the restoration phase not only solve the auxiliary minimization problem of the restoration phase, but are also endowed with a supplementary optimality property: they minimize a special functional, quadratic in the multipliers, subject to the multiplier differential equations and boundary conditions, for given state, control, and parameter.Dedicated to L. CesariThis work was supported by a grant of the National Science Foundation.     

Recent advances in gradient algorithms for optimal control problems

This paper summarizes recent advances in the area of gradient algorithms for optimal control problems, with particular emphasis on the work performed by the staff of the Aero-Astronautics Group of Rice University. The following basic problem is considered: minimize a functionalI which depends on the statex(t), the controlu(t), and the parameter π. Here,I is a scalar,x ann-vector,u anm-vector, and π ap-vector. At the initial point, the state is prescribed. At the final point, the statex and the parameter π are required to satisfyq scalar relations. Along the interval of integration, the state, the control, and the parameter are required to satisfyn scalar differential equations. First, the sequential gradient-restoration algorithm and the combined gradient-restoration algorithm are presented. The descent properties of these algorithms are studied, and schemes to determine the optimum stepsize are discussed. Both of the above algorithms require the solution of a linear, two-point boundary-value problem at each iteration. Hence, a discussion of integration techniques is given. Next, a family of gradient-restoration algorithms is introduced. Not only does this family include the previous two algorithms as particular cases, but it allows one to generate several additional algorithms, namely, those with alternate restoration and optional restoration. Then, two modifications of the sequential gradient-restoration algorithm are presented in an effort to accelerate terminal convergence. In the first modification, the quadratic constraint imposed on the variations of the control is modified by the inclusion of a positive-definite weighting matrix (the matrix of the second derivatives of the Hamiltonian with respect to the control). The second modification is a conjugate-gradient extension of the sequential gradient-restoration algorithm. Next, the addition of a nondifferential constraint, to be satisfied everywhere along the interval of integration, is considered. In theory, this seems to be only a minor modification of the basic problem. In practice, the change is considerable in that it enlarges dramatically the number and variety of problems of optimal control which can be treated by gradient-restoration algorithms. Indeed, by suitable transformations, almost every known problem of optimal control theory can be brought into this scheme. This statement applies, for instance, to the following situations: (i) problems with control equality constraints, (ii) problems with state equality constraints, (iii) problems with equality constraints on the time rate of change of the state, (iv) problems with control inequality constraints, (v) problems with state inequality constraints, and (vi) problems with inequality constraints on the time rate of change of the state. Finally, the simultaneous presence of nondifferential constraints and multiple subarcs is considered. The possibility that the analytical form of the functions under consideration might change from one subarc to another is taken into account. The resulting formulation is particularly relevant to those problems of optimal control involving bounds on the control or the state or the time derivative of the state. For these problems, one might be unwilling to accept the simplistic view of a continuous extremal arc. Indeed, one might want to take the more realistic view of an extremal arc composed of several subarcs, some internal to the boundary being considered and some lying on the boundary. The paper ends with a section dealing with transformation techniques. This section illustrates several analytical devices by means of which a great number of problems of optimal control can be reduced to one of the formulations presented here. In particular, the following topics are treated: (i) time normalization, (ii) free initial state, (iii) bounded control, and (iv) bounded state.     

Guidance Trajectories for Spacecraft Rendezvous

In a previous paper of Miele et al. (J. Optim. Theory Appl. 132(1), 2007), we employed the single-subarc sequential gradient-restoration algorithm to optimize the three-dimensional rendezvous between a target spacecraft in a planar circular orbit and a chaser spacecraft with an initial separation distance and separation velocity. The achieved continuous solutions are characterized by two, three, or four subarcs depending on the performance index (time, fuel) and the constraints. In this paper, based on the solutions in Miele et al. (J. Optim. Theory Appl. 132(1), 2007), we employ the multiple-subarc sequential gradient-restoration algorithm to produce pieced guidance trajectories implementable in real time via constant control components. In other words, in this investigation, we force the controls to behave as parameters in each subarc. With the above understanding, we investigate four problems: (P1) minimum time, fuel free; (P2) minimum fuel, time free; (P3) minimum time, fuel given; (P4) minimum fuel, time given. Problem P1 results in a two-subarc solution, each subarc with constant controls: a max-thrust accelerating subarc followed by a max-thrust braking subarc. Problem P2 results in a four-subarc solution, each subarc with constant controls: an initial coasting subarc, followed by a max-thrust braking subarc, followed by another coasting subarc, followed by another max-thrust braking subarc. Problems P3 and P4 result in two, three, or four-subarc solutions depending on the performance index and the constraints, albeit with constant controls in each subarc. For each of the problems studied, the performance index of the multiple-subarc pieced guidance trajectory approximates well the performance index of the single-subarc continuous optimal trajectory of Miele et al. (J. Optim. Theory Appl. 132(1), 2007) as well as the performance index of the multiple-subarc pieced optimal trajectory: the pairwise relative differences in performance index are less than 1/100. This research was supported by NSF under Grant CMS-0218878.     

Supplementary optimality properties of gradient-restoration algorithms for optimal control problems

In this paper, sequential gradient-restoration algorithms for optimal control problems are considered, and attention is focused on the gradient phase. It is shown that the Lagrange multipliers associated with the gradient phase not only solve the auxiliary minimization problem of the gradient phase, but are also endowed with a supplementary optimality property: they minimize the error in the optimality conditions, subject to the multiplier differential equations and boundary conditions, for given state, control, and parameter.Dedicated to R. BellmanThis work was supported by the National Science Foundation, Grant No. ENG-79-18667.     

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.     

Feasible Direction Algorithm for Optimal Control Problems with State and Control Constraints: Implementation

In this paper, we describe the implementation aspects of an optimization algorithm for optimal control problems with control, state, and terminal constraints presented in our earlier paper. The important aspect of the implementation is that, in the direction-finding subproblems, it is necessary only to impose the state constraint at relatively few points in the time involved. This contributes significantly to the algorithmic efficiency. The algorithm is applied to solve several optimal control problems, including the problem of the abort landing of an aircraft in the presence of windshear.     

城市道路交通信号实时控制的数学模型与算法研究

研究了交通信号的实时配时控制问题.建立了在已有交通设施条件下,控制信号具有线性约束的非线性实时配时系统优化模型,设计了与模型相适应的实时CLY系列算法.重点讨论了点控制问题,建立了相应的数学优化模型,设计了CLY-Point1算法求解.还对线控制问题和面控制问题,建立了多层优化控制模型,并设计CLY-Point2、CLY-Line和CLY-Area算法进行求解.数值模拟结果表明,CLY系列算法具有很强的实时性,车辆平均等待时间比固定配时减少了约20%.     

A Hybrid Genetic Algorithm with Boltzmann Convergence Properties

Stochastic global search algorithms such as genetic algorithms are used to attack difficult combinatorial optimization problems. However, genetic algorithms suffer from the lack of a convergence proof. This means that it is difficult to establish reliable algorithm braking criteria without extensive a priori knowledge of the solution space. The hybrid genetic algorithm presented here combines a genetic algorithm with simulated annealing in order to overcome the algorithm convergence problem. The genetic algorithm runs inside the simulated annealing algorithm and provides convergence via a Boltzmann cooling process. The hybrid algorithm was used successfully to solve a classical 30-city traveling salesman problem; it consistently outperformed both a conventional genetic algorithm and a conventional simulated annealing algorithm. This work was supported by the University of Colorado at Colorado Springs.     

A Domain Embedding Method Using the Optimal Distributed Control and a Fast Algorithm

We propose a domain embedding method to solve second order elliptic problems in arbitrary two-dimensional domains. The method is based on formulating the problem as an optimal distributed control problem inside a disc in which the arbitrary domain is embedded. The optimal distributed control problem inside the disc is solved rapidly using a fast algorithm developed by Daripa et al. [3,7,10–12]. The arbitrary domains can be simply or multiply connected and the proposed method can be applied, in principle, to a large number of elliptic problems. Numerical results obtained for Dirichlet problems associated with the Poisson equation in simply and multiply connected domains are presented. The computed solutions are found to be in good agreement with the exact solutions with moderate number of grid points in the domain.     

Optimal control of bioprocess systems using hybrid numerical optimization algorithms

In the paper, we consider the bioprocess system optimal control problem. Generally speaking, it is very difficult to solve this problem analytically. To obtain the numerical solution, the problem is transformed into a parameter optimization problem with some variable bounds, which can be efficiently solved using any conventional optimization algorithms, e.g. the improved Broyden–Fletcher–Goldfarb–Shanno algorithm. However, in spite of the improved Broyden–Fletcher–Goldfarb–Shanno algorithm is very efficient for local search, the solution obtained is usually a local extremum for non-convex optimal control problems. In order to escape from the local extremum, we develop a novel stochastic search method. By performing a large amount of numerical experiments, we find that the novel stochastic search method is excellent in exploration, while bad in exploitation. In order to improve the exploitation, we propose a hybrid numerical optimization algorithm to solve the problem based on the novel stochastic search method and the improved Broyden–Fletcher–Goldfarb–Shanno algorithm. Convergence results indicate that any global optimal solution of the approximate problem is also a global optimal solution of the original problem. Finally, two bioprocess system optimal control problems illustrate that the hybrid numerical optimization algorithm proposed by us is low time-consuming and obtains a better cost function value than the existing approaches.     

Optimal trajectories for aeroassisted,coplanar orbital transfer

This paper considers both classical and minimax problems of optimal control which arise in the study of aeroassisted, coplanar orbital transfer. The maneuver considered involves the coplanar transfer from a high planetary orbit to a low planetary orbit. An example is the HEO-to-LEO transfer of a spacecraft, where HEO denotes high Earth orbit and LEO denotes low Earth orbit. In particular, HEO can be GEO, a geosynchronous Earth orbit.The basic idea is to employ the hybrid combination of propulsive maneuvers in space and aerodynamic maneuvers in the sensible atmosphere. Hence, this type of flight is also called synergetic space flight. With reference to the atmospheric part of the maneuver, trajectory control is achieved by means of lift modulation. The presence of upper and lower bounds on the lift coefficient is considered.Within the framework of classical optimal control, the following problems are studied: (P1) minimize the energy required for orbital transfer; (P2) minimize the time integral of the heating rate; (P3) minimize the time of flight during the atmospheric portion of the trajectory; (P4) maximize the time of flight during the atmospheric portion of the trajectory; (P5) minimize the time integral of the square of the path inclination; and (P6) minimize the sum of the squares of the entry and exit path inclinations. Problems (P1) through (P6) are Bolza problems of optimal control.Within the framework of minimax optimal control, the following problems are studied: (Q1) minimize the peak heating rate; (Q2) minimize the peak dynamic pressure; and (Q3) minimize the peak altitude drop. Problems (Q1) through (Q3) are Chebyshev problems of optimal control, which can be converted into Bolza problems by suitable transformations.Numerical solutions for Problems (P1)–(P6) and Problems (Q1)–(Q3) are obtained by means of the sequential gradient-restoration algorithm for optimal control problems. The engineering implications of these solutions are discussed. In particular, the merits of nearly-grazing trajectories are considered.This research was supported by the Jet Propulsion Laboratory, Contract No. 956415. The authors are indebted to Dr. K. D. Mease, Jet Propulsion Laboratory, for helpful discussions. This paper is a condensation of the investigation reported in Ref. 1.     

On a Constrained Optimal Location Algorithm

In problems of optimal location, one seeks a position or location that optimizes a particular objective function; this objective function typically relates location and distances to a fixed point set. When one's search is restricted to a given set, we refer to this as a constrained optimal location problem. For a finite point set A, there exist numerous finite algorithms to solve optimal location problems. In this paper we demonstrate how an algorithm, solving optimal location problems in inner-product spaces, can be modified to solve certain constrained optimal location problems. We then apply this modification to a particularly simple (and easily implemented) algorithm and investigate the complexity of the result. In particular we improve a known estimate from exponential to polynomial.     

Summary and comparison of gradient-restoration algorithms for optimal control problems

This paper considers the problem of minimizing a functionalI which depends on the statex(t), the controlu(t), and the parameter . Here,I is a scalar,x ann-vector,u anm-vector, and ap-vector. At the initial point, the state is prescribed. At the final point, the state and the parameter are required to satisfyq scalar relations. Along the interval of integration, the state, the control, and the parameter are required to satisfyn scalar differential equations.Four types of gradient-restoration algorithms are considered, and their relative efficiency (in terms of number of iterations for convergence) is evaluated. The algorithms being considered are as follows: sequential gradient-restoration algorithm, complete restoration (SGRA-CR), sequential gradient-restoration algorithm, incomplete restoration (SGRA-IR), combined gradient-restoration algorithm, no restoration (CGRA-NR), and combined gradient-restoration algorithm, incomplete restoration (CGRA-IR).Evaluation of these algorithms is accomplished through six numerical examples. The results indicate that (i) the inclusion of a restoration phase is necessary for rapid convergence and (ii) while SGRA-CR is the most desirable algorithm if feasibility of the suboptimal solutions is required, rapidity of convergence to the optimal solution can be increased if one employs algorithms with incomplete restoration, in particular, CGRA-IR.This research was supported by the Office of Scientific Research, Office of Aerospace Research, United States Air Force, Grant No. AF-AFOSR-72-2185.     

Pareto memetic algorithm for multiple objective optimization with an industrial application

Multiple objective combinatorial optimization problems are difficult to solve and often, exact algorithms are unable to produce optimal solutions. The development of multiple objective heuristics was inspired by the need to quickly produce acceptable solutions. In this paper, we present a new multiple objective Pareto memetic algorithm called PMS^MO. The PMS^MO algorithm incorporates an enhanced fine-grained fitness assignment, a double level archiving process and a local search procedure to improve performance. The performance of PMS^MO is benchmarked against state-of-the-art algorithms using 0–1 multi-dimensional multiple objective knapsack problem from the literature and an industrial scheduling problem from the aluminum industry.     

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.     

Anchoring conditions for the sequential gradient-restoration algorithm and the modified quasilinearization algorithm for optimal control problems with bounded state

In Refs. 1–2, the sequential gradient-restoration algorithm and the modified quasilinearization algorithm were developed for optimal control problems with bounded state. These algorithms have a basic property: for a subarc lying on the state boundary, the state boundary equations are satisfied at every iteration, if they are satisfied at the beginning of the computational process. Thus, the subarc remains anchored on the state boundary. In this paper, the anchoring conditions employed in Refs. 1–2 are derived.This research was supported by the Office of Scientific Research, Office of Aerospace Research, United States Air Force, Grant No. AF-AFOSR-72-2185.     

A Schwarz domain decomposition method with gradient projection for optimal control governed by elliptic partial differential equations

A domain decomposition method (DDM) is presented to solve the distributed optimal control problem. The optimal control problem essentially couples an elliptic partial differential equation with respect to the state variable and a variational inequality with respect to the constrained control variable. The proposed algorithm, called SA-GP algorithm, consists of two iterative stages. In the inner loops, the Schwarz alternating method (SA) is applied to solve the state and co-state variables, and in the outer loops the gradient projection algorithm (GP) is adopted to obtain the control variable. Convergence of iterations depends on both the outer and the inner loops, which are coupled and affected by each other. In the classical iteration algorithms, a given tolerance would be reached after sufficiently many iteration steps, but more iterations lead to huge computational cost. For solving constrained optimal control problems, most of the computational cost is used to solve PDEs. In this paper, a proposed iterative number independent of the tolerance is used in the inner loops so as to save a lot of computational cost. The convergence rate of L²-error of control variable is derived. Also the analysis on how to choose the proposed iteration number in the inner loops is given. Some numerical experiments are performed to verify the theoretical results.     

Solving Convex MINLP Optimization Problems Using a Sequential Cutting Plane Algorithm

In this article we look at a new algorithm for solving convex mixed integer nonlinear programming problems. The algorithm uses an integrated approach, where a branch and bound strategy is mixed with solving nonlinear programming problems at each node of the tree. The nonlinear programming problems, at each node, are not solved to optimality, rather one iteration step is taken at each node and then branching is applied. A Sequential Cutting Plane (SCP) algorithm is used for solving the nonlinear programming problems by solving a sequence of linear programming problems. The proposed algorithm generates explicit lower bounds for the nodes in the branch and bound tree, which is a significant improvement over previous algorithms based on QP techniques. Initial numerical results indicate that the described algorithm is a competitive alternative to other existing algorithms for these types of problems.