Schwarz methods for inequalities with contraction operators

We prove the convergence of some multiplicative and additive Schwarz methods for inequalities which contain contraction operators. The problem is stated in a reflexive Banach space and it generalizes the well-known fixed-point problem in the Hilbert spaces. Error estimation theorems are given for three multiplicative algorithms and two additive algorithms. We show that these algorithms are in fact Schwarz methods if the subspaces are associated with a decomposition of the domain. Also, for the one- and two-level methods in the finite element spaces, we write the convergence rates as functions of the overlapping and mesh parameters. They are similar with the convergence rates of these methods for linear problems. Besides the direct use of the five algorithms for the inequalities with contraction operators, we can use the above results to obtain the convergence rate of the Schwarz method for other types of inequalities or nonlinear equations. In this way, we prove the convergence and estimate the error of the one- and two-level Schwarz methods for some inequalities in Hilbert spaces which are not of the variational type, and also, for the Navier–Stokes problem. Finally, we give conditions of existence and uniqueness of the solution for all problems we consider. We point out that these conditions and the convergence conditions of the proposed algorithms are of the same type.     

Dynamical Systems and Adaptive Timestepping in ODE Solvers

Initial value problems for ODEs are often solved numerically using adaptive timestepping algorithms. These algorithms are controlled by a user-defined tolerance which bounds from above the estimated error committed at each step. We formulate a large class of such algorithms as discrete dynamical systems which are discontinuous and of higher dimension than the underlying ODE. By assuming sufficiently strong finite-time convergence results on some neighbourhood of an attractor of the ODE we prove existence and upper semicontinuity results for a nearby numerical attractor as the tolerance tends to zero.This assumption of sufficiently strong finite-time convergence results is then examined for adaptive algorithms that use a pair of explicit Runge-Kutta methods of different order to estimate the one-step error. For arbitrary Runge-Kutta pairs the necessary finite-time convergence results fail to hold on a set of points in the phase space that includes all the equilibria of the ODE. Therefore, in general, the asymptotic convergence results cannot be applied to attractors containing equilibria. However, for a particular class of Runge-Kutta pairs, the finite-time convergence results can be strengthened to include neighbourhoods of equilibrium points for which the Jacobian is invertible.     

On the Orderings and Groupings of Conditional Maximizations within ECM-Type Algorithms

Abstract

The ECM and ECME algorithms are generalizations of the EM algorithm in which the maximization (M) step is replaced by several conditional maximization (CM) steps. The order that the CM-steps are performed is trivial to change and generally affects how fast the algorithm converges. Moreover, the same order of CM-steps need not be used at each iteration and in some applications it is feasible to group two or more CM-steps into one larger CM-step. These issues also arise when implementing the Gibbs sampler, and in this article we study them in the context of fitting log-linear and random-effects models with ECM-type algorithms. We find that some standard theoretical measures of the rate of convergence can be of little use in comparing the computational time required, and that common strategies such as using a random ordering may not provide the desired effects. We also develop two algorithms for fitting random-effects models to illustrate that with careful selection of CM-steps, ECM-type algorithms can be substantially faster than the standard EM algorithm.     

Local convergence analysis of several inexact Newton-type algorithms for general nonlinear eigenvalue problems

We study the local convergence of several inexact numerical algorithms closely related to Newton’s method for the solution of a simple eigenpair of the general nonlinear eigenvalue problem $T(\lambda )v=0$ . We investigate inverse iteration, Rayleigh quotient iteration, residual inverse iteration, and the single-vector Jacobi–Davidson method, analyzing the impact of the tolerances chosen for the approximate solution of the linear systems arising in these algorithms on the order of the local convergence rates. We show that the inexact algorithms can achieve the same order of convergence as the exact methods if appropriate sequences of tolerances are applied to the inner solves. We discuss the connections and emphasize the differences between the standard inexact Newton’s method and these inexact algorithms. When the local symmetry of $T(\lambda )$ is present, the use of a nonlinear Rayleigh functional is shown to be fundamental in achieving higher order of convergence rates. The convergence results are illustrated by numerical experiments.     

一簇非线性等式约束优化问题的过滤线搜索修正正割方法

本文提供了一簇新的过滤线搜索修正正割方法求解非线性等式约束优化问题.新算法簇的特点是:用修正正割算法簇中的一个算法获得搜索方向,回代线搜索技术得到步长,过滤准则用来决定是否接受步长,引入二阶校正技术减少不可行性并克服Maratos效应.在合理的假设条件下,分析了算法的总体收敛性.并证明了,通过附加二阶校正步,算法簇克服了Maratos效应,并二步Q-超线性收敛到满足二阶充分最优条件的局部解.数值结果表明了所提供的算法具有有效性.     

Choosing a stepsize for Taylor series methods for solving ODE'S

Problem-dependent upper and lower bounds are given for the stepsize taken by long Taylor series methods for solving initial value problems in ordinary differential equations. Taylor series methods recursively generate the terms of the Taylor series and estimate the radius of convergence as well as the order and location of the primary singularities. A stepsize must then be chosen which is as large as possible to minimize the required number of steps, while remaining small enough to maintain the truncation error less than some tolerance.One could use any of four different measures of trunction error in an attempt to control the global error : i) absolute truncation error per step, ii) absolute trunction error per unit step, iii) relative truncation error per step, and iv) relative truncation error per unit step. For each of these measures, we give bounds for error and for the stepsize which yields a prescribed error. The bounds depend on the series length, radius of convergence, order, and location of the primary singularities. The bounds are shown to be optimal for functions with only one singularity of any order on the circle of convergence.     

Third order convergent time discretization for parabolic optimal control problems with control constraints

We consider a priori error analysis for a discretization of a linear quadratic parabolic optimal control problem with box constraints on the time-dependent control variable. For such problems one can show that a time-discrete solution with second order convergence can be obtained by a first order discontinuous Galerkin time discretization for the state variable and either the variational discretization approach or a post-processing strategy for the control variable. Here, by combining the two approaches for the control variable, we demonstrate that almost third order convergence with respect to the size of the time steps can be achieved.     

Multistep approximation algorithms: Improved convergence rates through postconditioning with smoothing kernels

We show how certain widely used multistep approximation algorithms can be interpreted as instances of an approximate Newton method. It was shown in an earlier paper by the second author that the convergence rates of approximate Newton methods (in the context of the numerical solution of PDEs) suffer from a “loss of derivatives”, and that the subsequent linear rate of convergence can be improved to be superlinear using an adaptation of Nash–Moser iteration for numerical analysis purposes; the essence of the adaptation being a splitting of the inversion and the smoothing into two separate steps. We show how these ideas apply to scattered data approximation as well as the numerical solution of partial differential equations. We investigate the use of several radial kernels for the smoothing operation. In our numerical examples we use radial basis functions also in the inversion step. This revised version was published online in June 2006 with corrections to the Cover Date.     

Infinite-Dimensional Integration in Weighted Hilbert Spaces: Anchored Decompositions,Optimal Deterministic Algorithms,and Higher-Order Convergence

We study the numerical integration of functions depending on an infinite number of variables. We provide lower error bounds for general deterministic algorithms and provide matching upper error bounds with the help of suitable multilevel algorithms and changing-dimension algorithms. More precisely, the spaces of integrands we consider are weighted, reproducing kernel Hilbert spaces with norms induced by an underlying anchored function space decomposition. Here the weights model the relative importance of different groups of variables. The error criterion used is the deterministic worst-case error. We study two cost models for function evaluations that depend on the number of active variables of the chosen sample points, and we study two classes of weights, namely product and order-dependent weights and the newly introduced finite projective dimension weights. We show for these classes of weights that multilevel algorithms achieve the optimal rate of convergence in the first cost model while changing-dimension algorithms achieve the optimal convergence rate in the second model. As an illustrative example, we discuss the anchored Sobolev space with smoothness parameter \(\alpha \) and provide new optimal quasi-Monte Carlo multilevel algorithms and quasi-Monte Carlo changing-dimension algorithms based on higher-order polynomial lattice rules.     

Adaptive weak approximation of stochastic differential equations

Adaptive time‐stepping methods based on the Monte Carlo Euler method for weak approximation of Itô stochastic differential equations are developed. The main result is new expansions of the computational error, with computable leading‐order term in a posteriori form, based on stochastic flows and discrete dual backward problems. The expansions lead to efficient and accurate computation of error estimates. Adaptive algorithms for either stochastic time steps or deterministic time steps are described. Numerical examples illustrate when stochastic and deterministic adaptive time steps are superior to constant time steps and when adaptive stochastic steps are superior to adaptive deterministic steps. Stochastic time steps use Brownian bridges and require more work for a given number of time steps. Deterministic time steps may yield more time steps but require less work; for example, in the limit of vanishing error tolerance, the ratio of the computational error and its computable estimate tends to 1 with negligible additional work to determine the adaptive deterministic time steps. © 2001 John Wiley & Sons, Inc.     

Inexact Perturbed Newton Methods and Applications to a Class of Krylov Solvers

Inexact Newton methods are variant of the Newton method in which each step satisfies only approximately the linear system (Ref. 1). The local convergence theory given by the authors of Ref. 1 and most of the results based on it consider the error terms as being provided only by the fact that the linear systems are not solved exactly. The few existing results for the general case (when some perturbed linear systems are considered, which in turn are not solved exactly) do not offer explicit formulas in terms of the perturbations and residuals. We extend this local convergence theory to the general case, characterizing the rate of convergence in terms of the perturbations and residuals.The Newton iterations are then analyzed when, at each step, an approximate solution of the linear system is determined by the following Krylov solvers based on backward error minimization properties: GMRES, GMBACK, MINPERT. We obtain results concerning the following topics: monotone properties of the errors in these Newton–Krylov iterates when the initial guess is taken 0 in the Krylov algorithms; control of the convergence orders of the Newton–Krylov iterations by the magnitude of the backward errors of the approximate steps; similarities of the asymptotical behavior of GMRES and MINPERT when used in a converging Newton method. At the end of the paper, the theoretical results are verified on some numerical examples.     

Iterative Algorithms for Equilibrium Problems

We consider equilibrium problems in the framework of the formulation proposed by Blum and Oettli, which includes variational inequalities, Nash equilibria in noncooperative games, and vector optimization problems, for instance, as particular cases. We show that such problems are particular instances of convex feasibility problems with infinitely many convex sets, but with additional structure, so that projection algorithms for convex feasibility can be modified in order to improve their convergence properties, mainly achieving global convergence without either compactness or coercivity assumptions. We present a sequential projections algorithm with an approximately most violated constraint control strategy, and two variants where exact orthogonal projections are replaced by approximate ones, using separating hyperplanes generated by subgradients. We include full convergence analysis of these algorithms.     

Euclidean algorithms are Gaussian

We obtain a central limit theorem for a general class of additive parameters (costs, observables) associated to three standard Euclidean algorithms, with optimal speed of convergence. We also provide very precise asymptotic estimates and error terms for the mean and variance of such parameters. For costs that are lattice (including the number of steps), we go further and establish a local limit theorem, with optimal speed of convergence. We view an algorithm as a dynamical system restricted to rational inputs, and combine tools imported from dynamics, such as transfer operators, with various other techniques: Dirichlet series, Perron's formula, quasi-powers theorems, and the saddle-point method. Such dynamical analyses had previously been used to perform the average-case analysis of algorithms. For the present (dynamical) analysis in distribution, we require estimates on transfer operators when a parameter varies along vertical lines in the complex plane. To prove them, we adapt techniques introduced recently by Dolgopyat in the context of continuous-time dynamics (Ann. Math. 147 (1998) 357).     

Greedy-Type Approximation in Banach Spaces and Applications

We continue to study the efficiency of approximation and convergence of greedy-type algorithms in uniformly smooth Banach spaces. Two greedy-type approximation methods, the Weak Chebyshev Greedy Algorithm (WCGA) and the Weak Relaxed Greedy Algorithm (WRGA), have been introduced and studied in [24]. These methods (WCGA and WRGA) are very general approximation methods that work well in an arbitrary uniformly smooth Banach space $X$ for any dictionary ${\Cal D}$. It turns out that these general approximation methods are also very good for specific dictionaries. It has been observed in [7] that the WCGA and WRGA provide constructive methods in $m$-term trigonometric approximation in $L_p$, $p\in[2,\infty)$, which realize an optimal rate of $m$-term approximation for different function classes. In [25] the WCGA and WRGA have been used in constructing deterministic cubature formulas for a wide variety of function classes with error estimates similar to those for the Monte Carlo Method. The WCGA and WRGA can be considered as a constructive deterministic alternative to (or substitute for) some powerful probabilistic methods. This observation encourages us to continue a thorough study of the WCGA and WRGA. In this paper we study modifications of the WCGA and WRGA that are motivated by numerical applications. In these modifications we are able to perform steps of the WCGA (or WRGA) approximately with some controlled errors. We prove that the modified versions of the {\it WCGA and WRGA perform as well as the WCGA and WRGA}. We give two applications of greedy-type algorithms. First, we use them to provide a constructive proof of optimal estimates for best $m$-term trigonometric approximation in the uniform norm. Second, we use them to construct deterministic sets of points $\{\xi^1,\ldots,\xi^m\} \subset [0,1]^d$ with the $L_p$ discrepancy less than $Cp^{1/2}m^{-1/2}$, $C$ is an effective absolute constant.     

Lower Bounds for the Rate of Convergence of Dynamic Reconstruction Algorithms for Distributed-Parameter Systems

We obtain lower bounds for the rate of convergence of reconstruction algorithms for distributed-parameter systems of parabolic type. In the case of a pointwise constraint on control for known reconstruction algorithms, we establish a lower bound on the rate of convergence, which shows that, given certain conditions, for each solution of the system one can choose such a collection of measurements so that the reconstruction error will not be less than a certain value. In the case of unbounded controls, we obtain lower bounds for a possible reconstruction error for each trajectory as well as for a given set of trajectories. For a system of special form, we construct an algorithm for which we obtain upper and lower bounds for accuracy having identical order for a specific choice of matching of the parameters.     

Improved local analysis for a certain class of iterative methods with cubic convergence

We use Lipschitz and center-Lipschitz conditions to provide an improved local convergence analysis for a certain class of iterative methods with cubic order of convergence. It turns out that under the same computational cost as before, we obtain a larger radius of convergence and tighter error bounds. Numerical examples are also provided in this study.     

Global and local convergence of a class of penalty-free-type methods for nonlinear programming

We present a class of trust region algorithms without using a penalty function or a filter for nonlinear inequality constrained optimization and analyze their global and local convergence. In each iteration, the algorithms reduce the value of objective function or the measure of constraints violation according to the relationship between optimality and feasibility. A sequence of steps focused on improving optimality is referred to as an f-loop, while some restoration phase focuses on improving feasibility and is called an h-loop. In an f-loop, the algorithms compute trial step by solving a classic QP subproblem rather than using composite-step strategy. Global convergence is ensured by requiring the constraints violation of each iteration not to exceed an progressively tighter bound on constraints violation. By using a second order correction strategy based on active set identification technique, Marato’s effect is avoided and fast local convergence is shown. The preliminary numerical results are encouraging.     

Uniformly Convergent Multigrid Methods for Convection–Diffusion Problems without Any Constraint on Coarse Grids

We construct a class of multigrid methods for convection–diffusion problems. The proposed algorithms use first order stable monotone schemes to precondition the second order standard Galerkin finite element discretization. To speed up the solution process of the lower order schemes, cross-wind-block reordering of the unknowns is applied. A V-cycle iteration, based on these algorithms, is then used as a preconditioner in GMRES. The numerical examples show that this method is convergent without imposing any constraint on the coarsest grid and the convergence of the preconditioned method is uniform.     

Improving the accuracy of BDF methods for index 3 differential-algebraic equations

Methods for solving index 3 DAEs based on BDFs suffer a loss of accuracy when there is a change of step size or a change of order of the method. A layer of nonuniform convergence is observed in these cases, andO(1) errors may appear in the algebraic variables. From the viewpoint of error control, it is beneficial to allow smooth changes of step size, and since most codes based on BDFs are of variable order, it is also of interest to avoid the inaccuracies caused by a change of order of the method. In the case of BDFs applied to index 3 DAEs in semi-explicit form, we present algorithms that correct toO(h) the inaccurate approximations to the algebraic variables when there are changes of step size in the backward Euler method. These algorithms can be included in an existing code at a very small cost. We have also described how to obtain formulas that correct theO(1) errors in the algebraic variables appearing after a change of order.This author thanks the Centro de Estadística y Software Matemático de la Universidad Simón Bolívar (CESMa) for permitting her free use of its research facilities.     

Beyond Canonical DC-Optimization: The Single Reverse Polar Problem

We propose a novel generalization of the Canonical Difference of Convex problem (CDC), and we study the convergence of outer approximation algorithms for its solution, which use an approximated oracle for checking the global optimality conditions. Although the approximated optimality conditions are similar to those of CDC, this new class of problems is shown to significantly differ from its special case. Indeed, outer approximation approaches for CDC need be substantially modified in order to cope with the more general problem, bringing to new algorithms. We develop a hierarchy of conditions that guarantee global convergence, and we build three different cutting plane algorithms relying on them.