Existence theorems for multidimensional Lagrange problems

Existence theorems are proved for multidimensional Lagrange problems of the calculus of variations and optimal control. The unknowns are functions of several independent variables in a fixed bounded domain, the cost functional is a multiple integral, and the side conditions are partial differential equations, not necessarily linear, with assigned boundary conditions. Also, unilateral constraints may be prescribed both on the space and the control variables. These constraints are expressed by requiring that space and control variables take their values in certain fixed or variable sets wich are assumed to be closed but not necessarily compact.This research was partially supported by the Office of Scientific Research, Office of Aerospace Research, United States Air Force, Grant No. AF-AFOSR-942-65.     

The synthesis of optimal controls for linear,time-optimal problems with retarded controls

Optimization problems involving linear systems with retardations in the controls are studied in a systematic way. Some physical motivation for the problems is discussed. The topics covered are: controllability, existence and uniqueness of the optimal control, sufficient conditions, techniques of synthesis, and dynamic programming. A number of solved examples are presented.This research was supported in part by the National Aeronautics and Space Administration under Grant No. NGL-40-002-015, in part by the Air Force Office of Scientific Research under Grant No. AF-AFOSR-693-67B, and in part by the National Science Foundation under Grant No. GP-15132.     

The treatment of nonhomogeneous Dirichlet boundary conditions by thep-version of the finite element method

Summary The paper addresses the problem of the implementation of nonhomogeneous essential Dirichlet type boundary conditions in thep-version of the finite element method.Partially supported by the Office of Naval Research under Grant N-00014-85-K-0169Research partially supported by the Air Force Office of Scientific Research, Air Force Systems Command, USAF, under Grant Number AFOSR 85-0322     

A transformation technique for optimal control problems with partially linear state inequality constraints

This paper considers optimal control problems involving the minimization of a functional subject to differential constraints, terminal constraints, and a state inequality constraint. The state inequality constraint is of a special type, namely, it is linear in some or all of the components of the state vector.A transformation technique is introduced, by means of which the inequality-constrained problem is converted into an equality-constrained problem involving differential constraints, terminal constraints, and a control equality constraint. The transformation technique takes advantage of the partial linearity of the state inequality constraint so as to yield a transformed problem characterized by a new state vector of minimal size. This concept is important computationally, in that the computer time per iteration increases with the square of the dimension of the state vector.In order to illustrate the advantages of the new transformation technique, several numerical examples are solved by means of the sequential gradient-restoration algorithm for optimal control problems involving nondifferential constraints. The examples show the substantial savings in computer time for convergence, which are associated with the new transformation technique.This research was supported by the Office of Scientific Research, Office of Aerospace Research, United States Air Force, Grant No. AF-AFOSR-76-3075, and by the National Science Foundation, Grant No. MCS-76-21657.     

An exact penalty function algorithm for optimal control problems with control and terminal equality constraints,part 2

In Part 1 of this paper, implementable and conceptual versions of an algorithm for optimal control problems with control constraints and terminal equality constraints were presented. It was shown that anyL accumulation points of control sequences generated by the algorithms satisfy necessary conditions of optimality. Since such accumulation points need not exist, it is shown in this paper that control sequences generated by the algorithms always have accumulation points in the sense of control measure, and these accumulation points satisfy optimality conditions for the corresponding relaxed control problem.This work was supported by the United Kingdom Science Research Council, by the US Army Research Office, Contract No. DAA-29-73-C-0025, and by the National Science Foundation, Grant No. ENG-73-08214-A01.     

An exact penalty function algorithm for optimal control problems with control and terminal equality constraints,part 1

The presence of control constraints, because they are nondifferentiable in the space of control functions, makes it difficult to cope with terminal equality constraints in optimal control problems. Gradient-projection algorithms, for example, cannot be employed easily. These difficulties are overcome in this paper by employing an exact penalty function to handle the cost and terminal equality constraints and using the control constraints to define the space of permissible search directions in the search-direction subalgorithm. The search-direction subalgorithm is, therefore, more complex than the usual linear program employed in feasible-directions algorithms. The subalgorithm approximately solves a convex optimal control problem to determine the search direction; in the implementable version of the algorithm, the accuracy of the approximation is automatically increased to ensure convergence.This work was supported by the United Kingdom Science Research Council, by the US Army Research Office, Contract No. DAAG-29-73-C-0025, and by the National Science Foundation, Grant No. ENG-73-08214-A01.     

Controlled Markov processes on the infinite planning horizon: Weighted and overtaking cost criteria

Stochastic control problems for controlled Markov processes models with an infinite planning horizon are considered, under some non-standard cost criteria. The classical discounted and average cost criteria can be viewed as complementary, in the sense that the former captures the short-time and the latter the long-time performance of the system. Thus, we study a cost criterion obtained as weighted combinations of these criteria, extending to a general state and control space framework several recent results by Feinberg and Shwartz, and by Krass et al. In addition, a functional characterization is given for overtaking optimal policies, for problems with countable state spaces and compact control spaces; our approach is based on qualitative properties of the optimality equation for problems with an average cost criterion.Research partially supported by the Engineering Foundation under grant RI-A-93-10, in part by the National Science Foundation under grant NSF-INT 9201430, and in part by a grant from the AT&T Foundation.Research partially supported by the Air Force Office of Scientific Research under Grant F49620-92-J-0045, and in part by the National Science Foundation under Grant CDR-8803012.     

High-order adaptive finite element-singly implicit Runge-Kutta methods for parabolic differential equations

We describe an adaptive mesh refinement finite element method-of-lines procedure for solving one-dimensional parabolic partial differential equations. Solutions are calculated using Galerkin's method with a piecewise hierarchical polynomial basis in space and singly implicit Runge-Kutta (SIRK) methods in time. A modified SIRK formulation eliminates a linear systems solution that is required by the traditional SIRK formulation and leads to a new reduced-order interpolation formula. Stability and temporal error estimation techniques allow acceptance of approximate solutions at intermediate stages, yielding increased efficiency when solving partial differential equations. A priori energy estimates of the local discretization error are obtained for a nonlinear scalar problem. A posteriori estimates of local spatial discretization errors, obtained by order variation, are used with the a priori error estimates to control the adaptive mesh refinement strategy. Computational results suggest convergence of the a posteriori error estimate to the exact discretization error and verify the utility of the adaptive technique.This research was partially supported by the U.S. Air Force Office of Scientific Research, Air Force Systems Command, USAF, under Grant Number AFOSR-90-0194; the U.S. Army Research Office under Contract Number DAAL 03-91-G-0215; by the National Science Foundation under Grant Number CDA-8805910; and by a grant from the Committee on Research, Tulane University.     

A posteriori error estimation with finite element methods of lines for one-dimensional parabolic systems

Summary Consider the solution of one-dimensional linear initial-boundary value problems by a finite element method of lines using a piecewiseP ^th -degree polynomial basis. A posteriori estimates of the discretization error are obtained as the solutions of either local parabolic or local elliptic finite element problems using piecewise polynomial corrections of degreep+1 that vanish at element ends. Error estimates computed in this manner are shown to converge in energy under mesh refinement to the exact finite element discretization error. Computational results indicate that the error estimates are robust over a wide range of mesh spacings and polynomial degrees and are, furthermore, applicable in situations that are not supported by the analysis.This research was partially supported by the U.S. Air Force Office of Scientific Research, Air Force Systems Command, USAF, under Grant Number AFOSR 90-0194; by the U.S. Army Research Office under Contract Number DAAL03-91-G-0215; and by the National Science Foundation under Institutional Infrastructure Grant Number CDA-8805910     

Constrained duality via unconstrained duality in generalized geometric programming

A specialization of unconstrained duality (involving problems without explicit constraints) to constrained duality (involving problems with explicit constraints) provides an efficient mechanism for extending to the latter many important theorems that were previously established for the former.This research was sponsored by the Air Force Office of Scientific Research, Air Force Systems Command, USAF, under Grant No. AFOSR-73-2516.     

The complementary unboundedness of dual feasible solution sets in convex programming

F.E. Clark has shown that if at least one of the feasible solution sets for a pair of dual linear programming problems is nonempty then at least one of them is both nonempty and unbounded. Subsequently, M. Avriel and A.C. Williams have obtained the same result in the more general context of (prototype posynomial) geometric programming. In this paper we show that the same result is actually false in the even more general context of convex programming — unless a certain regularity condition is satisfied.We also show that the regularity condition is so weak that it is automatically satisfied in linear programming (prototype posynomial) geometric programming, quadratic programming (with either linear or quadratic constraints),l _p -regression analysis, optimal location, roadway network analysis, and chemical equilibrium analysis. Moreover, we develop an equivalent regularity condition for each of the usual formulations of duality.Research sponsored by the Air Force Office of Scientific Research, Air Force Systems Command, USAF, under Grant Number AFOSR-73-2516.     

Functional analytic analysis of a pursuit problem

Some new results related to pursuit problems considered in Ref. 1 are presented here. The present formulation of the problem is more general than that of Ref. 1 in some respects. It allows one to consider magnitude, effort, and energy constraints on the control action. The concept of interceptibility of the pursued by the pursuer is introduced. Several necessary and sufficient conditions of interception are then developed. Finally, optimal strategies of pursuit are discussed.This research was supported in part by the Air Force Office of Scientific Research, Grant No. AF-AFOSR-669-67.     

Numerical methods for reaction-diffusion problems with non-differentiable kinetics

Summary We consider a class of steady-state semilinear reaction-diffusion problems with non-differentiable kinetics. The analytical properties of these problems have received considerable attention in the literature. We take a first step in analyzing their numerical approximation. We present a finite element method and establish error bounds which are optimal for some of the problems. In addition, we also discuss a finite difference approach. Numerical experiments for one- and two-dimensional problems are reported.Dedicated to Ivo Babuka on his sixtieth birthdayResearch partially supported by the Air Force Office of Scientific Research, Air Force Systems Command, USAF under Grant Number AFOSR 85-0322     

Nonlocal regularization of L. C. Young's tacking problem

L. C. Young's tacking problem is a prototype of a nonconvex variational problem for which minimizing sequences for the energy do not attain a minimum. The minimizer of the energy is usually described as a Young-measure or generalized curve. In many studies, the tacking problem is regularized by adding a higher-order viscosity term to the energy. This regularized energy has classical minimizers. In this paper we regularize instead with a spatially nonlocal term. This weakly regularized problem still has measure-valued minimizers, but as the nonlocal term becomes stronger, the measure-valued solutions organize, coalesce, and eventually turn into classical solutions. The information on the measure-valued solutions is obtained by studying equivalent variational problems involving moments of the measures.The research of D. Brandon has been partially supported by the Office of Naval Research under Grant Number N00014-88-K-0417 and by DARPA Grant F4920-87-C-0116, and that of R. C. Rogers has been partially supported by the Office of Naval Research under Grant Number N00014-88-K-0417 and by the National Science Foundation under Grant Number DMS-8801412.     

The multiplier method of Hestenes and Powell applied to convex programming

For nonlinear programming problems with equality constraints, Hestenes and Powell have independently proposed a dual method of solution in which squares of the constraint functions are added as penalties to the Lagrangian, and a certain simple rule is used for updating the Lagrange multipliers after each cycle. Powell has essentially shown that the rate of convergence is linear if one starts with a sufficiently high penalty factor and sufficiently near to a local solution satisfying the usual second-order sufficient conditions for optimality. This paper furnishes the corresponding method for inequality-constrained problems. Global convergence to an optimal solution is established in the convex case for an arbitrary penalty factor and without the requirement that an exact minimum be calculated at each cycle. Furthermore, the Lagrange multipliers are shown to converge, even though the optimal multipliers may not be unique.This work was supported in part by the Air Force Office of Scientific Research under Grant No. AF-AFOSR-72-2269.     

Minimum-weight design of elastic sandwich beams with deflection constraints

In this paper, minimum-weight design of an elastic sandwich beam with a prescribed deflection constraint at a given point is investigated. The analysis is based on geometrical considerations using then-dimensional space of discretized specific bending stiffness. Since the present method of analysis is different from the method based on the calculus of variations, the conditions of piecewise continuity and differentiability on specific bending stiffness can be relaxed. Necessary and sufficient conditions for optimality are derived for both statically determinate and statically indeterminate beams. Beams subject to a single loading and beams subject to multiple loadings are analyzed. The degree to which the optimality condition renders the solution unique is discussed. To illustrate the method of solution, two examples are presented for minimum-weight designs under dual loading of a simply supported beam and a beam built in at both ends. The present analysis is also extended to the following problems: (a) optimal design of a beam built in at both ends with piecewise specific stiffness and a prescribed deflection constraint and (b) minimum-cost design of a sandwich beam with prescribed deflection constraints.The results presented in this paper were obtained in the course of research supported partly by the US Army Research Office, Durham, North Carolina, Research Grant No. DA-ARO-31-G1008, and partly by the Office of Naval Research, Contract No. N00014-67-A-0109-0003, Task No. NR 064-496. The authors wish to express their thanks to Professor H. Halkin for pointing out the applicability of optimal control theory to the present problem and to Professor W. Prager for his valuable suggestions.     

On the computation of the optimal cost function for discrete time Markov models with partial observations

We consider several applications of two state, finite action, infinite horizon, discrete-time Markov decision processes with partial observations, for two special cases of observation quality, and show that in each of these cases the optimal cost function is piecewise linear. This in turn allows us to obtain either explicit formulas or simplified algorithms to compute the optimal cost function and the associated optimal control policy. Several examples are presented.Research supported in part by the Air Force Office of Scientific Research under Grant AFOSR-86-0029, in part by the National Science Foundation under Grant ECS-8617860, in part by the Advanced Technology Program of the State of Texas, and in part by the DoD Joint Services Electronics Program through the Air Force Office of Scientific Research (AFSC) Contract F49620-86-C-0045.     

Pricing problems with a continuum of customers as stochastic Stackelberg games

The pricing problem where a company sells a certain kind of product to a continuum of customers is considered. It is formulated as a stochastic Stackelberg game with nonnested information structure. The inducible region concept, recently developed for deterministic Stackelberg games, is extended to treat the stochastic pricing problem. Necessary and sufficient conditions for a pricing scheme to be optimal are derived, and the pricing problem is solved by first delineating its inducible region, and then solving a constrained optimal control problem.The research work reported here as supported in part by the National Science Foundation under Grant ECS-81-05984, Grant ECS-82-10673, and by the Air Force Office of Scientific Research under AFOSR Grant 80-0098.     

Feedback exact null controllability for unbounded control problems in Hilbert space

Terminal constraint optimal control problems with unbounded control operators are considered. It is shown that the optimal solutions can be represented in a feedback form via a solution of an appropriate Riccati equation. In particular, it is proved that, for systems described by partial differential equations with infinite speed of propagation, boundary exact null controllability can be realized in feedback form.This work was partially supported by the National Science Foundation, Grant No. DMS-89-02811, and by the Air Force Office of Scientific Research, Grant No. AFOSR-89-0511 DEF.     

Exploiting special structure in Karmarkar's linear programming algorithm

We propose methods to take advantage of specially-structured constraints in a variant of Karmarkar's projective algorithm for standard form linear programming problems. We can use these constraints to generate improved bounds on the optimal value of the problem and also to compute the necessary projections more efficiently, while maintaining the theoretical bound on the algorithm's performance. It is shown how various upper-bounding constraints can be handled implicitly in this way. Unfortunately, the situation for network constraints appears less favorable.Research supported in part by National Science Foundation Grant ECS-8602534, ONR Contract N00014-87-K-0212 and the US Army Research Office through the Mathematical Sciences Institute of Cornell University.