Reduction of total-cost and average-cost MDPs with weakly continuous transition probabilities to discounted MDPs

This note describes sufficient conditions under which total-cost and average-cost Markov decision processes (MDPs) with general state and action spaces, and with weakly continuous transition probabilities, can be reduced to discounted MDPs. For undiscounted problems, these reductions imply the validity of optimality equations and the existence of stationary optimal policies. The reductions also provide methods for computing optimal policies. The results are applied to a capacitated inventory control problem with fixed costs and lost sales.     

Strong convergence and certain control conditions for modified Mann iteration

In this paper we propose a new modified Mann iteration for computing fixed points of nonexpansive mappings in a Banach space setting. This new iterative scheme combines the modified Mann iteration introduced by Kim and Xu [T.H. Kim, H.K. Xu, Strong convergence of modified Mann iterations, Nonlinear Anal. 61 (2005) 51–60] and the viscosity approximation method introduced by Moudafi [A. Moudafi, Viscosity approximation methods for fixed-points problems, J. Math. Anal. Appl. 241 (2000) 46–55]. We give certain different control conditions for the modified Mann iteration. Strong convergence in a uniformly smooth Banach space is established.     

Accelerating the convergence of value iteration by using partial transition functions

This work proposes an algorithm that makes use of partial information to improve the convergence properties of the value iteration algorithm in terms of the overall computational complexity. The algorithm iterates on a series of increasingly refined approximate models that converges to the true model according to an optimal linear rate, which coincides with the convergence rate of the original value iteration algorithm. The paper investigates the properties of the proposed algorithm and features a series of switchover queue examples which illustrates the efficacy of the method.     

On the rate of convergence of infinite horizon discounted optimal value functions

In this paper we investigate the rate of convergence of the optimal value function of an infinite horizon discounted optimal control problem as the discount rate tends to zero. Using the Integration Theorem for Laplace transformations we provide conditions on averaged functionals along suitable trajectories yielding quadratic pointwise convergence. From this we derive under appropriate controllability conditions criteria for linear uniform convergence of the value functions on control sets. Applications of these results are given and an example is discussed in which both linear and slower rates of convergence occur depending on the cost functional.     

A forward algorithm and planning horizon procedure for the production smoothing problem without inventory

We develop a forward algorithm for solving and finding planning horizons for the infinite horizon version of the deterministic production smoothing problem without inventory. This model approximates the real world situation for highly obsolescent or perishable commodities such as newspapers and fresh produce. Computational results show that the algorithm is linear in problem length while linear programming is at least quadratic.     

On the convergence of policy iteration for controlled diffusions

The convergence of an approximation scheme known as policy iteration has been demonstrated for controlled diffusions by Fleming, Puterman, and Bismut. In this paper, we show that this approximation scheme is equivalent to the Newton-Kantorovich iteration for solving the optimality equation and exploit this equivalence to obtain a new proof of convergence. Estimates of the rate of convergence of this procedure are also obtained.This research was partially supported by NRC Grant No. A-3609.     

Improvement of a convergence condition for the Durand-Kerner iteration

The Durand-Kerner iteration is a well-known simultaneous method for approximation of (simple) zeros of a polynomial. By relating Weierstrass' correction and the minimal distance between approximations practical conditions for convergence have been obtained. These conditions also ensure the existence of isolating discs for the polynomial roots, i.e. each iteration step gives a refined set of inclusion discs. In this paper refined conditions of convergence are given.     

A rolling horizon approach for disruption management of railway rolling stock

This paper deals with real-time disruption management of rolling stock in passenger railway transportation. We describe a generic framework for dealing with disruptions of railway rolling stock schedules. The framework is presented as an online combinatorial decision problem, where the uncertainty of a disruption is modeled by a sequence of information updates. To decompose the problem and to reduce the computation time, we propose a rolling horizon approach: rolling stock decisions are only considered if they are within a certain time horizon from the time of rescheduling. The schedules are then revised as time progresses and new information becomes available. We extend an existing model for rolling stock scheduling to the specific requirements of the real-time situation, and we apply it in the rolling horizon framework. We perform computational tests on instances constructed from real-life cases of Netherlands Railways (NS), the main operator of passenger trains in the Netherlands. We explore the consequences of different settings of the approach for the trade-off between solution quality and computation time.     

Mann迭代和具误差的Ishikawa迭代收敛性的等价定理

在迭代参数仅满足(?) supβ_n(k/L(L+1)),(?)α_n=0和(?)α_n=+∞的条件下,用不同与于已有的方法证明了任意实Banach空间中的Lipschitz强伪压缩算子的Mann迭代和具误差的Ishikawa迭代收敛是等价的.这推广和改进了目前需假设limβ_n=0和两迭代程序的初始点的取值需相同条件下的已知结果.     

On the convergence of higher-order orthogonal iteration

The higher-order orthogonal iteration (HOOI) has been popularly used for finding a best low-multilinear rank approximation of a tensor. However, its convergence is still an open question. In this paper, we first analyse a greedy HOOI, which updates each factor matrix by selecting from the best candidates one that is closest to the current iterate. Assuming the existence of a block-nondegenerate cluster point, we establish its global iterate sequence convergence through the so-called Kurdyka–?ojasiewicz property. In addition, we show that if the starting point is sufficiently close to any block-nondegenerate globally optimal solution, the greedy HOOI produces an iterate sequence convergent to a globally optimal solution. Relating the iterate sequence by the original HOOI to that by the greedy HOOI, we then show that the original HOOI has global convergence on the multilinear subspace sequence and thus positively address the open question.     

Strong convergence of the composite Halpern iteration

Let C be a closed convex subset of a uniformly smooth Banach space E and let T:C→C be a nonexpansive mapping with a nonempty fixed points set. Given a point u∈C, the initial guess x₀∈C is chosen arbitrarily and given sequences , and in (0,1), the following conditions are satisfied:

(i)

;

(ii)

αn→0, βn→0 and 0<a?γn, for some a∈(0,1);

(iii)

, and . Let be a composite iteration process defined by

     

The value iteration algorithm is not strongly polynomial for discounted dynamic programming

This note provides a simple example demonstrating that, if exact computations are allowed, the number of iterations required for the value iteration algorithm to find an optimal policy for discounted dynamic programming problems may grow arbitrarily quickly with the size of the problem. In particular, the number of iterations can be exponential in the number of actions. Thus, unlike policy iterations, the value iteration algorithm is not strongly polynomial for discounted dynamic programming.     

Lower bound for the convergence rate of nonstationary Jacobi-like iteration

Stationary and nonstationary Jacobi-like iterative processes for solving systems of linear algebraic equations are examined. For a system whose coefficient matrix A is an H-matrix, it is shown that the convergence rate of any Jacobi-like process is at least as high as that of the point Jacobi method as applied to a system with 〈A〉 as the coefficient matrix, where 〈A〉 is a comparison matrix of A.     

On the quadratic convergence of Kogbetliantz's algorithm for computing the singular value decomposition

It is shown that the cyclic Kogbetliantz algorithm ultimately converges quadratically when no pathologically close singular values are present.     

A wider convergence area for the MSTMAOR iteration methods for LCP

In this paper, based on the Hermitian and skew-Hermitian splitting, we give a generalized modified Hermitian and skew-Hermitian splitting (GMHSS) method to solve singular complex symmetric linear systems, this method has two parameters. We give the semi-convergent conditions, and some numerical experiments are given to illustrate the efficiency of this method.     

On the convergence of He's variational iteration method

In this work we will consider He's variational iteration method for solving second-order initial value problems. We will discuss the use of this approach for solving several important partial differential equations. This method is based on the use of Lagrange multipliers for identification of optimal value of a parameter in a functional. This procedure is a powerful tool for solving the large amount of problems. Using the variational iteration method, it is possible to find the exact solution or an approximate solution of the problem. This technique provides a sequence of functions which converges to the exact solution of the problem. Our emphasis will be on the convergence of the variational iteration method. In the current paper this scheme will be investigated in details and efficiency of the approach will be shown by applying the procedure on several interesting and important models.     

Improving the order of convergence od iteration functions

Improving methods for the order of convergence of iteration functions are give,. Using these methods new third or fourth-order root-finding methods for a single equation with a multiple root are derived. Numerical examples are given.     

Analyzing the convergence factor of residual inverse iteration

We will establish here a formula for the convergence factor of the method called residual inverse iteration, which is a method for nonlinear eigenvalue problems and a generalization of the well-known inverse iteration. The formula for the convergence factor is explicit and involves quantities associated with the eigenvalue to which the iteration converges, in particular the eigenvalue and eigenvector. Residual inverse iteration allows for some freedom in the choice of a vector w _k and we can use the formula for the convergence factor to analyze how it depends on the choice of w _k . We also use the formula to illustrate the convergence when the shift is close to the eigenvalue. Finally, we explain the slow convergence for double eigenvalues by showing that under generic conditions, the convergence factor is one, unless the eigenvalue is semisimple. If the eigenvalue is semisimple, it turns out that we can expect convergence similar to the simple case.     

On the global convergence of Halley's iteration formula

A point-iterative process similar to, but structurally simpler than, Ostrowski's square root technique is examined. This process is shown to be globally convergent monotonically to the zeros of entire functions of genus 0 and 1 (and in certain cases of genus 2) which are real for real arguments and have only real zeros.