Local and superlinear convergence of a primal-dual interior point method for nonlinear semidefinite programming

In this paper, we consider a primal-dual interior point method for solving nonlinear semidefinite programming problems. We propose primal-dual interior point methods based on the unscaled and scaled Newton methods, which correspond to the AHO, HRVW/KSH/M and NT search directions in linear SDP problems. We analyze local behavior of our proposed methods and show their local and superlinear convergence properties.     

QN THE CONVERGENCE ANALYSIS OF THE NONLINEAR ABS METHODS

In order to complete the convergence theory of nonlinear ABS algorithm, through a careful investigation to the algorithm structure, the author converts the nonlinear ABS algorithm into an inexact Newton method. Based on such equivalent variation, the Kantorovich type convergence of the ABS algorithm is established and the Convergence conditions of the algorithm that only depend on the initial conditions are obtained, which provides a useful basis for the choices of initial points of the ABS algorithm.     

A class of asynchronous multisplitting two-stage iterations for large sparse block systems of weakly nonlinear equations

For the block system of weakly nonlinear equations Ax=G(x), where is a large sparse block matrix and is a block nonlinear mapping having certain smoothness properties, we present a class of asynchronous parallel multisplitting block two-stage iteration methods in this paper. These methods are actually the block variants and generalizations of the asynchronous multisplitting two-stage iteration methods studied by Bai and Huang (Journal of Computational and Applied Mathematics 93(1) (1998) 13–33), and they can achieve high parallel efficiency of the multiprocessor system, especially, when there is load imbalance. Under quite general conditions that is a block H-matrix of different types and is a block P-bounded mapping, we establish convergence theories of these asynchronous multisplitting block two-stage iteration methods. Numerical computations show that these new methods are very efficient for solving the block system of weakly nonlinear equations in the asynchronous parallel computing environment.     

Superlinear convergence theorems for Newton-type methods for nonlinear systems of equations

In this paper, someQ-order convergence theorems are given for the problem of solving nonlinear systems of equations when using very general finitely terminating methods for the solution of the associated linear systems. The theorems differ from those of Dembo, Eisenstat, and Steihaug in the different stopping condition and in their applicability to the nonlinear ABS algorithm.Lecture presented at the University of Bergamo, Bergamo, Italy, October 1989.     

ABS methods and ABSPACK for linear systems and optimization: A review

ABS methods are a large class of methods, based upon the Egervary rank reducing algebraic process, first introduced in 1984 by Abaffy, Broyden and Spedicato for solving linear algebraic systems, and later extended to nonlinear algebraic equations, to optimization problems and other fields; software based upon ABS methods is now under development. Current ABS literature consists of about 400 papers. ABS methods provide a unification of several classes of classical algorithms and more efficient new solvers for a number of problems. In this paper we review ABS methods for linear systems and optimization, from both the point of view of theory and the numerical performance of ABSPACK.Work partially supported by ex MURST 60% 2001 funds.E. Spedicato     

求解特征值互补问题的一类ABS算法

ABS算法是20世纪80年代初,由Abaffy,Broyden和Spedicato完成的用于求解线性方程组的含有三个参量的投影算法,是一类有限次迭代直接法。目前,ABS算法不仅可以求解线性与非线性方程组,还可以求解线性规划和具有线性约束的非线性规划等问题。本文即是利用ABS算法求解特征值互补问题的一种尝试,构造了求解特征值互补问题的ABS算法,证明了求解特征值互补问题的ABS算法的收敛性。数值例子充分验证了求解特征值互补问题的ABS算法的有效性。     

Symmetric and Non-Symmetric ABS Methods for Solving Diophantine Systems of Equations

In the present paper we describe a new class of algorithms for solving Diophantine systems of equations in integer arithmetic. This algorithm, designated as the integer ABS (iABS) algorithm, is based on the ABS methods in the real space, with extensive modifications to ensure that all calculations remain in the integer space. Importantly, the iABS solves Diophantine systems of equations without determining the Hermite normal form. The algorithm is suitable for solving determined, over- or underdetermined, full rank or rank deficient linear integer equations. We also present a scaled integer ABS system and two special cases for solving general Diophantine systems of equations. In the scaled symmetric iABS (ssiABS), the Abaffian matrix H _i is symmetric, allowing that only half of its elements need to be calculated and stored. The scaled non-symmetric iABS system (snsiABS) provides more freedom in selecting the arbitrary parameters and thus the maximal values of H _i can be maintained at a certainly lower level. In addition to the above theoretical results, we also provide numerical experiments to test the performance of the ssiABS and the snsiABS algorithms. These experiments have confirmed the suitability of the iABS system for practical applications.     

Quasi-Newton ABS methods for solving nonlinear algebraic systems of equations

This paper is concerned with the solution of nonlinear algebraic systems of equations. For this problem, we suggest new methods, which are combinations of the nonlinear ABS methods and quasi-Newton methods. Extensive numerical experiments compare particular algorithms and show the efficiency of the proposed methods.The authors are grateful to Professors C. G. Broyden and E. Spedicato for many helpful discussions.     

Modified Iterative Runge-Kutta-Type Methods for Nonlinear Ill-Posed Problems

This work is devoted to the convergence analysis of a modified Runge-Kutta-type iterative regularization method for solving nonlinear ill-posed problems under a priori and a posteriori stopping rules. The convergence rate results of the proposed method can be obtained under a Hölder-type sourcewise condition if the Fréchet derivative is properly scaled and locally Lipschitz continuous. Numerical results are achieved by using the Levenberg-Marquardt, Lobatto, and Radau methods.     

Iterative methods for the solution of a singular control formulation of a GMWB pricing problem

Discretized singular control problems in finance result in highly nonlinear algebraic equations which must be solved at each timestep. We consider a singular stochastic control problem arising in pricing a guaranteed minimum withdrawal benefit (GMWB), where the underlying asset is assumed to follow a jump diffusion process. We use a scaled direct control formulation of the singular control problem and examine the conditions required to ensure that a fast fixed point policy iteration scheme converges. Our methods take advantage of the special structure of the GMWB problem in order to obtain a rapidly convergent iteration. The direct control method has a scaling parameter which must be set by the user. We give estimates for bounds on the scaling parameter so that convergence can be expected in the presence of round-off error. Example computations verify that these estimates are of the correct order. Finally, we compare the scaled direct control formulation to a formulation based on a block version of the penalty method (Huang and Forsyth in IMA J Numer Anal 32:320?C351, 2012). We show that the scaled direct control method has some advantages over the penalty method.     

A new derivative-free SCG-type projection method for nonlinear monotone equations with convex constraints

Based on a modified line search scheme, this paper presents a new derivative-free projection method for solving nonlinear monotone equations with convex constraints, which can be regarded as an extension of the scaled conjugate gradient method and the projection method. Under appropriate conditions, the global convergence and linear convergence rate of the proposed method is proven. Preliminary numerical results are also reported to show that this method is promising.     

Some non-interior path-following methods based on a scaled central path for linear complementarity problems

In this paper we present some non-interior path-following methods for linear complementarity problems. Instead of using the standard central path we use a scaled central path. Based on this new central path, we first give a feasible non-interior path-following method for linear complementarity problems. And then we extend it to an infeasible method. After proving the boundedness of the neighborhood, we prove the convergence of our method. Another point we should present is that we prove the local quadratic convergence of feasible method without the assumption of strict complementarity at the solution.     

An ABS algorithm for solving singular nonlinear systems with rank defects

A modified ABS algorithm for solving a class of singular nonlinear systems,F(x)=0,F∈R ⁿ, constructed by combining the discreted ABS algorithm and a method of Hoy and Schwetlick (1990), is presented. The second differential operation ofF at a point is not required to be calculated directly in this algorithm. Q-quadratic convergence of this algorithm is given.     

An ABS algorithm for solving singular nonlinear systems with rank one defect

A modified discretization ABS algorithm for solving a class of singular nonlinear systems, F(x) = 0, wherex, F ∈ Rⁿ, is presented, constructed by combining a discretization ABS algorithm and a method of Hoy and Schwetlick (1990). The second order differential operation ofF at a point is not required to be calculated directly in this algorithm. Q-quadratic convergence of this algorithm is given.     

A class of two‐stage iterative methods for systems of weakly nonlinear equations

The discretizations of many differential equations by the finite difference or the finite element methods can often result in a class of system of weakly nonlinear equations. In this paper, by applying the two-tage iteration technique and in accordance with the special properties of this weakly nonlinear system, we first propose a general two-tage iterative method through the two-tage splitting of the system matrix. Then, by applying the accelerated overrelaxation (AOR) technique of the linear iterative methods, we present a two-tage AOR method, which particularly uses the AOR iteration as the inner iteration and is substantially a relaxed variant of the afore-presented method. For these two classes of methods, we establish their local convergence theories, and precisely estimate their asymptotic convergence factors under some suitable assumptions when the involved nonlinear mapping is only B-differentiable. When the system matrix is either a monotone matrix or an H-matrix, and the nonlinear mapping is a P-bounded mapping, we thoroughly set up the global convergence theories of these new methods. Moreover, under the assumptions that the system matrix is monotone and the nonlinear mapping is isotone, we discuss the monotone convergence properties of the new two-tage iteration methods, and investigate the influence of the matrix splittings as well as the relaxation parameters on the convergence behaviours of these methods. Numerical computations show that our new methods are feasible and efficient for solving the system of weakly nonlinear equations. This revised version was published online in June 2006 with corrections to the Cover Date.     

On the convergence of a Jacobi-type algorithm for singly linearly-constrained problems subject to simple bounds

In this work we define a block decomposition Jacobi-type method for nonlinear optimization problems with one linear constraint and bound constraints on the variables. We prove convergence of the method to stationary points of the problem under quite general assumptions.     

A class of adaptive Dai–Liao conjugate gradient methods based on the scaled memoryless BFGS update

Minimizing the distance between search direction matrix of the Dai–Liao method and the scaled memoryless BFGS update in the Frobenius norm, and using Powell’s nonnegative restriction of the conjugate gradient parameters, a one-parameter class of nonlinear conjugate gradient methods is proposed. Then, a brief global convergence analysis is made with and without convexity assumption on the objective function. Preliminary numerical results are reported; they demonstrate a proper choice for the parameter of the proposed class of conjugate gradient methods may lead to promising numerical performance.     

Asynchronous multisplitting two-stage iterations for systems of weakly nonlinear equations

For the large sparse systems of weakly nonlinear equations arising in the discretizations of many classical differential and integral equations, this paper presents a class of asynchronous parallel multisplitting two-stage iteration methods for getting their solutions by the high-speed multiprocessor systems. Under suitable assumptions, we study the global convergence properties of these asynchronous multisplitting two-stage iteration methods. Moreover, for this class of new methods, we establish their local convergence theories, and precisely estimate their asymptotic convergence factors under some reasonable assumptions when the involved nonlinear mapping is only assumed to be directionally differentiable. Numerical computations show that our new methods are feasible and efficient for parallely solving the system of weakly nonlinear equations.     

Solving systems of nonlinear equations by means of an accelerated successive orthogonal projections method

In this paper we introduce an acceleration procedure for a block version of the generalization of Kaczmarz's method for nonlinear systems of equations. We prove a local linear convergence theorem. Some numerical experiments are presented, which show that the new method improves the nonlinear Kaczmarz's method without acceleration.     

Parallel multisplitting two-stage iterative methods for large sparse systems of weakly nonlinear equations

The finite difference or the finite element discretizations of many differential or integral equations often result in a class of systems of weakly nonlinear equations. In this paper, by reasonably applying both the multisplitting and the two-stage iteration techniques, and in accordance with the special properties of this system of weakly nonlinear equations, we first propose a general multisplitting two-stage iteration method through the two-stage multiple splittings of the system matrix. Then, by applying the accelerated overrelaxation (AOR) technique of the linear iterative methods, we present a multisplitting two-stage AOR method, which particularly uses the AOR-like iteration as inner iteration and is substantially a relaxed variant of the afore-presented method. These two methods have a forceful parallel computing function and are much more suitable to the high-speed multiprocessor systems. For these two classes of methods, we establish their local convergence theories, and precisely estimate their asymptotic convergence factors under some suitable assumptions when the involved nonlinear mapping is only directionally differentiable. When the system matrix is either an H-matrix or a monotone matrix, and the nonlinear mapping is a P-bounded mapping, we thoroughly set up the global convergence theories of these new methods. Moreover, under the assumptions that the system matrix is monotone and the nonlinear mapping is isotone, we discuss the monotone convergence properties of the new multisplitting two-stage iteration methods, and investigate the influence of the multiple splittings as well as the relaxation parameters upon the convergence behaviours of these methods. Numerical computations show that our new methods are feasible and efficient for parallel solving of the system of weakly nonlinear equations. This revised version was published online in August 2006 with corrections to the Cover Date.