Illustrated review of convergence conditions of the value iteration algorithm and the rolling horizon procedure for average-cost MDPs

This paper is concerned with the links between the Value Iteration algorithm and the Rolling Horizon procedure, for solving problems of stochastic optimal control under the long-run average criterion, in Markov Decision Processes with finite state and action spaces. We review conditions of the literature which imply the geometric convergence of Value Iteration to the optimal value. Aperiodicity is an essential prerequisite for convergence. We prove that the convergence of Value Iteration generally implies that of Rolling Horizon. We also present a modified Rolling Horizon procedure that can be applied to models without analyzing periodicity, and discuss the impact of this transformation on convergence. We illustrate with numerous examples the different results. Finally, we discuss rules for stopping Value Iteration or finding the length of a Rolling Horizon. We provide an example which demonstrates the difficulty of the question, disproving in particular a conjectured rule proposed by Puterman.     

Affine invariant convergence results for Newton's method

We present a unified derivation of affine invariant convergence results for Newton's method. Initially we derive affine invariant forms of the perturbation lemma and a mean value theorem. With their aid we obtain an optimal radius of convergence for Newton's method, from which further radius of convergence estimates follow. From the Newton-Kantorovitch theorem we derive other estimates of the radius of convergence. We discuss estimation of the parameters in the expressions we have derived.     

Conditions d'interface pour les méthodes de décomposition de domaine pour le système d'Oseen en dimensions 2 et 3

We study domain decomposition methods for two- and three-dimensional Oseen equations. We propose pseudo-differential interface conditions which lead to the convergence of an additive Schwarz type method in a number of steps equal to the number of subdomains. These conditions are approximated by partial differential conditions for which convergence is proved. These results generalize previous works on scalar equations.     

An Elastic Frictional Contact Problem with Unilateral Constraint

We consider a mathematical model which describes the equilibrium of an elastic body in contact with two obstacles. We derive its weak formulation which is in a form of an elliptic quasi-variational inequality for the displacement field. Then, under a smallness assumption, we establish the existence of a unique weak solution to the problem. We also study the dependence of the solution with respect to the data and prove a convergence result. Finally, we consider an optimization problem associated with the contact model for which we prove the existence of a minimizer and a convergence result, as well.     

Overlapping approximation of the exponential function on the positive axis

We investigate properties of the exponential function concerning the overlapping approximation which was introduced in former papers. We give bounds for the rate of convergence of the sequence of least deviations and give an exact formula for the convergence speed in the case of only one knot on the positive axis.     

Inexact inverse subspace iteration for generalized eigenvalue problems

n this paper, we present an inexact inverse subspace iteration method for computing a few eigenpairs of the generalized eigenvalue problem Ax=λBx. We first formulate a version of inexact inverse subspace iteration in which the approximation from one step is used as an initial approximation for the next step. We then analyze the convergence property, which relates the accuracy in the inner iteration to the convergence rate of the outer iteration. In particular, the linear convergence property of the inverse subspace iteration is preserved. Numerical examples are given to demonstrate the theoretical results.     

Primal and dual predicted decrease approximation methods

We introduce the notion of predicted decrease approximation (PDA) for constrained convex optimization, a flexible framework which includes as special cases known algorithms such as generalized conditional gradient, proximal gradient, greedy coordinate descent for separable constraints and working set methods for linear equality constraints with bounds. The new scheme allows the development of a unified convergence analysis for these methods. We further consider a partially strongly convex nonsmooth model and show that dual application of PDA-based methods yields new sublinear convergence rate estimates in terms of both primal and dual objectives. As an example of an application, we provide an explicit working set selection rule for SMO-type methods for training the support vector machine with an improved primal convergence analysis.     

Gradient-type penalty method with inertial effects for solving constrained convex optimization problems with smooth data

We consider the problem of minimizing a smooth convex objective function subject to the set of minima of another differentiable convex function. In order to solve this problem, we propose an algorithm which combines the gradient method with a penalization technique. Moreover, we insert in our algorithm an inertial term, which is able to take advantage of the history of the iterates. We show weak convergence of the generated sequence of iterates to an optimal solution of the optimization problem, provided a condition expressed via the Fenchel conjugate of the constraint function is fulfilled. We also prove convergence for the objective function values to the optimal objective value. The convergence analysis carried out in this paper relies on the celebrated Opial Lemma and generalized Fejér monotonicity techniques. We illustrate the functionality of the method via a numerical experiment addressing image classification via support vector machines.     

Smoothing factor,order of prolongation and actual multigrid convergence

We consider the Fourier analysis of multigrid methods (of Galerkin type) for symmetric positive definite and semi-positive definite linear systems arising from the discretization of scalar partial differential equations (PDEs). We relate the so-called smoothing factor to the actual two-grid convergence rate and also to the convergence rate of the V-cycle multigrid. We derive a two-sided bound that defines an interval containing both the two-grid and V-cycle convergence rate. This interval is narrow and away from 1 when both the smoothing factor and an additional parameter are small enough. Besides the smoothing factor, the convergence mainly depends on the angle between the range of the prolongation and the eigenvectors of the system matrix associated with small eigenvalues. Nice V-cycle convergence is guaranteed if the tangent of this angle has an upper bound proportional to the eigenvalue, whereas nice two-grid convergence requires a bound proportional to the square root of the eigenvalue. We also discuss the well-known rule which relates the order of the prolongation to that of the differential operator associated to the problem. We first define a frequency based order which in most cases amounts to the so-called high frequency order as defined in Hemker (J Comput Appl Math 32:423–429, 1990). We give a firmer basis to the related order rule by showing that, together with the requirement of having the smoothing factor away from one, it provides necessary and sufficient conditions for having the two-grid convergence rate away from 1. A stronger condition is further shown to be sufficient for optimal convergence with the V-cycle. The presented results apply to rigorous Fourier analysis for regular discrete PDEs, and also to local Fourier analysis via the discussion of semi-positive systems as may arise from the discretization of PDEs with periodic boundary conditions.     

Convergence in distribution of random metric measure spaces (Λ-coalescent measure trees)

We consider the space of complete and separable metric spaces which are equipped with a probability measure. A notion of convergence is given based on the philosophy that a sequence of metric measure spaces converges if and only if all finite subspaces sampled from these spaces converge. This topology is metrized following Gromov’s idea of embedding two metric spaces isometrically into a common metric space combined with the Prohorov metric between probability measures on a fixed metric space. We show that for this topology convergence in distribution follows—provided the sequence is tight—from convergence of all randomly sampled finite subspaces. We give a characterization of tightness based on quantities which are reasonably easy to calculate. Subspaces of particular interest are the space of real trees and of ultra-metric spaces equipped with a probability measure. As an example we characterize convergence in distribution for the (ultra-)metric measure spaces given by the random genealogies of the Λ-coalescents. We show that the Λ-coalescent defines an infinite (random) metric measure space if and only if the so-called “dust-free”-property holds.     

Convergence of Normal Form Transformations: The Role of Symmetries

We discuss the convergence problem for coordinate transformations which take a given vector field into Poincaré–Dulac normal form. We show that the presence of linear or nonlinear Lie point symmetries can guarantee convergence of these normalizing transformations in a number of scenarios. As an application, we consider a class of bifurcation problems.     

Newton's method for singular constrained optimization problems

We consider an iterative procedure where at each iteration a constrained quadratic optimization problem is solved. A Goldstein type step length rule is incorporated in order to assure global convergence. We consider a class of minimization problems which are singular at the optimal point and show that locally the superlinear convergence rate is retained for a certain part of the iterations. These results are applied to problems with perturbed data. In the last section global convergence results are proven.     

The Carathéodory topology for multiply connected domains I

We consider the convergence of pointed multiply connected domains in the Carathéodory topology. Behaviour in the limit is largely determined by the properties of the simple closed hyperbolic geodesics which separate components of the complement. Of particular importance are those whose hyperbolic length is as short as possible which we call meridians of the domain. We prove continuity results on convergence of such geodesics for sequences of pointed hyperbolic domains which converge in the Carathéodory topology to another pointed hyperbolic domain. Using these we describe an equivalent condition to Carathéodory convergence which is formulated in terms of Riemann mappings to standard slit domains.     

On ideal convergence of double sequences in probabilistic normed spaces

The notion of ideal convergence is a generalization of statistical convergence which has been intensively investigated in last few years.For an admissible ideal ∮N× N,the aim of the present paper is to introduce the concepts of ∮-convergence and ∮*-convergence for double sequences on probabilistic normed spaces(PN spaces for short).We give some relations related to these notions and find condition on the ideal ∮ for which both the notions coincide.We also define ∮-Cauchy and ∮*-Cauchy double sequences on PN spaces and show that ∮-convergent double sequences are ∮-Cauchy on these spaces.We establish example which shows that our method of convergence for double sequences on PN spaces is more general.     

An Ulm-Like Cayley Transform Method for Inverse Eigenvalue Problems with Multiple Eigenvalues

We study the convergence of an Ulm-like Cayley transform method for solving inverse eigenvalue problems which avoids solving approximate Jacobian equations. Under the nonsingularity assumption of the relative generalized Jacobian matrices at the solution, a convergence analysis covering both the distinct and multiple eigenvalues cases is provided and the quadratical convergence is proved. Moreover, numerical experiments are given in the last section to illustrate our results.     

A globally convergent BFGS method for nonlinear monotone equations without any merit functions

Since 1965, there has been significant progress in the theoretical study on quasi-Newton methods for solving nonlinear equations, especially in the local convergence analysis. However, the study on global convergence of quasi-Newton methods is relatively fewer, especially for the BFGS method. To ensure global convergence, some merit function such as the squared norm merit function is typically used. In this paper, we propose an algorithm for solving nonlinear monotone equations, which combines the BFGS method and the hyperplane projection method. We also prove that the proposed BFGS method converges globally if the equation is monotone and Lipschitz continuous without differentiability requirement on the equation, which makes it possible to solve some nonsmooth equations. An attractive property of the proposed method is that its global convergence is independent of any merit function.We also report some numerical results to show efficiency of the proposed method.

     

松弛型并行多分裂方法解非线性方程组的安全界

本文对某些非线性方程组F(x)=0,导出了一个算法,用它可以迭代建立F(x)=0的解的紧致上、下界。算法基于某些矩阵的多分裂,因此具有自然的并行性。我们证明了趋向于解的界之收敛原则,给出了参数的收敛性区域并考察了方法的收敛速度。     

Combined lp and quasi-Newton methods for minimax optimization

We present an algorithm for minimax optimization that combines LP methods and quasi-Newton methods. The quasi-Newton algorithm is used only if an irregular solution is detected, in which case second-order derivative information is needed in order to obtain a fast final rate of convergence. We prove that the algorithm can converge only to a stationary point and that normally the final rate of convergence will be either quadratic or superlinear. The performance is illustrated through some numerical examples.     

Adaptive constraint reduction for convex quadratic programming

We propose an adaptive, constraint-reduced, primal-dual interior-point algorithm for convex quadratic programming with many more inequality constraints than variables. We reduce the computational effort by assembling, instead of the exact normal-equation matrix, an approximate matrix from a well chosen index set which includes indices of constraints that seem to be most critical. Starting with a large portion of the constraints, our proposed scheme excludes more unnecessary constraints at later iterations. We provide proofs for the global convergence and the quadratic local convergence rate of an affine-scaling variant. Numerical experiments on random problems, on a data-fitting problem, and on a problem in array pattern synthesis show the effectiveness of the constraint reduction in decreasing the time per iteration without significantly affecting the number of iterations. We note that a similar constraint-reduction approach can be applied to algorithms of Mehrotra’s predictor-corrector type, although no convergence theory is supplied.     

各向异性外问题的Schwarz 交替法及其收敛性和误差估计

本文对于无界区域各向异性常系数椭圆型偏微分方程研究了一种基于自然边界归化的Schwarz交替法.利用极值原理证明了在连续情形最大模意义下的几何迭代收敛性,通过选取适当的共焦椭圆边界利用Fourier分析获得了不依赖各向异性程度的最优的迭代收缩因子,还在离散情形最大模意义下证明了几何收敛性,而且进一步得到了误差估计,最后,数值结果证实了迭代收缩因子和误差估计的正确性,表明了该方法在无界Ⅸ域上求解各向异性椭圆型偏微分方程的优越性.