A first-order interior-point method for linearly constrained smooth optimization

We propose a first-order interior-point method for linearly constrained smooth optimization that unifies and extends first-order affine-scaling method and replicator dynamics method for standard quadratic programming. Global convergence and, in the case of quadratic program, (sub)linear convergence rate and iterate convergence results are derived. Numerical experience on simplex constrained problems with 1000 variables is reported.     

On preconditioned Uzawa methods and SOR methods for saddle-point problems

This paper studies convergence analysis of a preconditioned inexact Uzawa method for nondifferentiable saddle-point problems. The SOR-Newton method and the SOR-BFGS method are special cases of this method. We relax the Bramble-Pasciak-Vassilev condition on preconditioners for convergence of the inexact Uzawa method for linear saddle-point problems. The relaxed condition is used to determine the relaxation parameters in the SOR-Newton method and the SOR-BFGS method. Furthermore, we study global convergence of the multistep inexact Uzawa method for nondifferentiable saddle-point problems.     

Optimal Rates of Linear Convergence of Relaxed Alternating Projections and Generalized Douglas-Rachford Methods for Two Subspaces

We systematically study the optimal linear convergence rates for several relaxed alternating projection methods and the generalized Douglas-Rachford splitting methods for finding the projection on the intersection of two subspaces. Our analysis is based on a study on the linear convergence rates of the powers of matrices. We show that the optimal linear convergence rate of powers of matrices is attained if and only if all subdominant eigenvalues of the matrix are semisimple. For the convenience of computation, a nonlinear approach to the partially relaxed alternating projection method with at least the same optimal convergence rate is also provided. Numerical experiments validate our convergence analysis     

A domain decomposition method based on the iterative operator splitting method

In this article a new approach is proposed for constructing a domain decomposition method based on the iterative operator splitting method. The convergence properties of such a method are studied. The main feature of the proposed idea is the decoupling of space and time. We present a multi-iterative operator splitting method that combines iteratively the space and time splitting. We confirm with numerical applications the effectiveness of the proposed iterative operator splitting method in comparison with the classical Schwarz waveform relaxation method as a standard method for domain decomposition. We provide improved results and convergence rates.     

On the convergence of two‐level Krylov methods for singular symmetric systems

We discuss the convergence of a two‐level version of the multilevel Krylov method for solving linear systems of equations with symmetric positive semidefinite matrix of coefficients. The analysis is based on the convergence result of Brown and Walker for the Generalized Minimal Residual method (GMRES), with the left‐ and right‐preconditioning implementation of the method. Numerical results based on diffusion problems are presented to show the convergence.     

Stable strong order 1.0 schemes for solving stochastic ordinary differential equations

The Balanced method was introduced as a class of quasi-implicit methods, based upon the Euler-Maruyama scheme, for solving stiff stochastic differential equations. We extend the Balanced method to introduce a class of stable strong order 1.0 numerical schemes for solving stochastic ordinary differential equations. We derive convergence results for this class of numerical schemes. We illustrate the asymptotic stability of this class of schemes is illustrated and is compared with contemporary schemes of strong order 1.0. We present some evidence on parametric selection with respect to minimising the error convergence terms. Furthermore we provide a convergence result for general Balanced style schemes of higher orders.     

A nonmonotone filter method for nonlinear optimization

We propose a new nonmonotone filter method to promote global and fast local convergence for sequential quadratic programming algorithms. Our method uses two filters: a standard, global g-filter for global convergence, and a local nonmonotone l-filter that allows us to establish fast local convergence. We show how to switch between the two filters efficiently, and we prove global and superlinear local convergence. A special feature of the proposed method is that it does not require second-order correction steps. We present preliminary numerical results comparing our implementation with a classical filter SQP method.     

Convergence of the Nelder-Mead method

We develop a matrix form of the Nelder-Mead simplex method and show that its convergence is related to the convergence of infinite matrix products. We then characterize the spectra of the involved matrices necessary for the study of convergence. Using these results, we discuss several examples of possible convergence or failure modes. Then, we prove a general convergence theorem for the simplex sequences generated by the method. The key assumption of the convergence theorem is proved in low-dimensional spaces up to 8 dimensions.

     

On a continuous method for solving nonlinear operator equations

We suggest a continuous method for solving nonlinear operator equations in Banach spaces. The proof of the convergence of the method is based on stability criteria for solutions of differential equations. The implementation of the method does not require the construction of inverse operators. Criteria for the global convergence are derived.     

Local convergence of quasi-Newton methods for B-differentiable equations

We study local convergence of quasi-Newton methods for solving systems of nonlinear equations defined by B-differentiable functions. We extend the classical linear and superlinear convergence results for general quasi-Newton methods as well as for Broyden's method. We also show how Broyden's method may be applied to nonlinear complementarity problems and illustrate its computational performance on two small examples.     

An interior Newton method for quadratic programming

We propose a new (interior) approach for the general quadratic programming problem. We establish that the new method has strong convergence properties: the generated sequence converges globally to a point satisfying the second-order necessary optimality conditions, and the rate of convergence is 2-step quadratic if the limit point is a strong local minimizer. Published alternative interior approaches do not share such strong convergence properties for the nonconvex case. We also report on the results of preliminary numerical experiments: the results indicate that the proposed method has considerable practical potential. Received October 11, 1993 / Revised version received February 20, 1996 Published online July 19, 1999     

变双障碍问题解的抽象稳定性

本文考虑了主部为非线性变双障碍问题解的抽象稳定性 (连续依赖性 ) .由于采用了弱收敛原理和文 [2 ]中取检验函数的技巧 ,我们的证明无需像 [1 ]那样应用Minty引理 .     

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.     

交错级数敛散性判别法

给出了交错级数的一个判别法,应用此判别法可直接判别交错级数是否收敛,以及收敛时是绝对收敛还是条件收敛.     

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.

     

Convergence analysis of waveform relaxation methods for neutral differential-functional systems

In this paper, the problems of convergence and superlinear convergence of continuous-time waveform relaxation method applied to Volterra type systems of neutral functional-differential equations are discussed. Under a Lipschitz condition with time- and delay-dependent right-hand side imposed on the so-called splitting function, more suitable conditions about convergence and superlinear convergence of continuous-time WR method are obtained. We also investigate the initial interval acceleration strategy for the practical implementation of the continuous-time waveform relaxation method, i.e., discrete-time waveform relaxation method. It is shown by numerical results that this strategy is efficacious and has the essential acceleration effect for the whole computation process.     

A Quasi-Newton Penalty Barrier Method for Convex Minimization Problems

We describe an infeasible interior point algorithm for convex minimization problems. The method uses quasi-Newton techniques for approximating the second derivatives and providing superlinear convergence. We propose a new feasibility control of the iterates by introducing shift variables and by penalizing them in the barrier problem. We prove global convergence under standard conditions on the problem data, without any assumption on the behavior of the algorithm.     

Piecewise linear least squares approximations of Frobenius-Perron operators

We propose a piecewise linear numerical method based on least squares approximations for computing stationary density functions of Frobenius-Perron operators associated with piecewise C² and stretching mappings of the unit interval. We prove the weak convergence of the method for a class of Frobenius-Perron operators, and the numerical results show that it is also norm convergent and has a better convergence rate than the piecewise linear Markov approximation method.     

Some observations on weighted GMRES

We investigate the convergence of the weighted GMRES method for solving linear systems. Two different weighting variants are compared with unweighted GMRES for three model problems, giving a phenomenological explanation of cases where weighting improves convergence, and a case where weighting has no effect on the convergence. We also present a new alternative implementation of the weighted Arnoldi algorithm which under known circumstances will be favourable in terms of computational complexity. These implementations of weighted GMRES are compared for a large number of examples. We find that weighted GMRES may outperform unweighted GMRES for some problems, but more often this method is not competitive with other Krylov subspace methods like GMRES with deflated restarting or BICGSTAB, in particular when a preconditioner is used.     

A new error bound result for Generalized Nash Equilibrium Problems and its algorithmic application

We present a new algorithm for the solution of Generalized Nash Equilibrium Problems. This hybrid method combines the robustness of a potential reduction algorithm and the local quadratic convergence rate of the LP-Newton method. We base our local convergence theory on a local error bound and provide a new sufficient condition for it to hold that is weaker than known ones. In particular, this condition implies neither local uniqueness of a solution nor strict complementarity. We also report promising numerical results.