Spectral residual method without gradient information for solving large-scale nonlinear systems of equations

A fully derivative-free spectral residual method for solving large-scale nonlinear systems of equations is presented. It uses in a systematic way the residual vector as a search direction, a spectral steplength that produces a nonmonotone process and a globalization strategy that allows for this nonmonotone behavior. The global convergence analysis of the combined scheme is presented. An extensive set of numerical experiments that indicate that the new combination is competitive and frequently better than well-known Newton-Krylov methods for large-scale problems is also presented.

     

A spectral algorithm for large-scale systems of nonlinear monotone equations

A derivative-free iterative scheme that uses the residual vector as search direction for solving large-scale systems of nonlinear monotone equations is presented. It is closely related to two recently proposed spectral residual methods for nonlinear systems which use a nonmonotone line-search globalization strategy and a step-size based on the Barzilai-Borwein choice. The global convergence analysis is presented. In order to study the numerical behavior of the algorithm, it is included an extensive series of numerical experiments. Our computational experiments show that the new algorithm is computationally efficient.     

A nonmonotone Jacobian smoothing inexact Newton method for NCP

In this paper we propose Jacobian smoothing inexact Newton method for nonlinear complementarity problems (NCP) with derivative-free nonmonotone line search. This nonmonotone line search technique ensures globalization and is a combination of Grippo-Lampariello-Lucidi (GLL) and Li-Fukushima (LF) strategies, with the aim to take into account their advantages. The method is based on very well known Fischer-Burmeister reformulation of NCP and its smoothing Kanzow’s approximation. The mixed Newton equation, which combines the semismooth function with the Jacobian of its smooth operator, is solved approximately in every iteration, so the method belongs to the class of Jacobian smoothing inexact Newton methods. The inexact search direction is not in general a descent direction and this is the reason why nonmonotone scheme is used for globalization. Global convergence and local superlinear convergence of method are proved. Numerical performances are also analyzed and point out that high level of nonmonotonicity of this line search rule enables robust and efficient method.     

A derivative-free nonmonotone line-search technique for unconstrained optimization

A tolerant derivative–free nonmonotone line-search technique is proposed and analyzed. Several consecutive increases in the objective function and also nondescent directions are admitted for unconstrained minimization. To exemplify the power of this new line search we describe a direct search algorithm in which the directions are chosen randomly. The convergence properties of this random method rely exclusively on the line-search technique. We present numerical experiments, to illustrate the advantages of using a derivative-free nonmonotone globalization strategy, with approximated-gradient type methods and also with the inverse SR1 update that could produce nondescent directions. In all cases we use a local variation finite differences approximation to the gradient.     

Nonmonotone Globalization Techniques for the Barzilai-Borwein Gradient Method

In this paper we propose new globalization strategies for the Barzilai and Borwein gradient method, based on suitable relaxations of the monotonicity requirements. In particular, we define a class of algorithms that combine nonmonotone watchdog techniques with nonmonotone linesearch rules and we prove the global convergence of these schemes. Then we perform an extensive computational study, which shows the effectiveness of the proposed approach in the solution of large dimensional unconstrained optimization problems.     

Nonmonotone smoothing Broyden-like method for generalized nonlinear complementarity problems

Based on a new symmetrically perturbed smoothing function, the generalized nonlinear complementarity problem defined on a polyhedral cone is reformulated as a system of smoothing equations. Then we suggest a new nonmonotone derivative-free line search and combine it into the smoothing Broyden-like method. The proposed algorithm contains the usual monotone line search as a special case and can overcome the difficult of smoothing Newton methods in solving the smooth equations to some extent. Under mild conditions, we prove that the proposed algorithm has global and local superlinear convergence. Furthermore, the algorithm is locally quadratically convergent under suitable assumptions. Preliminary numerical results are also reported.     

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.     

Monotone and nonmonotone trust-region-based algorithms for large scale unconstrained optimization problems

Two trust regions algorithms for unconstrained nonlinear optimization problems are presented: a monotone and a nonmonotone one. Both of them solve the trust region subproblem by the spectral projected gradient (SPG) method proposed by Birgin, Martínez and Raydan (in SIAM J. Optim. 10(4):1196?C1211, 2000). SPG is a nonmonotone projected gradient algorithm for solving large-scale convex-constrained optimization problems. It combines the classical projected gradient method with the spectral gradient choice of steplength and a nonmonotone line search strategy. The simplicity (only requires matrix-vector products, and one projection per iteration) and rapid convergence of this scheme fits nicely with globalization techniques based on the trust region philosophy, for large-scale problems. In the nonmonotone algorithm the trial step is evaluated by acceptance via a rule which can be considered a generalization of the well known fraction of Cauchy decrease condition and a generalization of the nonmonotone line search proposed by Grippo, Lampariello and Lucidi (in SIAM J. Numer. Anal. 23:707?C716, 1986). Convergence properties and extensive numerical results are presented. Our results establish the robustness and efficiency of the new algorithms.     

Nonmonotone stabilization methods for nonlinear equations

We are concerned with defining new globalization criteria for solution methods of nonlinear equations. The current criteria used in these methods require a sufficient decrease of a particular merit function at each iteration of the algorithm. As was observed in the field of smooth unconstrained optimization, this descent requirement can considerably slow the rate of convergence of the sequence of points produced and, in some cases, can heavily deteriorate the performance of algorithms. The aim of this paper is to show that the global convergence of most methods proposed in the literature for solving systems of nonlinear equations can be obtained using less restrictive criteria that do not enforce a monotonic decrease of the chosen merit function. In particular, we show that a general stabilization scheme, recently proposed for the unconstrained minimization of continuously differentiable functions, can be extended to methods for the solution of nonlinear (nonsmooth) equations. This scheme includes different kinds of relaxation of the descent requirement and opens up the possibility of describing new classes of algorithms where the old monotone linesearch techniques are replace with more flexible nonmonotone stabilization procedures. As in the case of smooth unconstrained optimization, this should be the basis for defining more efficient algorithms with very good practical rates of convergence.This material is partially based on research supported by the Air Force Office of Scientific Research Grant AFOSR-89-0410, National Science Foundation Grant CCR-91-57632, and Istituto di Analisi dei Sistemi ed Informatica del CNR.     

Weak order stochastic Runge–Kutta methods for commutative stochastic differential equations

A new explicit stochastic Runge–Kutta scheme of weak order 2 is proposed under a commutativity condition, which is derivative-free and which attains order 4 for ordinary differential equations. The weak order conditions are derived by utilizing multi-colored rooted tree analysis and a solution is found in a transparent way. The scheme is compared with other derivative-free and weak second order schemes in numerical experiments.     

Smoothing inexact Newton methods for NCP with various nonmonotone techniques

Various iterative methods for solving nonlinear complementarity problems (NCP) are developed in recent years. In this paper we propose Jacobian smoothing inexact Newton methods for NCP with different nonmonotone strategies. The methods are based on semismooth equation reformulation of NCP by Fischer-Burmeister function. Nonmonotone line-search techniques are used for globalization procedure. Numerical performance of algorithms are compared. (© 2013 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Quasi-Newton methods for constrained nonlinear systems: complexity analysis and applications

We address the solution of constrained nonlinear systems by new linesearch quasi-Newton methods. These methods are based on a proper use of the projection map onto the convex constraint set and on a derivative-free and nonmonotone linesearch strategy. The convergence properties of the proposed methods are presented along with a worst-case iteration complexity bound. Several implementations of the proposed scheme are discussed and validated on bound-constrained problems including gas distribution network models. The results reported show that the new methods are very efficient and competitive with an existing affine-scaling procedure.     

A nonmonotone smoothing Newton method for circular cone programming

The circular cone programming (CCP) problem is to minimize or maximize a linear function over the intersection of an affine space with the Cartesian product of circular cones. In this paper, we study nondegeneracy and strict complementarity for the CCP, and present a nonmonotone smoothing Newton method for solving the CCP. We reformulate the CCP as a second-order cone programming (SOCP) problem using the algebraic relation between the circular cone and the second-order cone. Then based on a one parametric class of smoothing functions for the SOCP, a smoothing Newton method is developed for the CCP by adopting a new nonmonotone line search scheme. Without restrictions regarding its starting point, our algorithm solves one linear system of equations approximately and performs one line search at each iteration. Under mild assumptions, our algorithm is shown to possess global and local quadratic convergence properties. Some preliminary numerical results illustrate that our nonmonotone smoothing Newton method is promising for solving the CCP.     

A nonmonotone derivative-free algorithm for nonlinear complementarity problems based on the new generalized penalized Fischer–Burmeister merit function

In this paper, we propose a new generalized penalized Fischer–Burmeister merit function, and show that the function possesses a system of favorite properties. Moreover, for the merit function, we establish the boundedness of level set under a weaker condition. We also propose a derivative-free algorithm for nonlinear complementarity problems with a nonmonotone line search. More specifically, we show that the proposed algorithm is globally convergent and has a locally linear convergence rate. Numerical comparisons are also made with the merit function used by Chen (J Comput Appl Math 232:455–471, 2009), which confirm the superior behaviour of the new merit function.     

Weak second-order stochastic Runge–Kutta methods for non-commutative stochastic differential equations

A new explicit stochastic Runge–Kutta scheme of weak order 2 is proposed for non-commutative stochastic differential equations (SDEs), which is derivative-free and which attains order 4 for ordinary differential equations. The scheme is directly applicable to Stratonovich SDEs and uses 2m-1$2m-1$ random variables for one step in the m-dimensional Wiener process case. It is compared with other derivative-free and weak second-order schemes in numerical experiments.     

Nonmonotone filter DQMM method for the system of nonlinear equations

In this paper, we propose a nonmonotone filter Diagonalized Quasi-Newton Multiplier (DQMM) method for solving system of nonlinear equations. The system of nonlinear equations is transformed into a constrained nonlinear programming problem which is then solved by nonmonotone filter DQMM method. A nonmonotone criterion is used to speed up the convergence progress in some ill-conditioned cases. Under reasonable conditions, we give the global convergence properties. The numerical experiments are reported to show the effectiveness of the proposed algorithm.     

A BFGS trust-region method with a new nonmonotone technique for nonlinear equations

In this paper, we consider a trust-region method for solving nonlinear equations which employs a new nonmonotone technique. A strong nonmonotone strategy and a weaker nonmonotone strategy can be obtained by choosing the parameter adaptively. Thus, the disadvantages of the traditional nonmonotone strategy can be avoided. It does not need to compute the Jacobian matrix at every iteration, so that the workload and time are decreased. Theoretical analysis indicates that the new algorithm preserves the global convergence under classical assumptions. Moreover, superlinear and quadratic convergence are established under suitable conditions. Numerical experiments show the efficiency and effectiveness of the proposed method for solving nonlinear equations.     

Nonmonotone projected gradient methods based on barrier and Euclidean distances

We consider nonmonotone projected gradient methods based on non-Euclidean distances, which play the role of barrier for a given constraint set. Our basic scheme uses the resulting projection-like maps that produces interior trajectories, and combines it with the recent nonmonotone line search technique originally proposed for unconstrained problems by Zhang and Hager. The combination of these two ideas leads to produce a nonmonotone scheme for constrained nonconvex problems, which is proven to converge to a stationary point. Some variants of this algorithm that incorporate spectral steplength are also studied and compared with classical nonmonotone schemes based on the usual Euclidean projection. To validate our approach, we report on numerical results solving bound constrained problems from the CUTEr library collection.     

A modified nonmonotone BFGS algorithm for solving smooth nonlinear equations

In this paper, a modified nonmonotone BFGS algorithm is developed for solving a smooth system of nonlinear equations. Different from the existent techniques of nonmonotone line search, the value of an algorithmic parameter controlling the magnitude of nonmonotonicity is updated at each iteration by the known information of the system of nonlinear equations such that the numerical performance of the developed algorithm is improved. Under some suitable assumptions, the global convergence of the algorithm is established for solving a generic nonlinear system of equations. Implementing the algorithm to solve some benchmark test problems, the obtained numerical results demonstrate that it is more effective than some similar algorithms available in the literature.