A predictor-corrector smoothing Newton method for symmetric cone complementarity problems

In this paper, we present a predictor-corrector smoothing Newton method for solving nonlinear symmetric cone complementarity problems (SCCP) based on the symmetrically perturbed smoothing function. Under a mild assumption, the solution set of the problem concerned is just nonempty, we show that the proposed algorithm is globally and locally quadratic convergent. Also, the algorithm finds a maximally complementary solution to the SCCP. Numerical results for second order cone complementarity problems (SOCCP), a special case of SCCP, show that the proposed algorithm is effective.     

Local and superlinear convergence of quasi-Newton methods based on modified secant conditions

For solving unconstrained minimization problems, quasi-Newton methods are popular iterative methods. The secant condition which employs only the gradient information is imposed on these methods. Several researchers paid attention to other secant conditions to get a better approximation of the Hessian matrix of the objective function. Recently, Zhang et al. [New quasi-Newton equation and related methods for unconstrained optimization, J. Optim. Theory Appl. 102 (1999) 147–167] and Zhang and Xu [Properties and numerical performance of quasi-Newton methods with modified quasi-Newton equations, J. Comput. Appl. Math. 137 (2001) 269–278] proposed the modified secant condition which uses both gradient and function value information in order to get a higher order accuracy in approximating the second curvature of the objective function. They showed the local and q-superlinear convergence property of the BFGS-like and DFP-like updates based on their proposed secant condition. In this paper, we incorporate one parameter into this secant condition to smoothly switch the standard secant condition and the secant condition of Zhang et al. We consider a modified Broyden family which includes the BFGS-like and the DFP-like updates proposed by Zhang et al. We prove the local and q-superlinear convergence of our method.     

Finite termination of a Newton-type algorithm for a class of affine variational inequality problems

Many optimization problems can be reformulated as a system of equations. One may use the generalized Newton method or the smoothing Newton method to solve the reformulated equations so that a solution of the original problem can be found. Such methods have been powerful tools to solve many optimization problems in the literature. In this paper, we propose a Newton-type algorithm for solving a class of monotone affine variational inequality problems (AVIPs for short). In the proposed algorithm, the techniques based on both the generalized Newton method and the smoothing Newton method are used. In particular, we show that the algorithm can find an exact solution of the AVIP in a finite number of iterations under an assumption that the solution set of the AVIP is nonempty. Preliminary numerical results are reported.     

A globally convergent derivative-free method for solving large-scale nonlinear monotone equations

In this paper, we propose two derivative-free iterative methods for solving nonlinear monotone equations, which combines two modified HS methods with the projection method in Solodov and Svaiter (1998) [5]. The proposed methods can be applied to solve nonsmooth equations. They are suitable to large-scale equations due to their lower storage requirement. Under mild conditions, we show that the proposed methods are globally convergent. The reported numerical results show that the methods are efficient.     

A proximal gradient descent method for the extended second-order cone linear complementarity problem

We consider an extended second-order cone linear complementarity problem (SOCLCP), including the generalized SOCLCP, the horizontal SOCLCP, the vertical SOCLCP, and the mixed SOCLCP as special cases. In this paper, we present some simple second-order cone constrained and unconstrained reformulation problems, and under mild conditions prove the equivalence between the stationary points of these optimization problems and the solutions of the extended SOCLCP. Particularly, we develop a proximal gradient descent method for solving the second-order cone constrained problems. This method is very simple and at each iteration makes only one Euclidean projection onto second-order cones. We establish global convergence and, under a local Lipschitzian error bound assumption, linear rate of convergence. Numerical comparisons are made with the limited-memory BFGS method for the unconstrained reformulations, which verify the effectiveness of the proposed method.     

On diagonally structured problems in unconstrained optimization using an inexact super Halley method

We consider solving the unconstrained minimization problem using an iterative method derived from the third order super Halley method. Each iteration of the super Halley method requires the solution of two linear systems of equations. We show a practical implementation using an iterative method to solve the linear systems. This paper introduces an array of arrays (jagged) data structure for storing the second and third derivative of a multivariate function and suitable termination criteria for the (inner) iterative method to achieve a cubic rate of convergence. Using a jagged compressed diagonal storage of the Hessian matrices and for the tensor, numerical results show that storing the diagonals are more efficient than the row or column oriented approach when we use an iterative method for solving the linear systems of equations.     

The solution set structure of monotone linear complementarity problems over second-order cone

The second-order cone linear complementarity problem (SOCLCP) is a generalization of the linear complementarity problem (LCP). In this paper we characterize the solution set of a monotone SOCLCP with the help of the Jordan-algebraic technique.     

Solvability of Newton equations in smoothing-type algorithms for the SOCCP

In this paper, we first investigate the invertibility of a class of matrices. Based on the obtained results, we then discuss the solvability of Newton equations appearing in the smoothing-type algorithm for solving the second-order cone complementarity problem (SOCCP). A condition ensuring the solvability of such a system of Newton equations is given. In addition, our results also show that the assumption that the Jacobian matrix of the function involved in the SOCCP is a P₀-matrix is not enough for ensuring the solvability of such a system of Newton equations, which is different from the one of smoothing-type algorithms for solving many traditional optimization problems in ℜⁿ.     

A simple feasible SQP method for inequality constrained optimization with global and superlinear convergence

In this paper, a simple feasible SQP method for nonlinear inequality constrained optimization is presented. At each iteration, we need to solve one QP subproblem only. After solving a system of linear equations, a new feasible descent direction is designed. The Maratos effect is avoided by using a high-order corrected direction. Under some suitable conditions the global and superlinear convergence can be induced. In the end, numerical experiments show that the method in this paper is effective.     

A superlinearly convergent strongly sub-feasible SSLE-type algorithm with working set for nonlinearly constrained optimization

In this paper, by means of a new efficient identification technique of active constraints and the method of strongly sub-feasible direction, we propose a new sequential system of linear equations (SSLE) algorithm for solving inequality constrained optimization problems, in which the initial point is arbitrary. At each iteration, we first yield the working set by a pivoting operation and a generalized projection; then, three or four reduced linear equations with a same coefficient are solved to obtain the search direction. After a finite number of iterations, the algorithm can produced a feasible iteration point, and it becomes the method of feasible directions. Moreover, after finitely many iterations, the working set becomes independent of the iterates and is essentially the same as the active set of the KKT point. Under some mild conditions, the proposed algorithm is proved to be globally, strongly and superlinearly convergent. Finally, some preliminary numerical experiments are reported to show that the algorithm is practicable and effective.     

Adomian’s decomposition method and homotopy perturbation method in solving nonlinear equations

The Adomian’s decomposition method and the homotopy perturbation method are two powerful methods which consider the approximate solution of a nonlinear equation as an infinite series usually converging to the accurate solution. By theoretical analysis of the two methods, we show, in the present paper, that the two methods are equivalent in solving nonlinear equations.     

A smoothing Newton-type method for generalized nonlinear complementarity problem

By using a new type of smoothing function, we first reformulate the generalized nonlinear complementarity problem over a polyhedral cone as a smoothing system of equations, and then develop a smoothing Newton-type method for solving it. For the proposed method, we obtain its global convergence under milder conditions, and we further establish its local superlinear (quadratic) convergence rate under the BD-regular assumption. Preliminary numerical experiments are also reported in this paper.     

On the similarity of some three-point methods for solving nonlinear equations

In this short note we discuss certain similarities between some three-point methods for solving nonlinear equations. In particular, we show that the recent three-point method published in [R. Thukral, A new eighth-order iterative method for solving nonlinear equations, Appl. Math. Comput. 217 (2010) 222-229] is a special case of the family of three-point methods proposed previously in [R. Thukral, M.S. Petkovi?, Family of three-point methods of optimal order for solving nonlinear equations, J. Comput. Appl. Math. 233 (2010) 2278-2284].     

Explicit One-Step P-Stable Methods for Second Order Periodic Initial Value Problems

In this paper, we present an explicit one-step method for solving periodic initial value problems of second order ordinary differential equations. The method is P-stable, and of first algebraic order and high phase-lag order. To improve the algebraic order, we give a composition second order scheme with the proposed method and its adjoint. We report some numerical results to illustrate the efficiency of our methods.     

A branch and bound algorithm for globally solving a class of nonconvex programming problems

A branch and bound algorithm is proposed for globally solving a class of nonconvex programming problems (NP). For minimizing the problem, linear lower bounding functions (LLBFs) of objective function and constraint functions are constructed, then a relaxation linear programming is obtained which is solved by the simplex method and which provides the lower bound of the optimal value. The proposed algorithm is convergent to the global minimum through the successive refinement of linear relaxation of the feasible region and the solutions of a series of linear programming problems. And finally the numerical experiment is reported to show the feasibility and effectiveness of the proposed algorithm.     

A family of derivative-free conjugate gradient methods for large-scale nonlinear systems of equations

In this paper, we propose a family of derivative-free conjugate gradient methods for large-scale nonlinear systems of equations. They come from two modified conjugate gradient methods [W.Y. Cheng, A two term PRP based descent Method, Numer. Funct. Anal. Optim. 28 (2007) 1217–1230; L. Zhang, W.J. Zhou, D.H. Li, A descent modified Polak–Ribiére–Polyak conjugate gradient method and its global convergence, IMA J. Numer. Anal. 26 (2006) 629–640] recently proposed for unconstrained optimization problems. Under appropriate conditions, the global convergence of the proposed method is established. Preliminary numerical results show that the proposed method is promising.     

A new smoothing Newton method for solving constrained nonlinear equations

In this paper, a new smoothing Newton method is proposed for solving constrained nonlinear equations. We first transform the constrained nonlinear equations to a system of semismooth equations by using the so-called absolute value function of the slack variables, and then present a new smoothing Newton method for solving the semismooth equations by constructing a new smoothing approximation function. This new method is globally and quadratically convergent. It needs to solve only one system of unconstrained equations and to perform one line search at each iteration. Numerical results show that the new algorithm works quite well.     

Two CSCS-based iteration methods for solving absolute value equations

Recently, two families of HSS-based iteration methods are constructed for solving the system of absolute value equations (AVEs), which is a class of non-differentiable NP-hard problems. In this study, we establish the Picard-CSCS iteration method and the nonlinear CSCS-like iteration method for AVEs involving the Toeplitz matrix. Then, we analyze the convergence of the Picard-CSCS iteration method for solving AVEs. By using the theory about nonsmooth analysis, we particularly prove the convergence of the nonlinear CSCS-like iteration solver for AVEs. The advantage of these methods is that they do not require the storage of coefficient matrices at all, and the sub-system of linear equations can be solved efficiently via the fast Fourier transforms (FFTs). Therefore, computational cost and storage can be saved in practical implementations. Numerical examples including numerical solutions of nonlinear fractional diffusion equations are reported to show the effectiveness of the proposed methods in comparison with some existing methods.     

BFGS trust-region method for symmetric nonlinear equations

In this paper, we propose a BFGS trust-region method for solving symmetric nonlinear equations. The global convergence and the superlinear convergence of the presented method will be established under favorable conditions. Numerical results show that the new algorithm is effective.     

A reproducing kernel method for solving nonlocal fractional boundary value problems

In our previous works, we proposed a reproducing kernel method for solving singular and nonsingular boundary value problems of integer order based on the reproducing kernel theory. In this letter, we shall expand the application of reproducing kernel theory to fractional differential equations and present an algorithm for solving nonlocal fractional boundary value problems. The results from numerical examples show that the present method is simple and effective.