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 Regularization Semismooth Newton Method for $P_0$-NCPs with a Non-Monotone Line Search

In this paper, we propose a regularized version of the generalized NCP-function proposed by Hu, Huang and Chen [J. Comput. Appl. Math., 230 (2009), pp. 69-82]. Based on this regularized function, we propose a semismooth Newton method for solving nonlinear complementarity problems, where a non-monotone line search scheme is used. In particular, we show that the proposed non-monotone method is globally and locally superlinearly convergent under suitable assumptions. We test the proposed method by solving the test problems from MCPLIB. Numerical experiments indicate that this algorithm has better numerical performance in the case of $p=5$ and $\theta\in[0.25,075]$ than other cases.     

The convergence of a modified smoothing-type algorithm for the symmetric cone complementarity problem

The symmetric cone complementarity problem (denoted by SCCP) is a broad class of optimization problems, which contains the semidefinite complementarity problem, the second-order cone complementarity problem, and the nonlinear complementarity problem. In this paper we first extend the smoothing function proposed by Huang et al. (Sci. China 44:1107–1114, 2001) for the nonlinear complementarity problem to the context of symmetric cones and show that it is coercive under suitable assumptions. Based on this smoothing function, a smoothing-type algorithm, which is a modified version of the Qi-Sun-Zhou method (Qi et al. in Math. Program. 87:1–35, 2000), is proposed for solving the SCCP. By using the theory of Euclidean Jordan algebras, we prove that the proposed algorithm is globally and locally quadratically convergent under suitable assumptions. Preliminary numerical results for some second-order cone complementarity problems are reported which indicate that the proposed algorithm is effective.     

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.     

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.     

Analysis of a smoothing Newton method for second-order cone complementarity problem

In this paper, we consider the second-order cone complementarity problem with P ₀-property. By introducing a smoothing parameter into the Fischer-Burmeister function, we present a smoothing Newton method for the second-order cone complementarity problem. The proposed algorithm solves only a linear system of equations and performs only one line search at each iteration. At the same time, the algorithm does not have restrictions on its starting point and has global convergence. Under the assumption of nonsingularity, we establish the locally quadratic convergence of the algorithm without strict complementarity condition. Preliminary numerical results show that the algorithm is promising.     

Superlinear/quadratic smoothing Broyden-like method for the generalized nonlinear complementarity problem

In this article, we first reformulate the generalized nonlinear complementarity problem (GNCP) over a polyhedral cone as a smoothing system of equations and then suggest a smoothing Broyden-like method for solving it. The proposed algorithm has to solve only one system of nonhomogeneous linear equations, perform only one line search and update only one matrix per iteration. We show that the iteration sequence generated by the proposed algorithm converges globally and superlinearly under suitable conditions. Furthermore, the algorithm has local quadratic convergence under mild assumptions. Some numerical examples are given to illustrate the performance and efficiency of the presented algorithm.     

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.     

A smoothing Newton method for the second-order cone complementarity problem

In this paper we introduce a new smoothing function and show that it is coercive under suitable assumptions. Based on this new function, we propose a smoothing Newton method for solving the second-order cone complementarity problem (SOCCP). The proposed algorithm solves only one linear system of equations and performs only one line search at each iteration. It is shown that any accumulation point of the iteration sequence generated by the proposed algorithm is a solution to the SOCCP. Furthermore, we prove that the generated sequence is bounded if the solution set of the SOCCP is nonempty and bounded. Under the assumption of nonsingularity, we establish the local quadratic convergence of the algorithm without the strict complementarity condition. Numerical results indicate that the proposed algorithm is promising.     

On the convergence of general regularization and smoothing schemes for mathematical programs with complementarity constraints

We extend the convergence analysis of a smoothing method [M. Fukushima and J.-S. Pang (2000). Convergence of a smoothing continuation method for mathematical programs with complementarity constraints. In: M. Théra and R. Tichatschke (Eds.), Ill-posed Variational Problems and Regularization Techniques, pp. 99–110. Springer, Berlin/Heidelberg.] to a general class of smoothing functions and show that a weak second-order necessary optimality condition holds at the limit point of a sequence of stationary points found by the smoothing method. We also show that convergence and stability results in [S. Scholtes (2001). Convergence properties of a regularization scheme for mathematical programs with complementarity constraints. SIAM J. Optim., 11, 918–936.] hold for a relaxation problem suggested by Scholtes [S. Scholtes (2003). Private communications.] using a class of smoothing functions. In addition, the relationship between two technical, yet critical, concepts in [M. Fukushima and J.-S. Pang (2000). Convergence of a smoothing continuation method for mathematical programs with complementarity constraints. In: M. Théra and R. Tichatschke (Eds.), Ill-posed Variational Problems and Regularization Techniques, pp. 99–110. Springer, Berlin/Heidelberg; S. Scholtes (2001). Convergence properties of a regularization scheme for mathematical programs with complementarity constraints. SIAM J. Optim., 11, 918–936.] for the convergence analysis of the smoothing and regularization methods is discussed and a counter-example is provided to show that the stability result in [S. Scholtes (2001). Convergence properties of a regularization scheme for mathematical programs with complementarity constraints. SIAM J. Optim., 11, 918–936.] cannot be extended to a weaker regularization.     

Strong convergence properties of a modified nonmonotone smoothing algorithm for the SCCP

The smoothing algorithms have been successfully applied to solve the symmetric cone complementarity problem (denoted by SCCP), which in general have the global and local superlinear/quadratic convergence if the solution set of the SCCP is nonempty and bounded. Huang, Hu and Han [Science in China Series A: Mathematics, 52: 833–848, 2009] presented a nonmonotone smoothing algorithm for solving the SCCP, whose global convergence is established by just requiring that the solution set of the SCCP is nonempty. In this paper, we propose a new nonmonotone smoothing algorithm for solving the SCCP by modifying the version of Huang-Hu-Han’s algorithm. We prove that the modified nonmonotone smoothing algorithm not only is globally convergent but also has local superlinear/quadratical convergence if the solution set of the SCCP is nonempty. This convergence result is stronger than those obtained by most smoothing-type algorithms. Finally, some numerical results are reported.     

Quadratic convergence of a smoothing Newton method for symmetric cone programming without strict complementarity

This paper deals with symmetric cone programming (SCP), which includes the linear programming (LP), the second-order cone programming (SOCP), the semidefinite programming (SDP) as special cases. Based on the Chen?CMangasarian smoothing function of the projection operator onto symmetric cones, we establish a smoothing Newton method for SCP. Global and quadratic convergence of the proposed algorithm is established under the primal and dual constraint nondegeneracies, but without the strict complementarity. Moreover, we show the equivalence at a Karush?CKuhn?CTucker (KKT) point among the primal and dual constraint nondegeneracies, the nonsingularity of the B-subdifferential of the smoothing counterpart of the KKT system, and the nonsingularity of the corresponding Clarke??s generalized Jacobian.     

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.     

A non-interior continuation method for second-order cone programming

We extend the smoothing function proposed by Huang, Han and Chen [Journal of Optimization Theory and Applications, 117 (2003), pp. 39–68] for the non-linear complementarity problems to the second-order cone programming (SOCP). Based on this smoothing function, a non-interior continuation method is presented for solving the SOCP. The proposed algorithm solves only one linear system of equations and performs only one line search at each iteration. It is shown that our algorithm is globally and locally superlinearly convergent in absence of strict complementarity at the optimal solution. Numerical results indicate the effectiveness of the algorithm.     

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.     

线性均衡约束最优化的一个广义投影强次可行方向法

本文讨论带线性均衡约束最优化问题,首先利用摄动技术和一个互补函数将问题等价转化为一般约束最优化问题,然后结合广义投影技术和强次可行方向法思想,建立了问题的一个新算法.算法在迭代过程中保证搜索方向不为零,从而使得每次迭代只需计算一次广义投影.在适当的条件下,证明了算法的全局收敛性,并对算法进行了初步的数值试验.     

A new one‐step smoothing newton method for the second‐order cone complementarity problem

In this paper, we present a new one‐step smoothing Newton method for solving the second‐order cone complementarity problem (SOCCP). Based on a new smoothing function, the SOCCP is approximated by a family of parameterized smooth equations. At each iteration, the proposed algorithm only need to solve one system of linear equations and perform only one Armijo‐type line search. The algorithm is proved to be convergent globally and superlinearly without requiring strict complementarity at the SOCCP solution. Moreover, the algorithm has locally quadratic convergence under mild conditions. Numerical experiments demonstrate the feasibility and efficiency of the new algorithm. Copyright © 2010 John Wiley & Sons, Ltd.     

A new class of smoothing functions and a smoothing Newton method for complementarity problems

In this paper, we introduce a new class of smoothing functions, which include some popular smoothing complementarity functions. We show that the new smoothing functions possess a system of favorite properties. The existence and continuity of a smooth path for solving the nonlinear complementarity problem (NCP) with a P ₀ function are discussed. The Jacobian consistency of this class of smoothing functions is analyzed. Based on the new smoothing functions, we investigate a smoothing Newton algorithm for the NCP and discuss its global and local superlinear convergence. Some preliminary numerical results are reported.     

A non-interior continuation method for generalized linear complementarity problems

In this paper, we propose a non-interior continuation method for solving generalized linear complementarity problems (GLCP) introduced by Cottle and Dantzig. The method is based on a smoothing function derived from the exponential penalty function first introduced by Kort and Bertsekas for constrained minimization. This smoothing function can also be viewed as a natural extension of Chen-Mangasarian’s neural network smooth function. By using the smoothing function, we approximate GLCP as a family of parameterized smooth equations. An algorithm is presented to follow the smoothing path. Under suitable assumptions, it is shown that the algorithm is globally convergent and local Q-quadratically convergent. Few preliminary numerical results are also reported. Received September 3, 1997 / Revised version received April 27, 1999?Published online July 19, 1999