A new modified one-step smoothing Newton method for solving the general mixed complementarity problem

In last decades, there has been much effort on the solution and the analysis of the mixed complementarity problem (MCP) by reformulating MCP as an unconstrained minimization involving an MCP function. In this paper, we propose a new modified one-step smoothing Newton method for solving general (not necessarily P₀) mixed complementarity problems based on well-known Chen-Harker-Kanzow-Smale smooth function. Under suitable assumptions, global convergence and locally superlinear convergence of the algorithm are established.     

求解张量随机互补问题的光滑牛顿算法

近年来, 越来越多的人意识到随机互补问题在经济管理中具有十分重要的作用。有学者已将随机互补问题由矩阵推广到张量, 并提出了张量随机互补问题。本文通过引入一类光滑函数, 提出了求解张量随机互补问题的一种光滑牛顿算法, 并证明了算法的全局和局部收敛性, 最后通过数值实验验证了算法的有效性。     

求解张量随机互补问题的光滑牛顿算法

近年来, 越来越多的人意识到随机互补问题在经济管理中具有十分重要的作用。有学者已将随机互补问题由矩阵推广到张量, 并提出了张量随机互补问题。本文通过引入一类光滑函数, 提出了求解张量随机互补问题的一种光滑牛顿算法, 并证明了算法的全局和局部收敛性, 最后通过数值实验验证了算法的有效性。     

一种求解非线性互补问题的filter内点算法

利用Armijio条件和信赖域方法,构造新的价值函数.首次将内点算法与filter技术结合起来,提出一种求解非线性互补问题的新算法,即filter内点算法.在主算法中使用Armijio型线搜索求取步长,在修复算法中使用信赖域方法进行适当控制以保证算法的收敛性.文章还讨论了算法的全局收敛性.最后用数值实验表明了该方法是有效的.     

Predictor-corrector method for nonlinear complementarity problem

Recently, Ye et al. proved that the predictor-corrector method proposed by Mizuno et al. maintains -iteration complexity while exhibiting the quadratic convergence of the dual gap to zero under very mild conditions. This impressive result becomes the best-known in the interior point methods. In this paper, we modify the predictor-corrector method and then extend it to solving the nonlinear complementarity problem. We prove that the new method has a -iteration complexity while maintaining the quadratic asymptotic convergence.     

One-step smoothing Newton method for solving the mixed complementarity problem with a function

The mixed complementarity problem (denote by MCP(F)) can be reformulated as the solution of a smooth system of equations. In the paper, based on a perturbed mid function, we propose a new smoothing function, which has an important property, not satisfied by many other smoothing function. The existence and continuity of a smooth path for solving the mixed complementarity problem with a P₀ function are discussed. Then we presented a one-step smoothing Newton algorithm to solve the MCP with a P₀ function. The global convergence of the proposed algorithm is verified under mild conditions. And by using the smooth and semismooth technique, the rate of convergence of the method is proved under some suitable assumptions.     

非线性互补问题的一种不可行非内点连续算法

基于Chen-Harker—Kanzow-Smale光滑函数，对单调非线性互补问题NCP(f)给出了一种不可行非内点连续算法，该算法在每次迭代时只需求解一个线性等式系统，执行一次线搜索，算法在NCP(f)的解处不需要严格互补的条件下，具有全局线性收敛性和局部二次收敛性．     

A smoothing conic trust region filter method for the nonlinear complementarity problem

This paper discusses nonlinear complementarity problems; its goal is to present a globally and superlinearly convergent algorithm for the discussed problems. Filter methods are extensively studied to handle nonlinear complementarity problem. Because of good numerical results, filter techniques are attached. By means of a filter strategy, we present a new trust region method based on a conic model for nonlinear complementarity problems. Under a proper condition, the superlinear convergence of the algorithm is established without the strict complementarity condition.     

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 class of smoothing functions for nonlinear and mixed complementarity problems

We propose a class of parametric smooth functions that approximate the fundamental plus function, (x)₊=max{0, x}, by twice integrating a probability density function. This leads to classes of smooth parametric nonlinear equation approximations of nonlinear and mixed complementarity problems (NCPs and MCPs). For any solvable NCP or MCP, existence of an arbitrarily accurate solution to the smooth nonlinear equations as well as the NCP or MCP, is established for sufficiently large value of a smoothing parameter . Newton-based algorithms are proposed for the smooth problem. For strongly monotone NCPs, global convergence and local quadratic convergence are established. For solvable monotone NCPs, each accumulation point of the proposed algorithms solves the smooth problem. Exact solutions of our smooth nonlinear equation for various values of the parameter , generate an interior path, which is different from the central path for interior point method. Computational results for 52 test problems compare favorably with these for another Newton-based method. The smooth technique is capable of solving efficiently the test problems solved by Dirkse and Ferris [6], Harker and Xiao [11] and Pang & Gabriel [28].This material is based on research supported by Air Force Office of Scientific Research Grant F49620-94-1-0036 and National Science Foundation Grant CCR-9322479.     

A smoothing method for second order cone complementarity problem

In this paper, the second order cone complementarity problem is studied. Based on a perturbed symmetrically smoothing function, which has coerciveness under proper conditions, we present a smoothing Newton method for this problem. The boundedness of the level set can be obtained from the coerciveness, which plays an important role in the convergence analysis. Furthermore, the proposed algorithm for the reformulation has no restrictions on the starting point and solves only one system of equations. Preliminary numerical results indicate that the algorithm is effective.     

Newton's method for the nonlinear complementarity problem: A B-differentiable equation approach

This paper describes a damped-Newton method for solving the nonlinear complementarity problem when it is formulated as a system of B-differentiable equations through the use of the Minty-map. This general Newton algorithm contains a one-dimensional line search and possesses a global convergence property under certain conditions; modifications and heuristic implementations of the algorithm for the case when these conditions do not hold are also discussed. The numerical experiments show that, in general, this new scheme is more efficient and robust than the traditional Josephy-Newton algorithm.     

Integral global optimization method for solution of nonlinear complementarity problems

The mapping in a nonlinear complementarity problem may be discontinuous. The integral global optimization algorithm is proposed to solve a nonlinear complementarity problem with a robust piecewise continuous mapping. Numerical examples are given to illustrate the effectiveness of the algorithm.     

A two-step modulus-based multisplitting iteration method for the nonlinear complementarity problem

In this paper, we construct a two-step modulus-based multisplitting iteration method based on multiple splittings of the system matrix for the nonlinear complementarity problem. And we prove its convergence when the system matrix is an $H$-matrix with positive diagonal elements. Numerical experiments show that the proposed method is efficient.     

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 modified SQP-filter method for nonlinear complementarity problem

The nonlinear complementarity problem can be reformulated as a nonlinear programming. For solving nonlinear programming, sequential quadratic programming (SQP) type method is very effective. Moreover, filter method, for its good numerical results, are extensively studied to handle nonlinear programming problems recently. In this paper, a modified quadratic subproblem is proposed. Based on it, we employ filter technique to tackle nonlinear complementarity problem. This method has no demand on initial point. The restoration phase, which is always used in traditional filter method, is not needed. Global convergence results of the proposed algorithm are established under suitable conditions. Some numerical results are reported in this paper.     

非线性l1问题的光滑近似算法

为非线性l1问题的求解构造了光滑逼近函数.首先将非线性l1问题转化为等价的不可微优化问题;其次通过两步提出光滑逼近函数的一般性构造方法;最后进行了数值仿真.文中介绍了光滑逼近函数的有关性质,指出相关文献已有的光滑函数方法是本文的特例,并证明了方法的收敛性及有效性.     

Inexact Newton methods for the nonlinear complementarity problem

An exact Newton method for solving a nonlinear complementarity problem consists of solving a sequence of linear complementarity subproblems. For problems of large size, solving the subproblems exactly can be very expensive. In this paper we study inexact Newton methods for solving the nonlinear, complementarity problem. In such an inexact method, the subproblems are solved only up to a certain degree of accuracy. The necessary accuracies that are needed to preserve the nice features of the exact Newton method are established and analyzed. We also discuss some extensions as well as an application. This research was based on work supported by the National Science Foundation under grant ECS-8407240.     

基于光滑化方法求解非线性l1问题

讨论了求解非线性l1问题的一种新的光滑函数法.通过对非线性l1问题模型的转化,将该问题化为一个不可微优化问题,据此提出了基于BFGS迭代的非线性l1问题的光滑函数法,介绍了非线性l1问题的光滑函数的有关性质、算法步骤及其收敛性.数值仿真显示了提出的光滑函数方法可以避免数值计算的溢出,具有一定的有效性.