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.     

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.     

Sequential conjugate-gradient-restoration algorithm for optimal control problems. Part 1. Theory

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. First, the case of a quadratic functional subject to linear constraints is considered, and a conjugate-gradient algorithm is derived. Nominal functionsx(t),u(t), π satisfying all the differential equations and boundary conditions are assumed. Variations Δx(t), δu(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 differential equations, the boundary conditions, and a quadratic constraint on the variations of the control and the parameter. Next, the more general case of a nonquadratic functional subject to nonlinear constraints is considered. The algorithm derived for the linear-quadratic case is employed with one modification: a restoration phase is inserted between any two successive conjugate-gradient phases. In the restoration phase, variations Δx(t), Δu(t), Δπ are determined by requiring the least-square change of the control and the parameter subject to the linearized differential equations and the linearized boundary conditions. Thus, a sequential conjugate-gradient-restoration algorithm is constructed in such a way that the differential equations and the boundary conditions are satisfied at the end of each complete conjugate-gradient-restoration cycle. Several numerical examples illustrating the theory of this paper are given in Part 2 (see Ref. 1). These examples 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 Professor A. Miele for stimulating discussions. Formerly, Graduate Studient in Aero-Astronautics, Department of Mechanical and Aerospace Engineering and Materials Science, Rice University, Houston, Texas.     

Multiple-Subarc Gradient-Restoration Algorithm, Part 1: Algorithm Structure

Rapid progresses in information and computer technology allow the development of more advanced optimal control algorithms dealing with real-world problems. In this paper, which is Part 1 of a two-part sequence, a multiple-subarc gradient-restoration algorithm (MSGRA) is developed. We note that the original version of the sequential gradient-restoration algorithm (SGRA) was developed by Miele et al. in single-subarc form (SSGRA) during the years 1968–86; it has been applied successfully to solve a large number of optimal control problems of atmospheric and space flight.MSGRA is an extension of SSGRA, the single-subarc gradient-restoration algorithm. The primary reason for MSGRA is to enhance the robustness of gradient-restoration algorithms and also to enlarge 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.Two features of MSGRA are increased automation and efficiency. The automation of MSGRA is enhanced via time normalization: the actual time domain is mapped into a normalized time domain such that the normalized time length of each subarc is 1. The efficiency of MSGRA is enhanced by using the method of particular solutions to solve the multipoint boundary-value problems associated with the gradient phase and the restoration phase of the algorithm.In a companion paper [Part 2 (Ref. 2)], 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 and compared.     

Generating pareto-optimal alternatives by a nonfeasible hierarchical method

A hierarchical algorithm for generating Pareto-optimal alternatives for convex multicriteria problems is derived. At the upper level, values for Lagrange multipliers of the coupling constraints are first given. Then at the subsystems, Pareto-optimal values are determined for the subsystem objectives, whereby an additional term or an additional objective is included due to the Lagrange multipliers. In the subsystem optimizations, the coupling equations between the subsystems are not satisfied; therefore, the method is called nonfeasible. Finally, the upper level checks which of the subsystem solutions satisfy the coupling constraints; these solutions are Pareto-optimal solutions for the overall system.     

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.     

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.     

Additional necessary conditions for optimal control with state-variable inequality constraints

It is shown that, when the set of necessary conditions for an optimal control problem with state-variable inequality constraints given by Bryson, Denham, and Dreyfus is appropriately augmented, it is equivalent to the (different) set of conditions given by Jacobson, Lele, and Speyer. Relationships among the various multipliers are given.This work was done at NASA Ames Research Center, Moffett Field, California, under a National Research Council Associateship.     

Extended convergence results for the method of multipliers for nonstrictly binding inequality constraints

In this paper, we extend the classical convergence and rate of convergence results for the method of multipliers for equality constrained problems to general inequality constrained problems, without assuming the strict complementarity hypothesis at the local optimal solution. Instead, we consider an alternative second-order sufficient condition for a strict local minimum, which coincides with the standard one in the case of strict complementary slackness. As a consequence, new stopping rules are derived in order to guarantee a local linear rate of convergence for the method, even if the current Lagrangian is only asymptotically minimized in this more general setting. These extended results allow us to broaden the scope of applicability of the method of multipliers, in order to cover all those problems admitting loosely binding constraints at some optimal solution. This fact is not meaningless, since in practice this kind of problem seems to be more the rule rather than the exception.In proving the different results, we follow the classical primaldual approach to the method of multipliers, considering the approximate minimizers for the original augmented Lagrangian as the exact solutions for some adequate approximate augmented Lagrangian. In particular, we prove a general uniform continuity property concerning both their primal and their dual optimal solution set maps, a property that could be useful beyond the scope of this paper. This approach leads to very simple proofs of the preliminary results and to a straight-forward proof of the main results.The author gratefully acknowledges the referees for their helpful comments and remarks. This research was supported by FONDECYT (Fondo Nacional de Desarrollo Científico y Technológico de Chile).     

Properties of the sequential gradient-restoration algorithm (SGRA), part 1: Introduction and comparison with related methods

The sequential gradient-restoration algorithm (SGRA) was developed in the late 1960s for the solution of equality-constrained nonlinear programs and has been successfully implemented by Miele and coworkers on many large-scale problems. The algorithm consists of two major sequentially applied phases. The first is a gradient-type minimization in a subspace tangent to the constraint surface, and the second is a feasibility restoration procedure. In Part 1, the original SGRA algorithm is described and is compared with two other related methods: the gradient projection and the generalized reduced gradient methods. Next, the special case of linear equalities is analyzed. It is shown that, in this case, only the gradient-type minimization phase is needed, and the SGRA becomes identical to the steepest-descent method. Convergence proofs for the nonlinearly constrained case are given in Part 2.Partial support for this work was provided by the Fund for the Promotion of Research at Technion, Israel Institute of Technology, Haifa, Israel.     

Application of the sequential gradient-restoration algorithm to thermal convective instability problems

The problem of the thermal stability of a horizontal incompressible fluid layer with linear and nonlinear temperature distributions is solved by using the sequential gradient-restoration algorithm developed for optimal control problems. The hydrodynamic boundary conditions for the layer include a rigid or free upper surface and a rigid lower surface. The resulting disturbing equations are solved as a Bolza problem in the calculus of variations. The results of the study are compared with the existing works in the literature.The authors acknowledge valuable discussions with Dr. A. Miele.     

Two-level primal-dual decomposition technique for large-scale nonconvex optimization problems with constraints

A two-level decomposition method for nonconvex separable optimization problems with additional local constraints of general inequality type is presented and thoroughly analyzed in the paper. The method is of primal-dual type, based on an augmentation of the Lagrange function. Previous methods of this type were in fact three-level, with adjustment of the Lagrange multipliers at one of the levels. This level is eliminated in the present approach by replacing the multipliers by a formula depending only on primal variables and Kuhn-Tucker multipliers for the local constraints. The primal variables and the Kuhn-Tucker multipliers are together the higher-level variables, which are updated simultaneously. Algorithms for this updating are proposed in the paper, together with their convergence analysis, which gives also indications on how to choose penalty coefficients of the augmented Lagrangian. Finally, numerical examples are presented.     

Primal-dual row-action method for convex programming

We present a primal-dual row-action method for the minimization of a convex function subject to general convex constraints. Constraints are used one at a time, no changes are made in the constraint functions and their Jacobian matrix (thus, the row-action nature of the algorithm), and at each iteration a subproblem is solved consisting of minimization of the objective function subject to one or two linear equations. The algorithm generates two sequences: one of them, called primal, converges to the solution of the problem; the other one, called dual, approximates a vector of optimal KKT multipliers for the problem. We prove convergence of the primal sequence for general convex constraints. In the case of linear constraints, we prove that the primal sequence converges at least linearly and obtain as a consequence the convergence of the dual sequence.The research of the first author was partially supported by CNPq Grant No. 301280/86.     

Two-Phase Model Algorithm with Global Convergence for Nonlinear Programming

The family of feasible methods for minimization with nonlinear constraints includes the nonlinear projected gradient method, the generalized reduced gradient method (GRG), and many variants of the sequential gradient restoration algorithm (SGRA). Generally speaking, a particular iteration of any of these methods proceeds in two phases. In the restoration phase, feasibility is restored by means of the resolution of an auxiliary nonlinear problem, generally a nonlinear system of equations. In the minimization phase, optimality is improved by means of the consideration of the objective function, or its Lagrangian, on the tangent subspace to the constraints. In this paper, minimal assumptions are stated on the restoration phase and the minimization phase that ensure that the resulting algorithm is globally convergent. The key point is the possibility of comparing two successive nonfeasible iterates by means of a suitable merit function that combines feasibility and optimality. The merit function allows one to work with a high degree of infeasibility at the first iterations of the algorithm. Global convergence is proved and a particular implementation of the model algorithm is described.     

New formulation of iterative substructuring methods without Lagrange multipliers: Neumann–Neumann and FETI

This article is devoted to introduce a new approach to iterative substructuring methods that, without recourse to Lagrange multipliers, yields positive definite preconditioned formulations of the Neumann–Neumann and FETI types. To my knowledge, this is the first time that such formulations have been made without resource to Lagrange multipliers. A numerical advantage that is concomitant to such multipliers‐free formulations is the reduction of the degrees of freedom associated with the Lagrange multipliers. Other attractive features are their generality, directness, and simplicity. The general framework of the new approach is rather simple and stems directly from the discretization procedures that are applied; in it, the differential operators act on discontinuous piecewise‐defined functions. Then, the Lagrange multipliers are not required because in such an environment the functions‐discontinuities are not an anomaly that need to be corrected. The resulting algorithms and equations‐systems are also derived with considerable detail. © 2007 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2008     

On sufficient second order optimality conditions in multiobjective optimization

A second order sufficient optimality criterion is presented for a multiobjective problem subject to a constraint given just as a set. To this aim, we first refine known necessary conditions in such a way that the sufficient ones differ by the replacement of inequalities by strict inequalities. Furthermore, we show that no relationship holds between this criterion and a sufficient multipliers rule, when the constraint is described by inequalities and equalities. Finally, improvements of this criterion for the unconstrained case are presented, stressing the differences with single-objective optimization     

Parallel alternating direction multiplier decomposition of convex programs

This paper describes two specializations of the alternating direction method of multipliers: the alternating step method and the epigraphic projection method. The alternating step method applies to monotropic programs, while the epigraphic method applies to general block-separable convex programs, including monotropic programs as a special case. The epigraphic method resembles an earlier parallel method due to Spingarn, but solves a larger number of simpler subproblems at each iteration. This paper gives convergence results for both the alternating step and epigraphic methods, and compares their performance on random dense separable quadratic programs.Some of the research described here was performed at the Massachusetts Institute of Technology and was supported by the Army Research Office under Grant DAAL03-86-K-0171 and the National Science Foundation under Grant ECS-85-19058. This portion of the work was supervised by Dimitri P. Bertsekas, for whose support the author is grateful.     

Updating the Multipliers Associated with Inequality Constraints in an Augmented Lagrangian Multiplier Method

This paper contributes to the development of the field of augmented Lagrangian multiplier methods for general nonlinear programming by introducing a new update for the multipliers corresponding to inequality constraints. The update maintains naturally the nonnegativity of the multipliers without the need for a positive-orthant projection, as a result of the verification of the first-order necessary conditions for the minimization of a modified augmented Lagrangian penalty function.In the new multiplier method, the roles of the multipliers are interchanged: the multipliers corresponding to the inequality constraints are updated explicitly, whereas the multipliers corresponding to the equality constraints are approximated implicitly. It is shown that the basic properties of local convergence of the traditional multiplier method are valid also for the proposed method.     

On constraint qualifications for second-order optimality conditions depending on a single Lagrange multiplier

We present new constraint qualifications (CQs) to ensure the validity of some well-known second-order optimality conditions. Our main interest is on second-order conditions that can be associated with numerical methods for solving constrained optimization problems. Such conditions depend on a single Lagrange multiplier, instead of the whole set of Lagrange multipliers. For each condition, we characterize the weakest CQ that guarantees its fulfillment at local minimizers, while proposing new weak conditions implying them. Relations with other CQs are discussed.