Convergence of the multilevel Full Approximation Scheme including theV-cycle

Summary The multilevel Full Approximation Scheme (FAS ML) is a well-known solver for nonlinear boundary value problems. In this paper we prove local quantitative convergence statements for a class of FAS ML algorithms in a general Hilbertspace setting. This setting clearly exhibits the structure of FAS ML. We prove local convergence of a nested iteration for a rather concrete class of FAS ML algorithms in whichV-cycles and only one Jacobilike pre- and post-smoothing on each level are used.     

Convergence of linear multistep and one-leg methods for stiff nonlinear initial value problems

To prove convergence of numerical methods for stiff initial value problems, stability is needed but also estimates for the local errors which are not affected by stiffness. In this paper global error bounds are derived for one-leg and linear multistep methods applied to classes of arbitrarily stiff, nonlinear initial value problems. It will be shown that under suitable stability assumptions the multistep methods are convergent for stiff problems with the same order of convergence as for nonstiff problems, provided that the stepsize variation is sufficiently regular.     

Linearity-preserving flux correction and convergence acceleration for constrained Galerkin schemes

This paper is concerned with the development of general-purpose algebraic flux correction schemes for continuous (linear and multilinear) finite elements. In order to enforce the discrete maximum principle (DMP), we modify the standard Galerkin discretization of a scalar transport equation by adding diffusive and antidiffusive fluxes. The result is a nonlinear algebraic system satisfying the DMP constraint. An estimate based on variational gradient recovery leads to a linearity-preserving limiter for the difference between the function values at two neighboring nodes. A fully multidimensional version of this scheme is obtained by taking the sum of local bounds and constraining the total flux. This new approach to algebraic flux correction provides a unified treatment of stationary and time-dependent problems. Moreover, the same algorithm is used to limit convective fluxes, anisotropic diffusion operators, and the antidiffusive part of the consistent mass matrix.The nonlinear algebraic system associated with the constrained Galerkin scheme is solved using fixed-point defect correction or a nonlinear SSOR method. A dramatic improvement of nonlinear convergence rates is achieved with the technique known as Anderson acceleration (or Anderson mixing). It blends a number of last iterates in a GMRES fashion, which results in a Broyden-like quasi-Newton update. The numerical behavior of the proposed algorithms is illustrated by a grid convergence study for convection-dominated transport problems and anisotropic diffusion equations in 2D.     

A general class of penalty/barrier path-following Newton methods for nonlinear programming

In the present article rather general penalty/barrier-methods (e.g. logarithmic barriers, SUMT, exponential penalties), which define a local continuously differentiable primal and dual path, are analyzed in case of strict local minima of nonlinear problems with inequality as well as equality constraints. In particular, the radius of convergence of Newton's method depending on the penalty/barrier-parameter is estimated. Unlike using self-concordance properties, the convergence bounds are derived by direct estimations of the solutions of the Newton equations. By means of the obtained results parameter selection rules are studied which guarantee the local convergence of the considered penalty/barrier-techniques with only a finite number of Newton steps at each parameter level. Numerical examples illustrate the practical behavior of the proposed class of methods.     

TIME-EXTRAPOLATION ALGORITHM （TEA） FOR LINEAR PARABOLIC PROBLEMS

The fast solutions of Crank-Nicolson scheme on quasi-uniform mesh for parabolic prob- lems are discussed. First, to decrease regularity requirements of solutions, some new error estimates are proved. Second, we analyze the two characteristics of parabolic discrete scheme, and find that the efficiency of Multigrid Method （MG） is greatly reduced. Nu- merical experiments compare the efficiency of Direct Conjugate Gradient Method （DCG） and Extrapolation Cascadic Multigrid Method （EXCMG）. Last, we propose a Time- Extrapolation Algorithm （TEA）, which takes a linear combination of previous several level solutions as good initial values to accelerate the rate of convergence. Some typical extrapolation formulas are compared numerically. And we find that under certain accuracy requirement, the CG iteration count for the 3-order and 7-level extrapolation formula is about 1/3 of that of DCG＇s. Since the TEA algorithm is independent of the space dimension, it is still valid for quasi-uniform meshes. As only the finest grid is needed, the proposed method is regarded very effective for nonlinear parabolic problems.     

A Theoretical and Numerical Comparison of Some Semismooth Algorithms for Complementarity Problems

In this paper we introduce a general line search scheme which easily allows us to define and analyze known and new semismooth algorithms for the solution of nonlinear complementarity problems. We enucleate the basic assumptions that a search direction to be used in the general scheme has to enjoy in order to guarantee global convergence, local superlinear/quadratic convergence or finite convergence. We examine in detail several different semismooth algorithms and compare their theoretical features and their practical behavior on a set of large-scale problems.     

CONSERVATION OF THREE—POINT COMPACT SCHEMES ON SINGLE AND MULTIBLOCK PATCHED GRIDS FOR HYPERBOLIC PROBLEMS

For nonlinear hyperbloic problems,Conservation of the numerical scheme is important for convergence to the correct weak solutions.In this paper the the conservation of the well-known compact scheme up to fourth order of accuracy on a single and uniform grid is studied,and a conservative interface treatment is derived for compact schemes on patched grids .For a pure initial value problem,the compact scheme is shown to be equivalent to a scheme in the usual conservative form .For the case of a mixed initial boundary value problem,the compact scheme is conservative only if the rounding errors are small enough.For a pactched grid interface,a conservative interface condition useful for mesh fefiement and for parallel computation is derived and its order of local accuracy is analyzed.     

Convergence of an implicit Voronoi finite volume method for reaction–diffusion problems

We investigate the convergence of an implicit Voronoi finite volume method for reaction–diffusion problems including nonlinear diffusion in two space dimensions. The model allows to handle heterogeneous materials and uses the chemical activities of the involved species as primary variables. The numerical scheme works with boundary conforming Delaunay meshes and preserves positivity and the dissipative property of the continuous system. Starting from a result on the global stability of the scheme (uniform, mesh‐independent global upper, and lower bounds), we prove strong convergence of the chemical activities and their gradients to a weak solution of the continuous problem. To illustrate the preservation of qualitative properties by the numerical scheme, we present a long‐term simulation of the Michaelis–Menten–Henri system. Especially, we investigate the decay properties of the relative free energy over several magnitudes of time, and obtain experimental orders of convergence for this quantity. © 2015 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 32: 141–174, 2016     

A Regularized Iterative Scheme for Solving Nonlinear Ill-Posed Problems

In this article, we consider a regularized iterative scheme for solving nonlinear ill-posed problems. The convergence analysis and error estimates are derived by choosing the regularization parameter according to both a priori and a posteriori methods. The iterative scheme is stopped using an a posteriori stopping rule, and we prove that the scheme converges to the solution of the well-known Lavrentiev scheme. The salient features of the proposed scheme are: (i) convergence and error estimate analysis require only weaker assumptions compared to standard assumptions followed in literature, and (ii) consideration of an adaptive a posteriori stopping rule and a parameter choice strategy that gives the same convergence rate as that of an a priori method without using the smallness assumption, the source condition. The above features are very useful from theory and application points of view. We also supply the numerical results to illustrate that the method is adaptable. Further, we compare the numerical result of the proposed method with the standard approach to demonstrate that our scheme is stable and achieves good computational output.     

A convergence analysis and applications for the Newton-Kantorovich method in K-normed spaces

We study the local and semilocal convergence of the Newton-Kantorovich method to a solution of a nonlinear operator equation on aK-normed space setting. Using more precise majorizing sequences than before we show that in the semilocal case finer error bounds can be determined on the distances involved and an at least as precise information on the location of the solution as in earlier results. In the local case we show that a larger radius of convergence can be obtained.     

Convergence and Application of a Decomposition Method Using Duality Bounds for Nonconvex Global Optimization

The subject of this article is a class of global optimization problems, in which the variables can be divided into two groups such that, in each group, the functions involved have the same structure (e.g. linear, convex or concave, etc.). Based on the decomposition idea of Benders (Ref. 1), a corresponding master problem is defined on the space of one of the two groups of variables. The objective function of this master problem is in fact the optimal value function of a nonlinear parametric optimization problem. To solve the resulting master problem, a branch-and-bound scheme is proposed, in which the estimation of the lower bounds is performed by applying the well-known weak duality theorem in Lagrange duality. The results of this article concentrate on two subjects: investigating the convergence of the general algorithm and solving dual problems of some special classes of nonconvex optimization problems. Based on results in sensitivity and stability theory and in parametric optimization, conditions for the convergence are established by investigating the so-called dual properness property and the upper semicontinuity of the objective function of the master problem. The general algorithm is then discussed in detail for some nonconvex problems including concave minimization problems with a special structure, general quadratic problems, optimization problems on the efficient set, and linear multiplicative programming problems.     

A globally convergent trust region algorithm for optimization with general constraints and simple bounds

1.IntroductionInthispaper,weconsiderthefollowingnonlinearprogr~ngproblemwherec(x)=(c,(x),c2(2),',We(.))',i(x)andci(x)(i=1,2,',m)arerealfunctions*ThisworkissupPOrtedbytheNationalNaturalScienceFOundationofChinaandtheManagement,DecisionandinformationSystemLab,theChineseAcademyofSciences.definedinD={xEReIISx5u}.Weassumethath相似文献   

A global extrapolated procedure for the boussinesq equation

In this paper we use the global extrapolation procedure to study the Boussinesq equation in one dimension. The application of a parametric finite-difference method leads to a three-time level nonlinear scheme, which is analyzed for local truncation error, stability and convergence. Then, the nonlinear term of the equation is properly linearized so, that the scheme becomes linear. The results of a number of numerical experiments for the single-soliton wave are given.     

A linear programming-based optimization algorithm for solving nonlinear programming problems

In this paper a linear programming-based optimization algorithm called the Sequential Cutting Plane algorithm is presented. The main features of the algorithm are described, convergence to a Karush–Kuhn–Tucker stationary point is proved and numerical experience on some well-known test sets is showed. The algorithm is based on an earlier version for convex inequality constrained problems, but here the algorithm is extended to general continuously differentiable nonlinear programming problems containing both nonlinear inequality and equality constraints. A comparison with some existing solvers shows that the algorithm is competitive with these solvers. Thus, this new method based on solving linear programming subproblems is a good alternative method for solving nonlinear programming problems efficiently. The algorithm has been used as a subsolver in a mixed integer nonlinear programming algorithm where the linear problems provide lower bounds on the optimal solutions of the nonlinear programming subproblems in the branch and bound tree for convex, inequality constrained problems.     

An Improved Linearity-Preserving Cell-Centered Scheme for Nonlinear Diffusion Problems on General Meshes

In this paper, we suggest a new vertex interpolation algorithm to improve an existing cell-centered finite volume scheme for nonlinear diffusion problems on general meshes. The new vertex interpolation algorithm is derived by applying a special limit procedure to the well-known MPFA-O method. Since the MPFA-O method for 3D cases has been addressed in some studies, the new vertex interpolation algorithm can be extended to 3D cases naturally. More interesting is that the solvability of the corresponding local system is proved under some assumptions. Additionally, we modify the edge flux approximation by an edge-based discretization of diffusion coefficient, and thus the improved scheme is free of the so-called numerical heat-barrier issue suffered by many existing cell-centered or hybrid schemes. The final scheme allows arbitrary continuous or discontinuous diffusion coefficients and can be applicable to arbitrary star-shaped polygonal meshes. A second-order convergence rate for the approximate solution and a first-order accuracy for the flux are observed in numerical experiments. In the comparative experiments with some existing vertex interpolation algorithms, the new algorithm shows obvious improvement on highly distorted meshes.     

Nonlinear semidefinite programming: sensitivity, convergence, and an application in passive reduced-order modeling

We consider the solution of nonlinear programs with nonlinear semidefiniteness constraints. The need for an efficient exploitation of the cone of positive semidefinite matrices makes the solution of such nonlinear semidefinite programs more complicated than the solution of standard nonlinear programs. This paper studies a sequential semidefinite programming (SSP) method, which is a generalization of the well-known sequential quadratic programming method for standard nonlinear programs. We present a sensitivity result for nonlinear semidefinite programs, and then based on this result, we give a self-contained proof of local quadratic convergence of the SSP method. We also describe a class of nonlinear semidefinite programs that arise in passive reduced-order modeling, and we report results of some numerical experiments with the SSP method applied to problems in that class.     

A Globally Convergent Trust-Region Method for Large-Scale Symmetric Nonlinear Systems

This study presents a novel adaptive trust-region method for solving symmetric nonlinear systems of equations. The new method uses a derivative-free quasi-Newton formula in place of the exact Jacobian. The global convergence and local quadratic convergence of the new method are established without the nondegeneracy assumption of the exact Jacobian. Using the compact limited memory BFGS, we adapt a version of the new method for solving large-scale problems and develop the dogleg scheme for solving the associated trust-region subproblems. The sufficient decrease condition for the adapted dogleg scheme is established. While the efficiency of the present trust-region approach can be improved by using adaptive radius techniques, utilizing the compact limited memory BFGS adjusts this approach to handle large-scale symmetric nonlinear systems of equations. Preliminary numerical results for both medium- and large-scale problems are reported.     

An algorithm for a class of nonlinear complementarity problems with non-Lipschitzian functions

In this paper, we focus on solving a class of nonlinear complementarity problems with non-Lipschitzian functions. We first introduce a generalized class of smoothing functions for the plus function. By combining it with Robinson's normal equation, we reformulate the complementarity problem as a family of parameterized smoothing equations. Then, a smoothing Newton method combined with a new nonmonotone line search scheme is employed to compute a solution of the smoothing equations. The global and local superlinear convergence of the proposed method is proved under mild assumptions. Preliminary numerical results obtained applying the proposed approach to nonlinear complementarity problems arising in free boundary problems are reported. They show that the smoothing function and the nonmonotone line search scheme proposed in this paper are effective.     

Nonlinear Subdivision Schemes on Irregular Meshes

The present article deals with convergence and smoothness analysis of geometric, nonlinear subdivision schemes in the presence of extraordinary points. We discuss when the existence of a proximity condition between a linear scheme and its nonlinear analogue implies convergence of the nonlinear scheme (for dense enough input data). Furthermore, we obtain C ¹ smoothness of the nonlinear limit function in the vicinity of an extraordinary point over Reif’s characteristic parametrization. The results apply to the geometric analogues of well-known subdivision schemes such as Doo–Sabin or Catmull–Clark schemes.     

Error bounds for 2-regular mappings with Lipschitzian derivatives and their applications

We obtain local estimates of the distance to a set defined by equality constraints under assumptions which are weaker than those previously used in the literature. Specifically, we assume that the constraints mapping has a Lipschitzian derivative, and satisfies a certain 2-regularity condition at the point under consideration. This setting directly subsumes the classical regular case and the twice differentiable 2-regular case, for which error bounds are known, but it is significantly richer than either of these two cases. When applied to a certain equation-based reformulation of the nonlinear complementarity problem, our results yield an error bound under an assumption more general than b-regularity. The latter appears to be the weakest assumption under which a local error bound for complementarity problems was previously available. We also discuss an application of our results to the convergence rate analysis of the exterior penalty method for solving irregular problems. Received: February 2000 / Accepted: November 2000?Published online January 17, 2001