SEQUENTIAL QUADRATIC PROGRAMMING METHODS FOR OPTIMAL CONTROL PROBLEMS WITH STATE CONSTRAINTS

A Kind of direct methods is presented for the solution of optimal control problems with state constraints.These methods are sequential quadratic programming methods.At every iteration a quadratic programming which is obtained by quadratic approximation to Lagrangian function and Linear approximations to constraints is solved to get a search direction for a merit function.The merit function is formulated by augmenting the Lagrangian funetion with a penalty term.A line search is carried out along the search direction to determine a step length such that the merit function is decreased.The methods presented in this paper include continuous sequential quadratic programming methods and discreate sequential quadrade programming methods.     

Construction of optimal order nonlinear solvers using inverse interpolation

There is a vast literature on finding simple roots of nonlinear equations by iterative methods. These methods can be classified by order, by the information used or by efficiency. There are very few optimal methods, that is methods of order 2^m requiring m + 1 function evaluations per iteration. Here we give a general way to construct such methods by using inverse interpolation and any optimal two-point method. The presented optimal multipoint methods are tested on numerical examples and compared to existing methods of the same order of convergence.     

Piecewise affine approximations for the control of a one-reservoir hydroelectric system

We analyze the computation of optimal and approximately optimal policies for a discrete-time model of a single reservoir whose discharges generate hydroelectric power. Inflows in successive periods are random variables. Revenue from hydroelectric production is represented by a piecewise linear function. We use the special structure of optimal policies, together with piecewise affine approximations of the optimal return functions at each stage of dynamic programming, to decrease the computational effort by an order of magnitude compared with ordinary value iteration. The method is then used to obtain easily computable lower and upper bounds on the value function of an optimal policy, and a policy whose value function is between the bounds.     

OPTIMAL ERROR ESTIMATES OF THE PARTITION OF UNITY METHOD WITH LOCAL POLYNOMIAL APPROXIMATION SPACES

In this paper, we provide a theoretical analysis of the partition of unity finite elementmethod (PUFEM), which belongs to the family of meshfree methods. The usual erroranalysis only shows the order of error estimate to the same as the local approximations[12].Using standard linear finite element base functions as partition of unity and polynomials aslocal approximation space, in 1-d case, we derive optimal order error estimates for PUFEMinterpolants. Our analysis show that the error estimate is of one order higher than thelocal approximations. The interpolation error estimates yield optimal error estimates forPUFEM solutions of elliptic boundary value problems.     

Optimal-order quadratic interpolation in vertices of unstructured triangulations

We study the problem of Lagrange interpolation of functions of two variables by quadratic polynomials under the condition that nodes of interpolation are vertices of a triangulation. For an extensive class of triangulations we prove that every inner vertex belongs to a local six-tuple of vertices which, used as nodes of interpolation, have the following property: For every smooth function there exists a unique quadratic Lagrange interpolation polynomial and the related local interpolation error is of optimal order. The existence of such six-tuples of vertices is a precondition for a successful application of certain post-processing procedures to the finite-element approximations of the solutions of differential problems. This work was supported by the grant GA ČR 103/05/0292.     

Q-learning and policy iteration algorithms for stochastic shortest path problems

We consider the stochastic shortest path problem, a classical finite-state Markovian decision problem with a termination state, and we propose new convergent Q-learning algorithms that combine elements of policy iteration and classical Q-learning/value iteration. These algorithms are related to the ones introduced by the authors for discounted problems in Bertsekas and Yu (Math. Oper. Res. 37(1):66-94, 2012). The main difference from the standard policy iteration approach is in the policy evaluation phase: instead of solving a linear system of equations, our algorithm solves an optimal stopping problem inexactly with a finite number of value iterations. The main advantage over the standard Q-learning approach is lower overhead: most iterations do not require a minimization over all controls, in the spirit of modified policy iteration. We prove the convergence of asynchronous deterministic and stochastic lookup table implementations of our method for undiscounted, total cost stochastic shortest path problems. These implementations overcome some of the traditional convergence difficulties of asynchronous modified policy iteration, and provide policy iteration-like alternative Q-learning schemes with as reliable convergence as classical Q-learning. We also discuss methods that use basis function approximations of Q-factors and we give an associated error bound.     

(Approximate) iterated successive approximations algorithm for sequential decision processes

The paper proves the convergence of (Approximate) Iterated Successive Approximations Algorithm for solving infinite-horizon sequential decision processes satisfying the monotone contraction assumption. At every stage of this algorithm, the value function at hand is used as a terminal reward to determine an (approximately) optimal policy for the one-period problem. This policy is then iterated for a (finite or infinite) number of times and the resulting return function is used as the starting value function for the next stage of the scheme. This method generalizes the standard successive approximations, policy iteration and Denardo’s generalization of the latter.     

Constrained interpolation and smoothing

Numerical and theoretical questions related to constrained interpolation and smoothing are treated. The prototype problem is that of finding the smoothest convex interpolant to given univariate data. Recent results have shown that this convex programming problem with infinite constraints can be recast as a finite parametric nonlinear system whose solution is closely related to the second derivative of the desired interpolating function. This paper focuses on the analysis of numerical techniques for solving the nonlinear system and on the theoretical issues that arise when certain extensions of the problem are considered. In particular, we show that two standard iteration techniques, the Jacobi and Gauss-Seidel methods, are globally convergent when applied to this problem. In addition we use the problem structure to develop an efficient implementation of Newton's method and observe consistent quadratic convergence. We also develop a theory for the existence, uniqueness, and representation of solutions to the convex interpolation problem with nonzero lower bounds on the second derivative (strict convexity). Finally, a smoothing spline analogue to the convex interpolation problem is studied with reference to the computation of convex approximations to noisy data.     

Optimal risk probability for first passage models in semi-Markov decision processes

This paper studies the risk minimization problem in semi-Markov decision processes with denumerable states. The criterion to be optimized is the risk probability (or risk function) that a first passage time to some target set doesn't exceed a threshold value. We first characterize such risk functions and the corresponding optimal value function, and prove that the optimal value function satisfies the optimality equation by using a successive approximation technique. Then, we present some properties of optimal policies, and further give conditions for the existence of optimal policies. In addition, a value iteration algorithm and a policy improvement method for obtaining respectively the optimal value function and optimal policies are developed. Finally, two examples are given to illustrate the value iteration procedure and essential characterization of the risk function.     

Smoothing methods for nonsmooth, nonconvex minimization

We consider a class of smoothing methods for minimization problems where the feasible set is convex but the objective function is not convex, not differentiable and perhaps not even locally Lipschitz at the solutions. Such optimization problems arise from wide applications including image restoration, signal reconstruction, variable selection, optimal control, stochastic equilibrium and spherical approximations. In this paper, we focus on smoothing methods for solving such optimization problems, which use the structure of the minimization problems and composition of smoothing functions for the plus function (x)₊. Many existing optimization algorithms and codes can be used in the inner iteration of the smoothing methods. We present properties of the smoothing functions and the gradient consistency of subdifferential associated with a smoothing function. Moreover, we describe how to update the smoothing parameter in the outer iteration of the smoothing methods to guarantee convergence of the smoothing methods to a stationary point of the original minimization problem.     

Optimal synthesis in grid schemes for quasi-convex approximation functions

A single grid algorithm which constructs the value function and the optimal synthesis, based on a local quasi-differential approximations of the Hamilton-Jacobi equation, is considered. The optimal synthesis is generated by the method of extremal translation in the direction of generalized gradients. The quasi-convex approximation functions, for which it is possible to use a linear dependence of the space-time steps for correct interpolation of the nodal optimal control values, thus substantially reducing the amount of computation, simplifying the finite-difference formulae and permitting the use of simple operators involving constructions of the method of least squares, are investigated.     

Accurate fourteenth-order methods for solving nonlinear equations

We establish new iterative methods of local order fourteen to approximate the simple roots of nonlinear equations. The considered three-step eighth-order construction can be viewed as a variant of Newton’s method in which the concept of Hermite interpolation is used at the third step to reduce the number of evaluations. This scheme includes three evaluations of the function and one evaluation of the first derivative per iteration, hence its efficiency index is 1.6817. Next, the obtained approximation for the derivative of the Newton’s iteration quotient is again taken into consideration to furnish novel fourteenth-order techniques consuming four function and one first derivative evaluations per iteration. In providing such new fourteenth-order methods, we also take a special heed to the computational burden. The contributed four-step methods have 1.6952 as their efficiency index. Finally, various numerical examples are given to illustrate the accuracy of the developed techniques.     

Rates of convergence for adaptive Newton methods

We consider Newton-type methods for constrained optimization problems in infinite-dimensional spaces, where at each iteration the first and second derivatives and the feasible set are approximated. The approximations can change at each iteration and conditions are given under which linear and superlinear rates of convergence of the iterates to the optimal point hold. Several applications are discussed.     

Flexible piecewise approximations based on partition of unity

In this paper, we study a flexible piecewise approximation technique based on the use of the idea of the partition of unity. The approximations are piecewisely defined, globally smooth up to any order, enjoy polynomial reproducing conditions, and satisfy nodal interpolation conditions for function values and derivatives of any order. We present various properties of the approximations, that are desirable properties for optimal order convergence in solving boundary value problems. AMS subject classification 65N30, 65D05Weimin Han: Corresponding author. The work of this author was partially supported by NSF under grant DMS-0106781.Wing Kam Liu: The work of this author was supported by NSF.     

An algorithm for approximating piecewise linear concave functions from sample gradients

An effective algorithm for solving stochastic resource allocation problems is to build piecewise linear, concave approximations of the recourse function based on sample gradient information. Algorithms based on this approach are proving useful in application areas such as the newsvendor problem, physical distribution and fleet management. These algorithms require the adaptive estimation of the approximations of the recourse function that maintain concavity at every iteration. In this paper, we prove convergence for a particular version of an algorithm that produces approximations from stochastic gradient information while maintaining concavity.     

Modified Ostrowski’s method with eighth-order convergence and high efficiency index

In this paper, based on Newton’s method, we derive a modified Ostrowski’s method with an eighth-order convergence for solving the simple roots of nonlinear equations by Hermite interpolation methods. Per iteration this method requires three evaluations of the function and one evaluation of its first derivative, which implies that the efficiency index of the developed method is 1.682, which is optimal according to Kung and Traub’s conjecture Kung and Traub (1974) [2]. Numerical comparisons are made to show the performance of the derived method, as shown in the illustrative examples.     

Lower bounding aggregation and direct computation for an infinite horizon one-reservoir model

We present a specialized policy iteration method for the computation of optimal and approximately optimal policies for a discrete-time model of a single reservoir whose discharges generate hydroelectric power. The model is described in (Lamond et al., 1995) and (Drouin et al., 1996), where the special structure of optimal policies is given and an approximate value iteration method is presented, using piecewise affine approximations of the optimal return functions. Here, we present a finite method for computing an optimal policy in O(n³) arithmetic operations, where n is the number of states in the associated Markov decision process, and a finite method for computing a lower bound on the optimal value function in O(m²n) where m is the number of nodes of the piecewise affine approximation.     

Polynomial particular solutions for certain partial differential operators

In this article, we consider a variant of the Dual Reciprocity Method (DRM) for solving boundary value problems based on approximating source terms by polynomials other than the traditional basis functions. The use of pseudo‐spectral approximations and symbolic methods enables us to obtain highly accurate results without solving the often ill‐conditioned equations that occur when radial basis function approximations are used. When the given partial differential equation is either Poisson's equation or an inhomogeneous Helmholtz‐type equation, we are able to obtain either closed form particular solutions or efficient recursive algorithms. Using the particular solutions, we convert the inhomogeneous equations to homogeneous. The resulting homogeneous equations are then amenable to solution by boundary‐type methods such as the Boundary Element Method (BEM) or the Method of Fundamental Solutions (MFS). Using the MFS, we provide numerical solutions to a variety of boundary value problems in R² and R³ . Using this approach, we can achieve high accuracy with a modest number of interpolation and collocation points. © 2002 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 19: 112–133, 2003     

Projected equation methods for approximate solution of large linear systems

We consider linear systems of equations and solution approximations derived by projection on a low-dimensional subspace. We propose stochastic iterative algorithms, based on simulation, which converge to the approximate solution and are suitable for very large-dimensional problems. The algorithms are extensions of recent approximate dynamic programming methods, known as temporal difference methods, which solve a projected form of Bellman’s equation by using simulation-based approximations to this equation, or by using a projected value iteration method.     

Optimal threshold probability and expectation in semi-Markov decision processes

We consider undiscounted semi-Markov decision process with a target set and our main concern is a problem minimizing threshold probability. We formulate the problem as an infinite horizon case with a recurrent class. We show that an optimal value function is a unique solution to an optimality equation and there exists a stationary optimal policy. Also several value iteration methods and a policy improvement method are given in our model. Furthermore, we investigate a relationship between threshold probabilities and expectations for total rewards.