A new technique for linear static state estimation based on weighted least absolute value approximations

This paper presents a new technique for solving the problem of linear static state estimation, based on weighted least absolute value (WLAV). A set ofm optimality equations is obtained, wherem=number of measurements, based on minimizing a WLAV performance index involvingn unknown state variables,m>n. These equations are solved using the left pseudo-inverse transformation, least-square sense, to obtain approximately the residual of each measurement.Ifk is the rank of the matrixH,k=n, we choose among the optimality equations a number of equations equal to the rankk and having the smallest residuals. The solution of thesen equations inn unknowns yields the best WLAV estimation. A numerical example is reported; the results for this example are obtained by using both WLS and WLAV techniques. It is shown that the best WLAV approximation is superior to the best WLS approximation when estimating the true form of data containing some inaccurate observations.This work was supported by the Natural Science and Engineering Research Council of Canada, Grant No. A4146.     

A Generalized Quasilinearization Method for Nonlinear Second-Order Impulsive Differential Equations Involving the <Emphasis Type="Italic">p</Emphasis>-Laplacian

Using variational method and lower and upper solutions, we get a generalized quasilinearization method which construct an iterative scheme converging uniformly to a solution of a nonlinear second-order impulsive differential equations involving the p-Laplacian, and converging quadratically when p=2.     

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.     

Bilinear separation of two sets inn-space

The NP-complete problem of determining whether two disjoint point sets in then-dimensional real spaceR ⁿ can be separated by two planes is cast as a bilinear program, that is minimizing the scalar product of two linear functions on a polyhedral set. The bilinear program, which has a vertex solution, is processed by an iterative linear programming algorithm that terminates in a finite number of steps a point satisfying a necessary optimality condition or at a global minimum. Encouraging computational experience on a number of test problems is reported.This material is based on research supported by Air Force Office of Scientific Research grant AFOSR-89-0410, National Science Foundation grant CCR-9101801, and Air Force Laboratory Graduate Fellowship SSN 531-56-2969.     

Intermediate-thrust arcs and their optimality in a central,time-invariant force field

This paper presents the general equations of the intermediate-thrust arcs in a general, time-invariant, central force field. Two families of planar arcs, namely, the family of Lawden's spirals in the equatorial plane of an oblate planet and the family of intermediate-thrust arcs in a gravitational field of the form /r ⁿ , have been considered in detail. The Kelley-Contensou condition has been used to test their optimality condition. It is shown that, in the first case, there exist portions of the arcs at a finite distance satisfying the condition, while, in the second case, the entire family satisfies the condition forn 3. Hence, in a perturbed Newtonian gravitational force field, the intermediate-thrust arcs, under certain favorable conditions, can be part of an optimal trajectory.     

Optimality equations and sensitive optimality in bounded Markov decision processes 1

This paper consider Markov decision processes with countable state space, compact action spaces and a bounded reward function. Under some recurrence and connectedness condition, including the simultaneous Döblin condition, we prove the existence of bounded solutions of the optimality equations which arise for the multichain case in connection with the average reward criterion and sensitive optimality criteria, and we give a characterization of the sets of n-average optimal decision rules.     

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.     

Iterative solution of the secular equation

The secular equation with real symmetric positive definite n × n matrix is transformed into a system of n ² quadratic equations for which it is possible to construct a convergent procedure realizing an iterative solution. An example of the numerical realization of the method for solving the problem of determining the electronic energy spectrum is given.     

Parameter estimation in systems of differential equations,based on three-way data arrays and random time changes

Consider a system of n₁ × n₂ differential equations depending on a vector θ of unknown parameters. We suggest an iterative estimation procedure for θ, based on a three-way array of observations. The method involves random time changes driven by multidimensional integrated Ornstein-Uhlenbeck processes.     

Iterative Estimation of the Extreme Value Index

Let {X_n, n ≥ 1} be a sequence of independent random variables with common continuous distribution function F having finite and unknown upper endpoint. A new iterative estimation procedure for the extreme value index γ is proposed and one implemented iterative estimator is investigated in detail, which is asymptotically as good as the uniform minimum varianced unbiased estimator in an ideal model. Moreover, the superiority of the iterative estimator over its non iterated counterpart in the non asymptotic case is shown in a simulation study.AMS 2000 Subject Classification: 62G32Supported by Swiss National Science foundation.     

Parallel computation of two-point boundary-value problems via particular solutions

Nonlinear two-point boundary-value problems (TPBVP) can be reduced to the iterative solution of a sequence of linear problems by means of quasilinearization techniques. Therefore, the efficient solution of linear problems is the key to the efficient solution of nonlinear problems.Among the techniques available for solving linear two-point boundary-value problems, the method of particular solutions (MPS) is particularly attractive in that it employs only one differential system, the original nonhomogeneous system, albeit with different initial conditions. This feature of MPS makes it ideally suitable for implementation on parallel computers in that the following requirements are met: the computational effort is subdivided into separate tasks (particular solutions) assigned to the different processors; the tasks have nearly the same size; there is little intercommunication between the tasks.For the TPBVP, the speedup achievable is ofO(n), wheren is the dimension of the state vector, hence relatively modest for the differential systems of interest in trajectory optimization and guidance. This being the case, we transform the TPBVP into a multi-point boundary-value problem (MPBVP) involvingm time subintervals, withm–1 continuity conditions imposed at the interface of contiguous subintervals. For the MPBVP, the speedup achievable is ofO(mn), hence substantially higher than that achievable for the TPBVP. It reduces toO(m) if the parallelism is implemented only in the time domain and not in the state domain.A drawback of the multi-point approach is that it requires the solution of a large linear algebraic system for the constants of the particular solutions. This drawback can be offset by exploiting the particular nature of the interface conditions: if the vector of constants for the first subinterval is known, the vector of constants for the subsequent subintervals can be obtained with linear transformations. Using decomposition techniques together with the discrete version of MPS, the size of the linear algebraic system for the multi-point case becomes the same as that for the two-point case.Numerical tests on the Intel iPSC/860 computer show that substantial speedup can be achieved via parallel algorithms vis-a-vis sequential algorithms. Therefore, the present technique has considerable interest for real-time trajectory optimization and guidance.Dedicated to the Memory of Professor Jan M. SkowronskiThis paper, based on Refs. 1–3, is a much condensed version of the material contained in these references.The technical assistance of the Research Center on Parallel Computation of Rice University, Houston, Texas is gratefully acknowledged.     

Two combinatorial problems in the plane

The authors discuss two problems involvingn points in the plane and thet lines they form.     

A posteriori error estimates of hp spectral element methods for optimal control problems with L2-norm state constraint

In this paper, we investigate a distributed optimal control problem governed by elliptic partial differential equations with L²-norm constraint on the state variable. Firstly, the control problem is approximated by hp spectral element methods, which combines the advantages of the finite element methods with spectral methods; then, the optimality conditions of continuous system and discrete system are presented, respectively. Next, hp a posteriori error estimates are derived for the coupled state and control approximation. In the end, a projection gradient iterative algorithm is given, which solves the optimal control problems efficiently. Numerical experiments are carried out to confirm that the numerical results are in good agreement with the theoretical results.

     

A Short Note on the Quasilinearization Method for Fractional Differential Equations

Recent literature shows that for certain classes of fractional differential equations the monotone iterative technique fails to guarantee the quadratic convergence of the quasilinearization method. The present work proves the quadratic convergence of the quasilinearization method and the existence and uniqueness of the solution of such a class of fractional differential equations. Our analysis depends upon the classical Kantorovich theorem on Newton's method. Various examples are discussed in order to illustrate our approach.     

Extensions of CGS algorithms: Generalized least-square solutions

The CGS (conjugate Gram-Schmidt) algorithms of Hestenes and Stiefel are formulated so as to obtain least-square solutions of a system of equationsg(x)=0 inn independent variables. Both the linear caseg(x)=Ax–h and the nonlinear case are discussed. In the linear case, a least-square solution is obtained in no more thann steps, and a method of obtaining the least-square solution of minimum length is given. In the nonlinear case, the CGS algorithm is combined with the Gauss-Newton process to minimize sums of squares of nonlinear functions. Results of numerical experiments with several versions of CGS on test functions indicate that the algorithms are effective.The author wishes to express appreciation and to acknowledge the ideas and help of Professor M. R. Hestenes which made this paper possible.     

A family of quasi-Newton methods for unconstrained optimization problems

ABSTRACT

In this paper, we present a class of approximating matrices as a function of a scalar parameter that includes the Davidon-Fletcher-Powell and Broyden-Fletcher-Goldfarb-Shanno methods as special cases. A powerful iterative descent method for finding a local minimum of a function of several variables is described. The new method maintains the positive definiteness of the approximating matrices. For a region in which the function depends quadratically on the variables, no more than n iterations are required, where n is the number of variables. A set of computational results that verifies the superiority of the new method are presented.     

On Hashin–Shtrikman bounds for mixtures of two isotropic materials

In the context of stationary diffusion equation we calculate explicitly the optimal microstructure for the Hashin–Shtrikman energy bound in the case of two isotropic phases with prescribed ratio, in three dimensions. A similar, but more general problem arises in the study of optimal design in conductivity with multiple state equations. Here, the necessary condition of optimality leads to a finite-dimensional optimisation problem which extends the problem of Hashin–Shtrikman bounds, which can be solved explicitly, as well.These calculations have important applications to the optimality criteria method for numerical solution of optimal design problems with multiple state equations. In this iterative algorithm, the presented results enable one to calculate explicitly the update of design variables, similar to the problems with one state equation. Therefore, its implementation is simple, showing nice convergence results on a number of examples, two of them being demonstrated here.     

Equations for the Missing Boundary Values in the Hamiltonian Formulation of Optimal Control Problems

Partial differential equations for the unknown final state and initial costate arising in the Hamiltonian formulation of regular optimal control problems with a quadratic final penalty are found. It is shown that the missing boundary conditions for Hamilton’s canonical ordinary differential equations satisfy a system of first-order quasilinear vector partial differential equations (PDEs), when the functional dependence of the H-optimal control in phase-space variables is explicitly known. Their solutions are computed in the context of nonlinear systems with ℝ ⁿ -valued states. No special restrictions are imposed on the form of the Lagrangian cost term. Having calculated the initial values of the costates, the optimal control can then be constructed from on-line integration of the corresponding 2n-dimensional Hamilton ordinary differential equations (ODEs). The off-line procedure requires finding two auxiliary n×n matrices that generalize those appearing in the solution of the differential Riccati equation (DRE) associated with the linear-quadratic regulator (LQR) problem. In all equations, the independent variables are the finite time-horizon duration T and the final-penalty matrix coefficient S, so their solutions give information on a whole two-parameter family of control problems, which can be used for design purposes. The mathematical treatment takes advantage from the symplectic structure of the Hamiltonian formalism, which allows one to reformulate Bellman’s conjectures concerning the “invariant-embedding” methodology for two-point boundary-value problems. Results for LQR problems are tested against solutions of the associated differential Riccati equation, and the attributes of the two approaches are illustrated and discussed. Also, nonlinear problems are numerically solved and compared against those obtained by using shooting techniques.     

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.