Sequential gradient-restoration algorithm for optimal control problems with general boundary conditions

This paper considers the numerical solution of two classes of optimal control problems, called Problem P1 and Problem P2 for easy identification.Problem P1 involves a functionalI subject to differential 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 and the boundary conditions are satisfied to a predetermined accuracy. Problem P2 extends Problem P1 to include nondifferential constraints to be satisfied everywhere along the interval of integration. Algorithms are developed for both Problem P1 and Problem P2.The approach taken is a sequence of two-phase cycles, composed of a gradient phase and a restoration phase. The gradient phase involves one iteration and is designed to decrease the value of the functional, while the constraints are satisfied to first order. The restoration phase involves one or more iterations and is designed to force constraint satisfaction to a predetermined accuracy, while the norm squared of the variations of the control, the parameter, and the missing components of the initial state is minimized.The principal property of both algorithms is that they produce a sequence of feasible suboptimal solutions: the functions obtained at the end of each cycle satisfy the constraints to a predetermined accuracy. Therefore, the values of the functionalI corresponding to any two elements of the sequence are comparable.The stepsize of the gradient phase is determined by a one-dimensional search on the augmented functionalJ, while the stepsize of the restoration phase is obtained by a one-dimensional search on the constraint errorP. The gradient stepsize and the restoration stepsize are chosen so that the restoration phase preserves the descent property of the gradient phase. Therefore, the value of the functionalI at the end of any complete gradient-restoration cycle is smaller than the value of the same functional at the beginning of that cycle.The algorithms presented here differ from those of Refs. 1 and 2, in that it is not required that the state vector be given at the initial point. Instead, the initial conditions can be absolutely general. In analogy with Refs. 1 and 2, the present algorithms are capable of handling general final conditions; therefore, they are suited for the solution of optimal control problems with general boundary conditions. Their importance lies in the fact that many optimal control problems involve initial conditions of the type considered here.Six numerical examples are presented in order to illustrate the performance of the algorithms associated with Problem P1 and Problem P2. The numerical results show the feasibility as well as the convergence characteristics of these algorithms.This research was supported by the Office of Scientific Research, Office of Aerospace Research, United States Air Force, Grant No. AF-AFOSR-76-3075. Partial support for S. Gonzalez was provided by CONACYT, Consejo Nacional de Ciencia y Tecnologia, Mexico City, Mexico.     

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.     

Sequential gradient-restoration 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.The approach taken is a sequence of two-phase processes or cycles, composed of a gradient phase and a restoration phase. The gradient phase involves a single iteration and is designed to decrease the functional, while the constraints are satisfied to first order. The restoration phase involves one or several iterations and is designed to restore the constraints to a predetermined accuracy, while the norm of the variations of the control and the parameter is minimized. The principal property of the algorithm is that it produces a sequence of feasible suboptimal solutions: the functionsx(t),u(t), obtained at the end of each cycle satisfy the constraints to a predetermined accuracy. Therefore, the functionals of any two elements of the sequence are comparable.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 sequential gradient-restoration algorithm is constructed in such a way that the state inequality constraint is satisfied at each iteration of the gradient phase and the restoration phase 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.To facilitate the numerical solution on digital computers, the actual time is replaced by the normalized timet, defined in such a way that each of the subarcs composing the extremal arc has a normalized time length t=1. In this way, variable-time corner conditions and variable-time terminal conditions are transformed into fixed-time corner conditions and fixed-time terminal conditions. The actual times ₁, ₂, at which (i) the state boundary is entered, (ii) the state boundary is exited, and (iii) the terminal boundary is reached are regarded to be components of the parameter being optimized.The numerical examples illustrating the theory demonstrate the feasibility as well as the rapidity of convergence of the technique developed in this paper.This paper is based in part on a portion of the dissertation which the first author submitted in partial fulfillment of the requirements for the PhD Degree at the Air Force Institute of Technology, Wright-Patterson AFB, Ohio. This research was supported in part 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 Professor H. Y. Huang, Dr. R. R. Iyer, Dr. J. N. Damoulakis, Mr. A. Esterle, and Mr. J. R. Cloutier for helpful discussions as well as analytical and numerical assistance. This paper is a condensation of the investigations reported in Refs. 1–2.     

Maximum principle and second-order conditions for minimax problems of optimal control

In this paper, we study the optimal control problem of minimizing the functionalJ(x, u)=max_t1tt2(x(t),t). We formulate and prove necessary optimality conditions for this problem. We establish the equivalence between the initial minimax problem and a problem involving a terminal functional and phase constraints.     

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.     

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.     

Variable multistep methods for delay differential equations

In this paper, variable stepsize multistep methods for delay differential equations of the type y(t) = f(t, y(t), y(t − τ)) are proposed. Error bounds for the global discretization error of variable stepsize multistep methods for delay differential equations are explicitly computed. It is proved that a variable multistep method which is a perturbation of strongly stable fixed step size method is convergent.     

On Restart Procedures for the Conjugate Gradient Method

The conjugate gradient method is a powerful solution scheme for solving unconstrained optimization problems, especially for large-scale problems. However, the convergence rate of the method without restart is only linear. In this paper, we will consider an idea contained in [16] and present a new restart technique for this method. Given an arbitrary descent direction d _t and the gradient g _t , our key idea is to make use of the BFGS updating formula to provide a symmetric positive definite matrix P _t such that d _t =?P _t g _t , and then define the conjugate gradient iteration in the transformed space. Two conjugate gradient algorithms are designed based on the new restart technique. Their global convergence is proved under mild assumptions on the objective function. Numerical experiments are also reported, which show that the two algorithms are comparable to the Beale–Powell restart algorithm.     

Remarks on frequency domain methods for Volterra integral equations

The equation u(t) = ? ∫₀^tA(t ? τ) g(u(τ)) dτ + h(t), t ? 0 is studied on a Hilbert space H. A(t) is a family of bounded linear operators and g can be unbounded and nonlinear. Stability and asymptotic stability of solutions are studied. Frequency domain conditions are statements about the Laplace transform of A. An extension of the frequency domain method of Popov for H = R¹ is given. Here it is assumed that g is the gradient of a functional G. The frequency domain conditions are related to monotonicity and convexity conditions on A thus connecting Popov's result with work of Levin and London on equations in R¹. A second result is given in which g is not assumed to be a gradient. This extends a result of Levin in R¹. The ideas are illustrated by an example of a nonlinear partial differential functional equation.     

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.     

On oscillation of solutions of higher order forced functional differential inequalities

Oscillation criteria for the class of forced functional differential inequalities x(t){L_nx(t) + f(t, x(t), x[g₁(t)],…, x[g_m(t)]) ? h(t)} ? 0, for n even, and x(t){L_nx(t) ? f(t, x(t), x[g₁(t)],…, x[g_m(t)]) ? h(t)} ? 0, for n odd, are established.     

A note on the evaluation of bounded L2-functionals at B-splines and its application to singular integral equations

An algorithm computing recursively the values of ∫g(t)v(t) dt, whereg is anL ₂-function andv is aB-spline, is presented. For the functionsg _s(t)=log∥s?t∥ the starting values of the recursion formula can be computed analytically. The problem is related to the numerical solution of integral equations with a logarithmic singularity.     

Boundedness of solutions of difference equations and application to numerical solution of Volterra integral equations of the second kind

We study the difference equations obtained when some numerical methods for Volterra integral equations of the second kind are applied to the linear test problem y(t) = 1 + ∝₀^t (λ + μt + vs) y(s) ds, t ⩾ 0, with fixed stepsize h. The resulting difference equations are of Poincaré type and we formulate a criterion for boundedness of solutions of these equations if the associated characteristic polynomial is a simple von Neumann polynomial. This result is then used in stability analysis of reducible quadrature methods for Volterra integral equations.     

Oscillatory and asymptotic behavior of solutions of differential equations with deviating arguments

The oscillatory and asymptotic behavior of solutions of a class of nth order nonlinear differential equations, with deviating arguments, of the form (E, δ) L_nx(t) + δq(t) f(x[g₁(t)],…, x[g_m(t)]) = 0, where δ = ± 1 and L₀x(t) = x(t), L_kx(t) = a_k(t)(L_{k ? 1}x(t))^., $\text{k = 1, 2,…, n (}{}^{\mathrm{.}}\text{=}\text{d}\text{dt}\text{)}$, is examined. A classification of solutions of (E, δ) with respect to their behavior as t → ∞ and their oscillatory character is obtained. The comparisons of (E, 1) and (E, ?1) with first and second order equations of the form y^.(t) + c₁(t) f(y[g₁(t)],…, y[g_m(t)]) = 0 and (a_{n ? 1}(t)z^.(t))^. ? c₂(t) f(z[g₁(t)],…, z[g_m(t)]) = 0, respectively, are presented. The obtained results unify, extend and improve some of the results by Graef, Grammatikopoulos and Spikes, Philos and Staikos.     

Differential Harnack inequalities for heat equations with potentials under geometric flows

In the paper we consider a closed Riemannian manifold M with a time-dependent Riemannian metric g _ij (t) evolving by ? _t g _ij  = ?2S _ij , where S _ij is a symmetric two-tensor on (M,g(t)). We prove some differential Harnack inequalities for positive solutions of heat equations with potentials on (M,g(t)). Some applications of these inequalities will be obtained.     

On a nonlinear Volterra integral equation in a Banach space

The equation u(t) + ∝₀^tk(t ? s)g(s) ds?f(t), t ? 0, is studied in a real Banach space with uniformly convex dual. Conditions, sufficient for the existence of a unique solution, are given for the operatorvalued kernel k, the nonlinear m-accretive operators g(t) and the function f. The case when k is realvalued, g(t) ≡ g and X a reflexive Banach space is also considered. These results extend earlier results by Barbu, Londen and MacCamy.     

On the cycle structure of certain classes of nonlinear shift registers

When m = qt, g(x_t+1, x_2t+1,…, x_(q?1)t+1) is a linear combination of only odd (or only even) elementary symmetric functions, then every cycle of the nonlinear shift register with feedback function f(x₁, x₂,…, x_m) = x₁ + g(x_t+1, x_2t+1,…, x_(q?1)t+1) has a minimal period dividing m(q+1). It is also shown that when g is derived from a cyclic code with minimum distance ?3, every cycle of this shift register has a minimal period dividing m(q + 1).     

Existence and uniqueness of periodic solutions for a kind of first order neutral functional differential equations

In this paper, we use the coincidence degree theory to establish new results on the existence and uniqueness of T-periodic solutions for the first order neutral functional differential equation of the form

(x(t)+Bx(t−δ)^)′=g₁(t,x(t))+g₂(t,x(t−τ))+p(t).     

Existence and uniqueness result for a backward stochastic differential equation whose generator is Lipschitz continuous in y and uniformly continuous in z

In this note, we extend the result in Lepetier and San Martin (Stat. Probab. Lett. 32:425–430, 1997) by eliminating the condition that (g(t,0,0)) _t∈[0,T] is a bounded process. Furthermore, we prove that if g is Lipschitz continuous in y and uniformly continuous in z, and (g(t,0,0)) _t∈[0,T] is square integrable, then for each square integrable terminal condition ξ, there exists a unique square integrable adapted solution to the one-dimensional backward stochastic differential equation (BSDE) with the generator g, which generalizes the corresponding (one-dimensional) results in Pardoux and Peng (Syst. Control Lett. 14:55–61, 1990), Jia (C. R. Acad. Sci. Paris, Ser. I 346:439–444, 2008) and Jia (Stat. Probab. Lett. 79:436–441, 2009).     

Periodic solutions for a Rayleigh type p-Laplacian equation with sign-variable coefficient of nonlinear term

As p-Laplacian equations have been widely applied in the field of fluid mechanics and nonlinear elastic mechanics, it is necessary to investigate the periodic solutions of functional differential equations involving the scalar p-Laplacian. By using Lu’s continuation theorem, which is an extension of Manásevich-Mawhin, we study the existence of periodic solutions for a Rayleigh type p-Laplacian equation

(φ_p(x^′(t)))^′+f(x^′(t))+g₁(x(t-τ₁(t,|x|_∞)))+β(t)g₂(x(t-τ₂(t,|x|_∞)))=e(t).