Extensions in quasilinearization techniques for optimal control

This paper presents several extensions in quasilinearization techniques for optimal control problems. Techniques are developed that facilitate the application of quasilinearization to control problems where bounds on the controls exist. Toward this end, quadratic convergence for bounded continuous control is shown. A method for extending the region over which the method converges is presented, and the theoretical advantage of the extended method is shown. The work of Long is modified to provide more accurate integration while preserving its usefulness in solving problems where the final time is free. A companion paper presents computational results.This research was supported in part by the Air Force Office of Scientific Research, Grant No. AF-AFOSR-699-67.     

Modified quasilinearization algorithm for optimal control problems with bounded state

This paper considers the numerical solution of optimal control problems involving a functionalI subject to differential constraints, a state inequality constraint, and terminal constraints. The problem is to find the statex(t), the controlu(t), and the parameter so that the functional is minimized, while the constraints are satisfied to a predetermined accuracy.A modified quasilinearization algorithm is developed. Its main property is the descent property in the performance indexR, the cumulative error in the constraints and the optimality conditions. Modified quasilinearization differs from ordinary quasilinearization because of the inclusion of the scaling factor (or stepsize) in the system of variations. The stepsize is determined by a one-dimensional search on the performance indexR. Since the first variation R is negative, the decrease inR is guaranteed if is sufficiently small. Convergence to the solution is achieved whenR becomes smaller than some preselected value.Here, the state inequality constraint is handled in a direct manner. A predetermined number and sequence of subarcs is assumed and, for the time interval for which the trajectory of the system lies on the state boundary, the control is determined so that the state boundary is satisfied. The state boundary and the entrance conditions are assumed to be linear inx and , and the modified quasilinearization algorithm is constructed in such a way that the state inequality constraint is satisfied at each iteration and along all of the subarcs composing the trajectory.At first glance, the assumed linearity of the state boundary and the entrance conditions appears to be a limitation to the theory. Actually, this is not the case. The reason is that every constrained minimization problem can be brought to the present form through the introduction of additional state variables.In order to start the algorithm, some nominal functionsx(t),u(t), and nominal multipliers (t), (t), , must be chosen. In a real problem, the selection of the nominal functions can be made on the basis of physical considerations. Concerning the nominal multipliers, no useful guidelines have been available thus far. In this paper, an auxiliary minimization algorithm for selecting the multipliers optimally is presented: the performance indexR is minimized with respect to (t), (t), , . Since the functionalR is quadratically dependent on the multipliers, the resulting variational problem is governed by optimality conditions which are linear and, therefore, can be solved without difficulty.The numerical examples illustrating the theory demonstrate the feasibility as well as the rapidity of convergence of the technique developed in this paper.This research was supported by the Office of Scientific Research, Office of Aerospace Research, United States Air Force, Grant No. AF-AFOSR-72-2185. The authors are indebted to Dr. R. R. Iyer and Mr. A. K. Aggarwal for helpful discussions as well as analytical and numerical assistance. This paper is a condensation of the investigations described in Refs. 1–2.     

Modified quasilinearization algorithm for optimal control problems with nondifferential constraints

This paper considers the numerical solution of optimal control problems involving a functionalI subject to differential constraints, nondifferential constraints, and terminal constraints. The problem is to find the statex(t), the controlu(t), and the parameter π so that the functional is minimized, while the constraints are satisfied to a predetermined accuracy. A modified quasilinearization algorithm is developed. Its main property is the descent property in the performance indexR, the cumulative error in the constraints and the optimality conditions. Modified quasilinearization differs from ordinary quasilinearization because of the inclusion of the scaling factor (or stepsize) α in the system of variations. The stepsize is determined by a one-dimensional search on the performance indexR. Since the first variation δR is negative, the decrease inR is guaranteed if α is sufficiently small. Convergence to the solution is achieved whenR becomes smaller than some preselected value. In order to start the algorithm, some nominal functionsx(t),u(t), π and nominal multipliers λ(t), ρ(t), μ must be chosen. In a real problem, the selection of the nominal functions can be made on the basis of physical considerations. Concerning the nominal multipliers, no useful guidelines have been available thus far. In this paper, an auxiliary minimization algorithm for selecting the multipliers optimally is presented: the performance indexR is minimized with respect to λ(t), ρ(t), μ. Since the functionalR is quadratically dependent on the multipliers, the resulting variational problem is governed by optimality conditions which are linear and, therefore, can be solved without difficulty. To facilitate the numerical solution on digital computers, the actual time θ is replaced by the normalized timet, defined in such a way that the extremal arc has a normalized time length Δt=1. In this way, variable-time terminal conditions are transformed into fixed-time terminal conditions. The actual time τ at which the terminal boundary is reached is regarded to be a component of the parameter π being optimized. The present general formulation differs from that of Ref. 3 because of the inclusion of the nondifferential constraints to be satisfied everywhere over the interval 0?t?1. Its importance lies in that (i) many optimization problems arise directly in the form considered here, (ii) there are problems involving state equality constraints which can be reduced to the present scheme through suitable transformations, and (iii) there are some problems involving inequality constraints which can be reduced to the present scheme through the introduction of auxiliary variables. Numerical examples are presented for the free-final-time case. These examples demonstrate the feasibility as well as the rapidity of convergence of the technique developed in this paper.     

Modified quasilinearization algorithm for optimal control problems with nondifferential constraints and general boundary conditions

This paper considers the numerical solution of the problem of minimizing a functionalI, subject to differential constraints, nondifferential constraints, and general boundary conditions. It consists of finding the statex(t), the controlu(t), and the parameter so that the functionalI is minimized while the constraints are satisfied to a predetermined accuracy.The modified quasilinearization algorithm (MQA) is extended, so that it can be applied to the solution of optimal control problems with general boundary conditions, where the state is not explicitly given at the initial point.The algorithm presented here preserves the MQA descent property on the cumulative error. This error consists of the error in the optimality conditions and the error in the constraints.Three numerical examples are presented in order to illustrate the performance of the algorithm. The numerical results are discussed to show the feasibility as well as the convergence characteristics of the algorithm.This work was supported by the Electrical Research Institute of Mexico and by CONACYT, Consejo Nacional de Ciencia y Tecnologia, Mexico City, Mexico.     

Computational aspects of discrete-time optimal control

Our opinion is that a little-known technique called “differential dynamicprogramming” offers the potential of enormously expanding the scale of discrete-time optimal- control problems which are subject to numerical solution. Among the attractive features of this method are that no discretization of control or state space is used; the memory requirements grow as m² and the computational requirements as m³, with m being the dimension of the control variable; the successive approximations converge globally under lenient smoothness assumptions; and the convergence is quadratic if certain convexity assumptions hold. The contribution of the present paper is to demonstrate the practical merit of differential dynamic programming by reporting computational solutions to problems having as many as forty control variables and no particularly convenient structure. Additionally, we give a more algorithmically oriented presentation of the method than hitherto available, extend the basic methodto the nonconvex case, and give a proof of global convergence.     

Measure change techniques in optimal control

Fully and partially observed stochastic control of systems with nonlinear dynamics and terminal and running costs are considered. Measure changes are introduced which allow both state and observation dynamics to be thought of as linear. In the case when the terms of the cost have a special form the measure change transformation “cancels out” the nonlinearities and changes the original nonlinear problem into a classical LQG one and standard results can be applied. We also consider unnormalized conditional densities of the whole path as state variables and obtain dynamic programming and verification results. R. J. Elliott wishes to acknowledge support of the Natural Sciences and Engineering Research Council of Canada, Grant A7964.     

Computational and approximate methods of optimal control

Approximate methods of solving problems of optimal control are classified and analyzed, and their domain of applicability is indicated. Among the special problems the problem of the choice of optimal trajectories for aircraft is considered.Translated from Itogi Nauki i Tekhniki, Matematicheskii Analiz, Vol. 14, pp. 101–166, 1977.The authors of the survey are grateful to N. N. Bolotnik, M. Yu. Borodovskii, G. G. Egiyan, V. A. Korneev, V. M. Mamalyga, A. A. Mironov, Yu. R. Roshchin, and A. P. Seiranyan for their assistance in compiling the bibliography and to R. P. Soldatova and I. S. Kheiker for their help in the shaping of the paper.     

Modified quasilinearization and optimal initial choice of the multipliers part 2—Optimal control problems

This paper considers the problem of extremizing a functionalI which depends on the statex(t), the controlu(t), and the parameter . The state is ann-vector, the control is anm-vector, and the parameter is 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. A modified quasilinearization algorithm is developed; its main property is a descent property in the performance indexR, the cumulative error in the constraints and the optimum conditions.Modified quasilinearization differs from ordinary quasilinearization because of the inclusion of a scaling factor (or stepsize) in the system of variations. The stepsize is determined by a one-dimensional search so as to ensure the decrease in the performance indexR; this can be achieved through a bisection process starting from = 1. Convergence is achieved whenR becomes smaller than some preselected value.In order to start the algorithm, some nominal functionsx(t),u(t), and multipliers (t), must be chosen. In a real problem, the selection ofx(t),u(t), can be made on the basis of physical considerations. Concerning (t) and , no useful guidelines have been available thus far. In this paper, a method for selecting (t) and optimally is presented: the performance indexR is minimized with respect to (t) and . Since the functionalR is quadratically dependent on (t) and , the resulting variational problem is governed by Euler equations and boundary conditions which are linear.Two numerical examples are presented, and it is shown that, if the initial multipliers (t) and are chosen optimally, modified quasilinearization converges rapidly to the solution. On the other hand, if the initial multipliers are chosen arbitrarily, modified quasilinearization may or may not converge to the solution. From the examples, it is concluded that the beneficial effects associated with the optimal initial choice of the multipliers (t) and lie primarily in increasing the likelihood of convergence rather than accelerating convergence. However, this optimal choice does not guarantee convergence, since convergence depends on the functional being extremized, the differential constraints, the boundary conditions, and the nominal functionsx(t),u(t), chosen in order to start the algorithm.This research, supported by the National Science Foundation, Grant No. GP-18522, is based on Ref. 1. The authors are indebted to Mr. E. E. Cragg for analytical and computational assistance.     

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.     

The existence results for obstacle optimal control problems

This paper is concerned with the existence of an optimal control problem for a quasi-linear elliptic obstacle variational inequality in which the obstacle is taken as the control. Firstly, we get some existence results under the assumption of the leading operator of the variational inequality with a monotone type mapping in Section 2. In Section 3, as an application, without the assumption of the monotone type mapping for the leading operator of the variational inequality, we prove that the leading operator of the variational inequality is a monotone type mapping. Existence of the optimal obstacle is proved. The method used here is different from [Y.Y. Zhou, X.Q. Yang, K.L. Teo, The existence results for optimal control problems governed by a variational inequality, J. Math. Anal. Appl. 321 (2006) 595-608].     

On infinite-horizon lower closure results for optimal control

Summary Recently, Carlson gave a new infinite-horizon lower closure result [12, 14].Here an infinite-dimensional generalization of this result is derived by combining a new extension of Chacon's biting lemma with a known infinite-dimensional lower semicontinuity result for problems with a finite time horizon.     

Modified optimal quadrature extensions

Summary Optimal extensions of quadrature rules are of importance in the construction of automatic integrators but many sequences fail to exist in usable form. The paper considers some techniques for overcoming the problem of inextensibility with a minimal effect on integrating efficiency. A modification to the extension procedure proposed recently by Begumisa and Robinson is shown to be just a special case of the standard theory for quadrature extension. Some illustrative examples are included.     

Semiconcavity results for constrained optimal control problems in a half-space

In this paper we give semiconcavity results for the value function of some constrained optimal control problems with infinite horizon in a half-space. In particular, we assume that the control space is the l¹-ball or the l^∞-ball in Rn.     

Conjugate gradient techniques for the optimal control evolution dam problem

This paper considers the numerical simulation of optimal control evolution dam problem by using conjugate gradient method.The paper considers the free boundary value problem related to time dependent fluid flow in a homogeneous earth rectangular dam.The dam is taken to be sufficiently long that the flow is considered to be two dimensional.On the left and right walls of the dam there is a reservoir of fluid at a level dependent on time.This problem can be transformed into a variational inequality on a fixed domain.The numerical techniques we use are based on a linear finite element method to approximate the state equations and a conjugate gradient algorithm to solve the discrete optimal control problem.This algorithm is based on Armijo's rule in the unconstrained optimization theory.The convergence of the discrete optimal solutions to the continuous optimal solutions,and the convergence of the conjugate gradient algorithm are proved.A numerical example is given to determine the location of the minimum surface     

Computational method for optimal control of switched systems with input and state constraints

In this paper, we consider an optimal control problem of switched systems with input and state constraints. Since the complexity of such constraint and switching laws, it is difficult to solve the problem using standard optimization techniques. In addition, although conjugate gradient algorithms are very useful for solving nonlinear optimization problem, in practical implementations, the existing Wolfe condition may never be satisfied due to the existence of numerical errors. And the mode insertion technique only leads to suboptimal solutions, due to only certain mode insertions being considered. Thus, based on an improved conjugate gradient algorithm and a discrete filled function method, an improved bi-level algorithm is proposed to solve this optimization problem. Convergence results indicate that the proposed algorithm is globally convergent. Three numerical examples are solved to illustrate the proposed algorithm converges faster and yields a better cost function value than existing bi-level algorithms.     

Invariance results for definable extensions of groups

We show that in an o-minimal expansion of an ordered group finite definable extensions of a definable group which is defined in a reduct are already defined in the reduct. A similar result is proved for finite topological extensions of definable groups defined in o-minimal expansions of the ordered set of real numbers.     

Semiconcavity results for optimal control problems admitting no singular minimizing controls

Semiconcavity results have generally been obtained for optimal control problems in absence of state constraints. In this paper, we prove the semiconcavity of the value function of an optimal control problem with end-point constraints for which all minimizing controls are supposed to be nonsingular.     

Continuation in quasilinearization

A continuation method is described for extending the applicability of quasilinearization to numerically unstable two-point boundary-value problems. Since quasilinearization is a realization of Newton's method, one might expect difficulties in finding satisfactory initial trialpoints, which actually are functions over the specified interval that satisfy the boundary conditions. A practical technique for generating suitable initial profiles for quasilinearization is described. Numerical experience with these techniques is reported for two numerically unstable problems.