求解非线性互补问题的一类光滑Broyden-like方法

非线性互补问题可以等价地转换为光滑方程组来求解. 基于一种新的非单调线搜索准则, 提出了求解非线性互补问题等价光滑方程组的一类新的非单调光滑 Broyden-like 算法.在适当的假设条件下, 证明了该算法的全局收敛性与局部超线性收敛性. 数值实验表明所提出的算法是有效的.     

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 smoothing Newton method for NCPs with the P0-property

In this paper, we first investigate a two-parametric class of smoothing functions which contains the penalized smoothing Fischer-Burmeister function and the penalized smoothing CHKS function as special cases. Then we present a smoothing Newton method for the nonlinear complementarity problem based on the class of smoothing functions. Issues such as line search rule, boundedness of the level set, global and quadratic convergence are studied. In particular, we give a line search rule containing the common used Armijo-type line search rule as a special case. Also without requiring strict complementarity assumption at the P₀-NCP solution or the nonemptyness and boundedness of the solution set, the proposed algorithm is proved to be globally convergent. Preliminary numerical results show the efficiency of the algorithm and provide efficient domains of the two parameters for the complementarity problems.     

A new hybrid method for nonlinear complementarity problems

In this paper, a new hybrid method is proposed for solving nonlinear complementarity problems (NCP) with P ₀ function. In the new method, we combine a smoothing nonmonotone trust region method based on a conic model and line search techniques. We reformulate the NCP as a system of semismooth equations using the Fischer-Burmeister function. Using Kanzow’s smooth approximation function to construct the smooth operator, we propose a smoothing nonmonotone trust region algorithm of a conic model for solving the NCP with P ₀ functions. This is different from the classical trust region methods, in that when a trial step is not accepted, the method does not resolve the trust region subproblem but generates an iterative point whose steplength is defined by a line search. We prove that every accumulation point of the sequence generated by the algorithm is a solution of the NCP. Under a nonsingularity condition, the superlinear convergence of the algorithm is established without a strict complementarity condition.     

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 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 smoothing-type algorithm for the second-order cone complementarity problem with a new nonmonotone line search

The second-order cone complementarity problem (denoted by SOCCP) can be effectively solved by smoothing-type algorithms, which in general are designed based on some monotone line search. In this paper, based on a new smoothing function of the Fischer–Burmeister function, we propose a smoothing-type algorithm for solving the SOCCP. The proposed algorithm uses a new nonmonotone line search scheme, which contains the usual monotone line search as a special case. Under suitable assumptions, we show that the proposed algorithm is globally and locally quadratically convergent. Some numerical results are reported which indicate the effectiveness of the proposed algorithm.     

A one-parametric class of smoothing functions and an improved regularization Newton method for the NCP

In this paper, we introduce a one-parametric class of smoothing functions, which enjoys some favourable properties and includes two famous smoothing functions as special cases. Based on this class of smoothing functions, we propose a regularization Newton method for solving the non-linear complementarity problem. The main feature of the proposed method is that it uses a perturbed Newton equation to obtain the direction. This not only allows our method to have global and local quadratic convergences without strict complementarity conditions, but also makes the regularization parameter converge to zero globally Q-linearly. In addition, we use a new non-monotone line search scheme to obtain the step size. Some numerical results are reported which confirm the good theoretical properties of the proposed method.     

Barzilai–Borwein method with variable sample size for stochastic linear complementarity problems

A smoothing method for solving stochastic linear complementarity problems is proposed. The expected residual minimization reformulation of the problem is considered, and it is approximated by the sample average approximation (SAA). The proposed method is based on sequential solving of a sequence of smoothing problems where each of the smoothing problems is defined with its own sample average approximation. A nonmonotone line search with a variant of the Barzilai–Borwein (BB) gradient direction is used for solving each of the smoothing problems. The BB search direction is efficient and low cost, particularly suitable for nonmonotone line search procedure. The variable sample size scheme allows the sample size to vary across the iterations and the method tends to use smaller sample size far away from the solution. The key point of this strategy is a good balance between the variable sample size strategy, the smoothing sequence and nonmonotonicity. Eventually, the maximal sample size is used and the SAA problem is solved. Presented numerical results indicate that the proposed strategy reduces the overall computational cost.     

A family of new smoothing functions and?a?nonmonotone smoothing Newton method for?the?nonlinear complementarity problems

In this paper, based on a p-norm with p being any fixed real number in the interval (1,+??), we introduce a family of new smoothing functions, which include the smoothing symmetric perturbed Fischer function as a special case. We also show that the functions have several favorable properties. Based on the new smoothing functions, we propose a nonmonotone smoothing Newton algorithm for solving nonlinear complementarity problems. The proposed algorithm only need to solve one linear system of equations. We show that the proposed algorithm is globally and locally superlinearly convergent under suitable assumptions. Numerical experiments indicate that the method associated with a smaller p, for example p=1.1, usually has better numerical performance than the smoothing symmetric perturbed Fischer function, which exactly corresponds to p=2.     

Globally Convergent Broyden-Like Methods for Semismooth Equations and Applications to VIP, NCP and MCP

In this paper, we propose a general smoothing Broyden-like quasi-Newton method for solving a class of nonsmooth equations. Under appropriate conditions, the proposed method converges to a solution of the equation globally and superlinearly. In particular, the proposed method provides the possibility of developing a quasi-Newton method that enjoys superlinear convergence even if strict complementarity fails to hold. We pay particular attention to semismooth equations arising from nonlinear complementarity problems, mixed complementarity problems and variational inequality problems. We show that under certain conditions, the related methods based on the perturbed Fischer–Burmeister function, Chen–Harker–Kanzow–Smale smoothing function and the Gabriel–Moré class of smoothing functions converge globally and superlinearly.     

Improved smoothing Newton methods for symmetric cone complementarity problems

There recently has been much interest in smoothing Newton method for solving nonlinear complementarity problems. We extend such method to symmetric cone complementarity problems (SCCP). In this paper, we first investigate a one-parametric class of smoothing functions in the context of symmetric cones, which contains the Fischer–Burmeister smoothing function and the CHKS smoothing function as special cases. Then we propose a smoothing Newton method for the SCCP based on the one-parametric class of smoothing functions. For the proposed method, besides the classical step length, we provide a new step length and the global convergence is obtained. Finally, preliminary numerical results are reported, which show the effectiveness of the two step lengthes in the algorithm and provide efficient domains of the parameter for the complementarity problems.     

Continuation method for nonlinear complementarity problems via normal maps

In a recent paper by Chen and Mangasarian (C. Chen, O.L. Mangasarian, A class of smoothing functions for nonlinear and mixed complementarity problems, Computational Optimization and Applications 2 (1996), 97–138) a class of parametric smoothing functions has been proposed to approximate the plus function present in many optimization and complementarity related problems. This paper uses these smoothing functions to approximate the normal map formulation of nonlinear complementarity problems (NCP). Properties of the smoothing function are investigated based on the density functions that defines the smooth approximations. A continuation method is then proposed to solve the NCPs arising from the approximations. Sufficient conditions are provided to guarantee the boundedness of the solution trajectory. Furthermore, the structure of the subproblems arising in the proposed continuation method is analyzed for different choices of smoothing functions. Computational results of the continuation method are reported.     

A new class of smoothing complementarity functions over symmetric cones

A popular approach to solving the complementarity problem is to reformulate it as an equivalent system of smooth equations via a smoothing complementarity function. In this paper, first we propose a new class of smoothing complementarity functions, which contains the natural residual smoothing function and the Fischer–Burmeister smoothing function for symmetric cone complementarity problems. Then we give some unified formulae of the Fréchet derivatives associated with Jordan product. Finally, the derivative of the new proposed class of smoothing complementarity functions is deduced over symmetric cones.     

Smoothing Newton algorithm for the second-order cone programming with a nonmonotone line search

The smoothing-type algorithms, which are in general designed based on some monotone line search, have been successfully applied to solve the second-order cone programming (denoted by SOCP). In this paper, we propose a nonmonotone smoothing Newton algorithm for solving the SOCP. Under suitable assumptions, we show that the proposed algorithm is globally and locally quadratically convergent. To compare with the existing smoothing-type algorithms for the SOCP, our algorithm has the following special properties: (i) it is based on a new smoothing function of the vector-valued natural residual function; (ii) it uses a nonmonotone line search scheme which contains the usual monotone line search as a special case. Preliminary numerical results demonstrate that the smoothing-type algorithm using the nonmonotone line search is promising for solving the SOCP.     

A new smoothing and regularization Newton method for the symmetric cone complementarity problem

Based on a regularized Chen–Harker–Kanzow–Smale (CHKS) smoothing function, we propose a new smoothing and regularization Newton method for solving the symmetric cone complementarity problem. By using the theory of Euclidean Jordan algebras, we establish the global and local quadratic convergence of the method on certain assumptions. The proposed method uses a nonmonotone line search technique which includes the usual monotone line search as a special case. In addition, our method treats both the smoothing parameter \(\mu \) and the regularization parameter \(\varepsilon \) as independent variables. Preliminary numerical results are reported which indicate that the proposed method is effective.     

Nonmonotone derivative-free methods for nonlinear equations

In this paper we study nonmonotone globalization techniques, in connection with iterative derivative-free methods for solving a system of nonlinear equations in several variables. First we define and analyze a class of nonmonotone derivative-free linesearch techniques for unconstrained minimization of differentiable functions. Then we introduce a globalization scheme, which combines nonmonotone watchdog rules and nonmonotone linesearches, and we study the application of this scheme to some recent extensions of the Barzilai–Borwein gradient method and to hybrid stabilization algorithms employing linesearches along coordinate directions. Numerical results on a set of standard test problems show that the proposed techniques can be of value in the solution of large-dimensional systems of equations.     

On convergence of a smoothing Broyden-like method for P0-NCP

A smoothing Broyden-like method is proposed for solving nonlinear complementarity problem in this paper. The algorithm considered here is based on the smooth approximation Fischer–Burmeister function and makes use of the line search rule of Li and Fukushima [A derivative-free line search and global convergence of Broyden-like method for nonlinear equations, Optim. Methods Software 13(3) (2000) 181–201]. Under suitable conditions, the iterates generated by the proposed method converge to a solution of the nonlinear complementarity problem globally and superlinearly.     

Convergence of a smoothing algorithm for symmetric cone complementarity problems with a nonmonotone line search

In this paper, we propose a smoothing algorithm for solving the monotone symmetric cone complementarity problems (SCCP for short) with a nonmonotone line search. We show that the nonmonotone algorithm is globally convergent under an assumption that the solution set of the problem concerned is nonempty. Such an assumption is weaker than those given in most existing algorithms for solving optimization problems over symmetric cones. We also prove that the solution obtained by the algorithm is a maximally complementary solution to the monotone SCCP under some assumptions. This work was supported by National Natural Science Foundation of China (Grant Nos. 10571134, 10671010) and Natural Science Foundation of Tianjin (Grant No. 07JCYBJC05200)     

A new subspace minimization conjugate gradient method with nonmonotone line search for unconstrained optimization

A new subspace minimization conjugate gradient algorithm with a nonmonotone Wolfe line search is proposed and analyzed. In the scheme, we propose two choices of the search direction by minimizing a quadratic approximation of the objective function in special subspaces, and state criterions on how to choose the direction. Under given conditions, we obtain the significant conclusion that each choice of the direction satisfies the sufficient descent property. Based on the idea on how the function is close to a quadratic function, a new strategy for choosing the initial stepsize is presented for the line search. With the used nonmonotone Wolfe line search, we prove the global convergence of the proposed method for general nonlinear functions under mild assumptions. Numerical comparisons are given with well-known CGOPT and CG_DESCENT and show that the proposed algorithm is very promising.