非线性互补问题的组合同伦算法

针对拟P_*-映射和P(τ,α,β)-映射所对应的非线性互补问题,本文对其解的存在性及有效求解算法进行了研究.文中利用组合同伦方法给出了这两类非线性互补问题存在有界解的构造性证明,并利用预估校正方法对同伦路径进行跟踪,得到了互补问题的解.通过数值算例验证了该算法的有效性.     

求解线性互补问题的同伦方法

It is well known that a linear complementarity problem (LCP) can be formulated as a system of nonsmooth equations F(x) = 0, where F is a map from Rninto itself. Using the aggregate function, we construct a smooth Newton homotopy H(x,t) = 0. Under certain assumptions, we prove the existence of a smooth path defined by the Newton homotopy which leads to a solution of the original problem, and study limiting properties of the homotopy path.     

A Regularization Newton Method for Solving Nonlinear Complementarity Problems

In this paper we construct a regularization Newton method for solving the nonlinear complementarity problem (NCP(F )) and analyze its convergence properties under the assumption that F is a P ₀ -function. We prove that every accumulation point of the sequence of iterates is a solution of NCP(F ) and that the sequence of iterates is bounded if the solution set of NCP(F ) is nonempty and bounded. Moreover, if F is a monotone and Lipschitz continuous function, we prove that the sequence of iterates is bounded if and only if the solution set of NCP(F ) is nonempty by setting , where is a parameter. If NCP(F) has a locally unique solution and satisfies a nonsingularity condition, then the convergence rate is superlinear (quadratic) without strict complementarity conditions. At each step, we only solve a linear system of equations. Numerical results are provided and further applications to other problems are discussed. Accepted 25 March 1998     

Properties of Restricted NCP Functions for Nonlinear Complementarity Problems

In this paper, we study restricted NCP functions which may be used to reformulate the nonlinear complementarity problem as a constrained minimization problem. In particular, we consider three classes of restricted NCP functions, two of them introduced by Solodov and the other proposed in this paper. We give conditions under which a minimization problem based on a restricted NCP function enjoys favorable properties, such as equivalence between a stationary point of the minimization problem and the nonlinear complementarity problem, strict complementarity at a solution of the minimization problem, and boundedness of the level sets of the objective function. We examine these properties for three restricted NCP functions and show that the merit function based on the restricted NCP function proposed in this paper enjoys favorable properties compared with those based on the other restricted NCP functions.     

NCP Functions Applied to Lagrangian Globalization for the Nonlinear Complementarity Problem

Based on NCP functions, we present a Lagrangian globalization (LG) algorithm model for solving the nonlinear complementarity problem. In particular, this algorithm model does not depend on some specific NCP function. Under several theoretical assumptions on NCP functions we prove that the algorithm model is well-defined and globally convergent. Several NCP functions applicable to the LG-method are analyzed in details and shown to satisfy these assumptions. Furthermore, we identify not only the properties of NCP functions which enable them to be used in the LG method but also their properties which enable the strict complementarity condition to be removed from the convergence conditions of the LG method. Moreover, we construct a new NCP function which possesses some favourable properties.     

Extended LQP Method for Monotone Nonlinear Complementarity Problems

To solve nonlinear complementarity problems (NCP), the logarithmic-quadratic proximal (LQP) method solves a system of nonlinear equations at each iteration. In this paper, the iterates generated by the original LQP method are extended by explicit formulas and thus an extended LQP method is presented. It is proved theoretically that the lower bound of the progress obtained by the extended LQP method is greater than that by the original LQP method. Preliminary numerical results are provided to verify the theoretical assertions and the effectiveness of both the original and the extended LQP method.     

A Hybrid Smoothing Method for Mixed Nonlinear Complementarity Problems

In this paper, we describe a new, integral-based smoothing method for solving the mixed nonlinear complementarity problem (MNCP). This approach is based on recasting MNCP as finding the zero of a nonsmooth system and then generating iterates via two types of smooth approximations to this system. Under weak regularity conditions, we establish that the sequence of iterates converges to a solution if the limit point of this sequence is regular. In addition, we show that the rate is Q-linear, Q-superlinear, or Q-quadratic depending on the level of inexactness in the subproblem calculations and we make use of the inexact Newton theory of Dembo, Eisenstat, and Steihaug. Lastly, we demonstrate the viability of the proposed method by presenting the results of numerical tests on a variety of complementarity problems.     

A Null Space Approach for Solving Nonlinear Complementarity Problems

In this work, null space techniques are employed to tackle nonlinear complementarity problems （NCPs）. NCP conditions are transform into a nonlinear programming problem, which is handled by null space algorithms, The NCP conditions are divided into two groups, Some equalities and inequalities in an NCP are treated as constraints, While other equalities and inequalities in an NCP are to be regarded as objective function. Two groups are all updated in every step. Null space approaches are extended to nonlinear complementarity problems. Two different solvers are employed for all NCP in an algorithm.     

Lagrangian Globalization Methods for Nonlinear Complementarity Problems

This paper extends the Lagrangian globalization (LG) method to the nonsmooth equation arising from a nonlinear complementarity problem (NCP) and presents a descent algorithm for the LG phase. The aim of this paper is not to present a new method for solving the NCP, but to find such that when the NCP has a solution and is a stationary point but not a solution.     

求解无限维非线性互补问题的光滑化牛顿法

研究一类无限维非线性互补问题的光滑化牛顿法.借助于非线性互补函数,将无限维非线性互补问题转化为一个非光滑算子方程.构造光滑算子逼近非光滑算子,在光滑逼近算子满足方向可微相容性的条件下,证明了光滑化牛顿法具有超线性收敛性.     

求解非线性互补问题的逐次逼近阻尼牛顿法

针对非线性互补问题,提出了与其等价的非光滑方程的逐次逼近阻尼牛顿法,并 在一定条件下证明了该算法的全局收敛性.数值结果表明,这一算法是有效的.     

A Smoothing Newton Method for General Nonlinear Complementarity Problems

Smoothing Newton methods for nonlinear complementarity problems NCP(F) often require F to be at least a P ₀-function in order to guarantee that the underlying Newton equation is solvable. Based on a special equation reformulation of NCP(F), we propose a new smoothing Newton method for general nonlinear complementarity problems. The introduction of Kanzow and Pieper's gradient step makes our algorithm to be globally convergent. Under certain conditions, our method achieves fast local convergence rate. Extensive numerical results are also reported for all complementarity problems in MCPLIB and GAMSLIB libraries with all available starting points.     

求解非线性互补问题的一个下降算法(英文)

在[1]中,Solodov将非线性互补问题等价地转化成一个带非负约束的优化问题.基于这种转化形式,我们给出了一种求解非线性互补问题的下降算法.在映射为强单调时,证明了算法的全局收敛性.     

Exceptional Family of Elements and Feasibility for Nonlinear Complementarity Problems

In this paper, we introduce the new concept of -exceptional families of elements and (,)-exceptional families of elements for continuous functions, and utilize these notions for the study of the feasibility of nonlinear complementarity problems in R ⁿ and an infinite-dimensional Hilbert space H without the assumption K ^* K.     

非线性二阶锥互补问题的低阶罚函数算法（英文）

本文研究非线性二阶锥互补问题的一般低阶罚函数算法.并将非线性二阶锥互补问题转化为序列非线性方程组.在一定条件下,当罚因子趋向于无穷时,获得序列非线性方程组的解序列以指数速度收敛于原始非线性二阶锥互补问题的解,推广了幂罚函数算法求解非线性二阶锥互补问题的结果.数值实验结果说明了算法的有效性.     

An NE/SQP Method for the Bounded Nonlinear Complementarity Problem

NE/SQP (Refs. 2–3) is a recent algorithm that has proven quite effective for solving the nonlinear complementarity problem (NCP). NE/SQP is robust in the sense that its direction-finding subproblems are always solvable; in addition, the convergence rate of this method is q-quadratic. In this note, we consider a generalized version of NE/SQP, as first described in Ref. 4, which is suitable for the bounded NCP. We extend the work in Ref. 4 by demonstrating a stronger convergence result and present numerical results on test problems.     

求解非线性互补问题的内点正算法

针对非线性互补问题,提出了与其等价的非光滑方程的内点正算法,并在一定条件下证明了该算法的收敛性定理。数值结果表明,该算法是十分有效的。     

A Projected Algebraic Multigrid Method for Linear Complementarity Problems

We present an algebraic version of an iterative multigrid method for obstacle problems, called projected algebraic multigrid (PAMG) here. We show that classical algebraic multigrid algorithms can easily be extended to deal with this kind of problem. This paves the way for efficient multigrid solution of obstacle problems with partial differential equations arising, for example, in financial engineering.     

同伦分析方法：一种新的求解非线性问题的近似解析方法

本文描述了一种称为“同伦分析方法”（ＨＡＭ）的新的求解非线性问题的近似解析方法之基本思想·不同于摄动展开方法，“同伦分析方法”的有效性不依赖于所研究的非线性方程中是否含有小参数·因此，该方法提供了一个强有力的分析非线性问题的新工具·作为示例，我们应用一个典型的非线性问题来说明该方法的有效性及其巨大潜力·