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.     

Sequential gradient-restoration algorithm 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 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. Asequential algorithm composed of the alternate succession of gradient phases and restoration phases is presented. This sequential algorithm is contructed in such a way that the differential equations and boundary conditions are satisfied at the end of each iteration, that is, at the end of a complete gradient-restoration phase; hence, the value of the functional at the end of one iteration is comparable with the value of the functional at the end of any other iteration.In thegradient phase, nominal functionsx(t),u(t), satisfying all the differential equations and boundary conditions are assumed. Variations x(t), u(t), leading to varied functions (t),(t), are determined so that the value of the functional is decreased. These variations are obtained by minimizing the first-order change of the functional subject to the linearized differential equations, the linearized boundary conditions, and a quadratic constraint on the variations of the control and the parameter.Since the constraints are satisfied only to first order during the gradient phase, the functions (t),(t), may violate the differential equations and/or the boundary conditions. This being the case, a restoration phase is needed prior to starting the next gradient phase. In thisrestoration phase, the functions (t),(t), are assumed to be the nominal functions. Variations (t), (t), leading to varied functions (t),û(t), consistent with all the differential equations and boundary conditions are determined. These variations are obtained by requiring the least-square change of the control and the parameter subject to the linearized differential equations and the linearized boundary conditions. Of course, the restoration phase must be performed iteratively until the cumulative error in the differential equations and boundary conditions becomes smaller than some preselected value.If the gradient stepsize is , an order-of-magnitude analysis shows that the gradient corrections are x=O(), u=O(), =O(), while the restoration corrections are . Hence, for sufficiently small, the restoration phase preserves the descent property of the gradient phase: the functionalI decreases between any two successive iterations.Methods to determine the gradient stepsize in an optimal fashion are discussed. Examples are presented for both the fixed-final-time case and the free-final-time case. The numerical results show the rapid convergence characteristics of the sequential gradient-restoration algorithm.The portions of this paper dealing with the fixed-final-time case were presented by the senior author at the 2nd Hawaii International Conference on System Sciences, Honolulu, Hawaii, 1969. The portions of this paper dealing with the free-final-time case were presented by the senior author at the 20th International Astronautical Congress, Mar del Plata, Argentina, 1969. This research, supported by the NASA-Manned Spacecraft Center, Grant No. NGR-44-006-089, Supplement No. 1, is a condensation of the investigations presented in Refs. 1–5. The authors are indebted to Professor H. Y. Huang for helpful discussions.     

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.     

A boundary-value problem for the biharmonic equation and the iterated Laplacian in a 3D-domain with an edge

Let Ω be a domain with piecewise smooth boundary. In general, it is impossible to obtain a generalized solution u ∈ W ₂ ² (Ω) of the equation Δ _x ² u = f with the boundary conditions u = Δ_xu = 0 by solving iteratively a system of two Poisson equations under homogeneous Dirichlet conditions. Such a system is obtained by setting v = −Δu. In the two-dimensional case, this fact is known as the Sapongyan paradox in the theory of simply supported polygonal plates. In the present paper, the three-dimensional problem is investigated for a domain with a smooth edge Γ. If the variable opening angle α ∈ C^∞(Γ) is less than π everywhere on the edge, then the boundary-value problem for the biharmonic equation is equivalent to the iterated Dirichlet problem, and its solution u inherits the positivity preserving property from these problems. In the case α ∈ (π 2π), the procedure of solving the two Dirichlet problems must be modified by permitting infinite-dimensional kernel and co-kernel of the operators and determining the solution u ∈ W ₂ ² (Ω) by inverting a certain integral operator on the contour Γ. If α(s) ∈ (3π/2,2π) for a point s ∈ Γ, then there exists a nonnegative function f ∈ L₂(Ω) for which the solution u changes sign inside the domain Ω. In the case of crack (α = 2π everywhere on Γ), one needs to introduce a special scale of weighted function spaces. In this case, the positivity preserving property fails. In some geometrical situations, the problems on well-posedness for the boundary-value problem for the biharmonic equation and the positivity property remain open. Bibliography: 46 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 336, 2006, pp. 153–198.     

Multiple solutions for a class of nonlinear elliptic equations on the Sierpiński gasket

This paper investigates a class of nonlinear elliptic equations on a fractal domain. We establish a strong Sobolev-type inequality which leads to the existence of multiple non-trivial solutions of Δu +c(x)u =f(x,u), with zero Dirichlet boundary conditions on the Sierpiski gasket. Our existence results do not require any growth conditions off(x, t) in t, in contrast to the classical theory of elliptic equations on smooth domains.     

Oscillatory Periodic Solutions of Nonlinear Second Order Ordinary Differential Equations

In this paper the existence results of oscillatory periodic solutions are obtained for a second order ordinary differential equation -u″（t） = f（t, u（t））, where f ： R^2 → R is a continuous odd function and is 2π-periodic in t. The discussion is based on the fixed point index theory in cones.     

The blow-up rate for a system of heat equations with neumann boundary conditions

This paper deals with the blow-up properties of solutions to a system of heat equations u _t=Δu, v _t=Δv in B _R×(0, T) with the Neumann boundary conditions εu/εη=e ^v, εv/εη=e ^u on S _R×[0, T). The exact blow-up rates are established. It is also proved that the blow-up will occur only on the boundary. This work is supported by the National Natural Science Foundation of China     

Implications of the Choice of Quadrature Nodes for Picard Integral Deferred Corrections Methods for Ordinary Differential Equations

This paper concerns a class of deferred correction methods recently developed for initial value ordinary differential equations; such methods are based on a Picard integral form of the correction equation. These methods divide a given timestep [t_n,t_n+1] into substeps, and use function values computed at these substeps to approximate the Picard integral by means of a numerical quadrature. The main purpose of this paper is to present a detailed analysis of the implications of the location of quadrature nodes on the accuracy and stability of the overall method. Comparisons between Gauss-Legendre, Gauss-Lobatto, Gauss-Radau, and uniformly spaced points are presented. Also, for a given set of quadrature nodes, quadrature rules may be formulated that include or exclude function values computed at the left-hand endpoint t_n. Quadrature rules that do not depend on the left-hand endpoint (which are referred to as right-hand quadrature rules) are shown to lead to L(α)-stable implicit methods with α≈π/2. The semi-implicit analog of this property is also discussed. Numerical results suggest that the use of uniform quadrature nodes, as opposed to nodes based on Gaussian quadratures, does not significantly affect the stability or accuracy of these methods for orders less than ten. In contrast, a study of the reduction of order for stiff equations shows that when uniform quadrature nodes are used in conjunction with a right-hand quadrature rule, the form and extent of order-reduction changes considerably. Specifically, a reduction of order to is observed for uniform nodes as opposed to for non-uniform nodes, where Δt denotes the time step and ε a stiffness parameter such that ε→0 corresponds to the problem becoming increasingly stiff. AMS subject classification (2000) 65B05     

Smoluchowski-Kramers approximation for a general class of SPDEs

We prove that the so-called Smoluchowski-Kramers approximation holds for a class of partial differential equations perturbed by a non-Gaussian noisy term. Namely, we show that the solution of the one-dimensional semi-linear stochastic damped wave equations , u(0) = u₀, u_t (0) = v₀, endowed with Dirichlet boundary conditions, converges as the parameter μ goes to zero to the solution of the semi-linear stochastic heat equation , u(0) = u₀, endowed with Dirichlet boundary conditions. Dedicated to Giuseppe Da Prato on the occasion of his 70th birthday     

<Emphasis Type="Italic">f</Emphasis>-Vectors of barycentric subdivisions

For a simplicial complex or more generally Boolean cell complex Δ we study the behavior of the f- and h-vector under barycentric subdivision. We show that if Δ has a non-negative h-vector then the h-polynomial of its barycentric subdivision has only simple and real zeros. As a consequence this implies a strong version of the Charney–Davis conjecture for spheres that are the subdivision of a Boolean cell complex or the subdivision of the boundary complex of a simple polytope. For a general (d − 1)-dimensional simplicial complex Δ the h-polynomial of its n-th iterated subdivision shows convergent behavior. More precisely, we show that among the zeros of this h-polynomial there is one converging to infinity and the other d − 1 converge to a set of d − 1 real numbers which only depends on d. F. Brenti and V. Welker are partially supported by EU Research Training Network “Algebraic Combinatorics in Europe”, grant HPRN-CT-2001-00272 and the program on “Algebraic Combinatorics” at the Mittag-Leffler Institut in Spring 2005.     

Some combinatorial properties of flag simplicial pseudomanifolds and spheres

A simplicial complex Δ is called flag if all minimal nonfaces of Δ have at most two elements. The following are proved: First, if Δ is a flag simplicial pseudomanifold of dimension d−1, then the graph of Δ (i) is (2d−2)-vertex-connected and (ii) has a subgraph which is a subdivision of the graph of the d-dimensional cross-polytope. Second, the h-vector of a flag simplicial homology sphere Δ of dimension d−1 is minimized when Δ is the boundary complex of the d-dimensional cross-polytope.     

The solvability of a boundary-value periodic problem

In the space of functions B _a³⁺={g(x, t)=−g(−x, t)=g(x+2π, t)=−g(x, t+T₃/2)=g(x, −t)}, we establish that if the condition aT ₃ (2s−1)=4πk, (4πk, a (2s−1))=1, k ∈ ℤ, s ∈ ℕ, is satisfied, then the linear problem u _u −a ² u _xx =g(x, t), u(0, t)=u(π, t)=0, u(x, t+T ₃ )=u(x, t), ℝ², is always consistent. To prove this statement, we construct an exact solution in the form of an integral operator. Ternopol’ Pedagogical Institute, Ternopol’. Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 49, No. 2, pp. 302–308, Feburary, 1997 Ternopol’ Pedagogical Institute, Ternopol’. Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 49, No. 2, pp. 302–308, Feburary, 1997     

Linear periodic boundary-value problem for a second-order hyperbolic equation. II. Quasilinear problem

In three spaces, we find exact classical solutions of the boundary-value periodic problem u_tt - a²u_xx = g(x, t) u(0, t) = u(π, t) = 0, u(x, t + T) = u(x, t), x ∈ ℝ, t ∈ ℝ. We study the periodic boundary-value problem for a quasilinear equation whose left-hand side is the d’Alembert operator and whose right-hand side is a nonlinear operator. Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 50, No. 12, pp. 1680–1685, December, 1998.     

Maximal Betti numbers of Cohen–Macaulay complexes with a given <Emphasis Type="Italic">f</Emphasis>-vector

Given the f-vector f = (f₀, f₁, . . .) of a Cohen–Macaulay simplicial complex, it will be proved that there exists a shellable simplicial complex Δ_f with f(Δ_f) = f such that, for any Cohen–Macaulay simplicial complex Δ with f(Δ) = f, one has for all i and j, where f(Δ) is the f-vector of Δ and where β _ij (I _Δ) are graded Betti numbers of the Stanley–Reisner ideal I _Δ of Δ. The first author is supported by JSPS Research Fellowships for Young Scientists. Received: 23 January 2006     

On a two-point boundary value problem of duffing type equation with dirichlet conditions

An existence and uniqueness result concerned with the Diriehlet boundary value prob-lem u“ cu‘ g(t,u)=e(t),u(0)=u(π)=0 is offered.     

Existence of the Vejvoda-Shtedry spaces

We investigate the linear periodic problem u _tt −u _xx =F(x, t), u(x+2π, t)=u(x, t+T)=u(x, t), ∈ ℝ², and establish conditions for the existence of its classical solution in spaces that are subspaces of the Vejvoda-Shtedry spaces. Ternopol’ Pedagogical Institute, Ternopol’. Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 49, No. 2, pp. 302–308, February, 1997.     

A sturm-liouville problem with physical and spectral parameters in boundary conditions

We study the spectral probleml(u)=−u″+q(x)u(x)=λu(x),u′(0)=0, u′(π)=mλu(π), where λ andm are a spectral and a physical parameter. Form<0, we associate with the problem a self-adjoint operator in Pontryagin space II₁. Using this fact and developing analytic methods of the theory of Sturm-Liouville operators, we study the dynamics of eigenvalues and eigenfunctions of the problems asm→−0. Translated fromMatematicheskie Zametki, Vol. 66, No. 2, pp. 163–172, August, 1999.     

Evolution equations with a free boundary condition

In this paper we consider the heat flow of harmonic maps between two compact Riemannian Manifolds M and N (without boundary) with a free boundary condition. That is, the following initial boundary value problem ∂₁,u −Δu = Γ(u)(∇u, ∇u) [tT T_{u u}N, on M × [0, ∞), u(t, x) ∈ Σ, for x ∈ ∂M, t > 0, ∂u/t6n(t, x) ⊥_u T_u(t,x) Σ, for x ∈ ∂M, t > 0, u(o,x) = u_o(x), on M, where Σ is a smooth submanifold without boundary in N and n is a unit normal vector field of M along ∂M. Due to the higher nonlinearity of the boundary condition, the estimate near the boundary poses considerable difficulties, even for the case N = ℝⁿ, in which the nonlinear equation reduces to ∂_tu-Δu = 0. We proved the local existence and the uniqueness of the regular solution by a localized reflection method and the Leray-Schauder fixed point theorem. We then established the energy monotonicity formula and small energy regularity theorem for the regular solutions. These facts are used in this paper to construct various examples to show that the regular solutions may develop singularities in a finite time. A general blow-up theorem is also proven. Moreover, various a priori estimates are discussed to obtain a lower bound of the blow-up time. We also proved a global existence theorem of regular solutions under some geometrical conditions on N and Σ which are weaker than K_N <-0 and Σ is totally geodesic in N.     

On a smooth solution of a nonlinear periodic boundary-value problem

We establish conditions for the existence of a smooth solution of a quasilinear hyperbolic equationu _tt - u_xx = ƒ(x, t, u, u, u _x),u (0,t) = u (π,t) = 0,u (x, t+ T) = u (x, t), (x, t) ∈ [0, π] ×R, and prove a theorem on the existence and uniqueness of a solution. Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 51, No. 11, pp. 1574–1576, November, 1999.     

On the fundamental group of real toric varieties

LetX (Δ) be the real toric variety associated to a smooth fan Δ. The main purpose of this article is: (i) to determine the fundamental group and the universal cover ofX (Δ), (ii) to give necessary and sufficient conditions on Δ under which π₁(X(Δ)) is abelian, (iii) to give necessary and sufficient conditions on Δ under whichX(Δ) is aspherical, and when Δ is complete, (iv) to give necessary and sufficient conditions forC _Δ to be aK (π, 1) space whereC _Δ is the complement of a real subspace arrangement associated to Δ.