On the existence and uniqueness of solutions in nonlinear complementarity theory

A complementarity problem is said to be globally uniquely solvable (GUS) if it has a unique solution, and this property will not change, even if any constant term is added to the mapping generating the problem.A characterization of the GUS property which generalizes a basic theorem in linear complementarity theory is given. Known sufficient conditions given by Cottle, Karamardian, and Moré for the nonlinear case are also shown to be generalized. In particular, several open questions concerning Cottle's condition are settled and a new proof is given for the sufficiency of this condition.A simple characterization for the two-dimensional case and a necessary condition for then-dimensional case are also given.The research described in this paper was carried out while N. Megiddo was visiting Tokyo Institute of Technology under a Fellowship of the Japan Society for the Promotion of Science.     

Existence theory for generalized nonlinear complementarity problems

The nonlinear complementarity problem is generalized by replacing the usual nonnegative ordering ofR ⁿ by an ordering generated by a convex cone. Two new classes of operators are introduced, each of which is used to guarantee the existence of a solution to the generalized problem. The new classes can be seen to be broader than previously studied classes. In addition, conditions are presented under which the solution set of the generalized linear complementarity problem is shown to have at most a finite number of solutions.This research was partially supported by National Science Foundation, Grant No. GP-16293, and constitutes part of the junior author's doctoral thesis. The authors are indebted to Dr. Carlton E. Lemke for many helpful discussions.     

Equivalence of the Generalized Vertical Block Linear Complementarity Problems and Linear Complementarity Problems

In this paper, generalization of a vertical block linear complementarity problem associated with two different types of matrices, one of which is a square matrix and the other is a vertical block matrix, is proposed. The necessary and sufficient conditions for the existence of the solution of the generalized vertical block linear complementarity problem is derived and the relationship between the solution set of the generalized vertical block linear complementarity problem and the linear complementarity problem is established. It is proved that the generalized vertical block linear complementarity problem has the P-property if and only if the vertical block linear complementarity problem has the P-property.     

Partial Augmented Lagrangian Method and Mathematical Programs with Complementarity Constraints

In this paper, we apply a partial augmented Lagrangian method to mathematical programs with complementarity constraints (MPCC). Specifically, only the complementarity constraints are incorporated into the objective function of the augmented Lagrangian problem while the other constraints of the original MPCC are retained as constraints in the augmented Lagrangian problem. We show that the limit point of a sequence of points that satisfy second-order necessary conditions of the partial augmented Lagrangian problems is a strongly stationary point (hence a B-stationary point) of the original MPCC if the limit point is feasible to MPCC, the linear independence constraint qualification for MPCC and the upper level strict complementarity condition hold at the limit point. Furthermore, this limit point also satisfies a second-order necessary optimality condition of MPCC. Numerical experiments are done to test the computational performances of several methods for MPCC proposed in the literature. This research was partially supported by the Research Grants Council (BQ654) of Hong Kong and the Postdoctoral Fellowship of The Hong Kong Polytechnic University. Dedicated to Alex Rubinov on the occassion of his 65th birthday.     

Monotone generalized variational inequalities and generalized complementarity problems

Some existence results for generalized variational inequalities and generalized complementarity problems involving quasimonotone and pseudomonotone set-valued mappings in reflexive Banach spaces are proved. In particular, some known results for nonlinear variational inequalities and complementarity problems in finite-dimensional and infinite-dimensional Hilbert spaces are generalized to quasimonotone and pseudomonotone set-valued mappings and reflexive Banach spaces. Application to a class of generalized nonlinear complementarity problems studied as mathematical models for mechanical problems is given.The research of the first author was supported by the National Natural Science Foundation of P. R. China and by the Ethel Raybould Fellowship, University of Queensland, St. Lucia, Brisbane, Australia.     

The generalized linear complementarity problem revisited

Given a vertical block matrixA, we consider in this paper the generalized linear complementarity problem VLCP(q, A) introduced by Cottle and Dantzig. We formulate this problem as a linear complementarity problem with a square matrixM, a formulation which is different from a similar formulation given earlier by Lemke. Our formulation helps in extending many well-known results in linear complementarity to the generalized linear complementarity problem. We also show that the class of vertical block matrices which Cottle and Dantzig's algorithm can process is the same as the class of equivalent square matrices which Lemke's algorithm can process. We also present some degree-theoretic results on a vertical block matrix.     

An application of <Emphasis Type="Italic">H</Emphasis>-differentiability to nonnegative and unrestricted generalized complementarity problems

This paper deals with nonnegative nonsmooth generalized complementarity problem, denoted by GCP(f,g). Starting with H-differentiable functions f and g, we describe H-differentials of some GCP functions and their merit functions. We show how, under appropriate conditions on H-differentials of f and g, minimizing a merit function corresponding to f and g leads to a solution of the generalized complementarity problem. Moreover, we generalize the concepts of monotonicity, P ₀-property and their variants for functions and use them to establish some conditions to get a solution for generalized complementarity problem. Our results are generalizations of such results for nonlinear complementarity problem when the underlying functions are C ¹, semismooth, and locally Lipschitzian.     

改进的分块模方法求解对角占优线性互补问题

为了高效求解中小型线性互补问题,本文提出了改进的分块模方法,并证明了关于严格对角占优(对角元素均为正数)线性互补问题的收敛性.对于广义对角占优线性互补问题,先将其转化为严格对角占优线性互补问题,再采用改进的分块模方法求解.数值结果表明,改进的分块模方法在求解广义对角占优线性互补问题时在内迭代次数和计算时间上均明显优于分...     

A method for solving the general parametric linear complementarity problem

This paper presents a solution method for the general (mixed integer) parametric linear complementarity problem pLCP(q(θ),M), where the matrix M has a general structure and integrality restriction can be enforced on the solution. Based on the equivalence between the linear complementarity problem and mixed integer feasibility problem, we propose a mixed integer programming formulation with an objective of finding the minimum 1-norm solution for the original linear complementarity problem. The parametric linear complementarity problem is then formulated as multiparametric mixed integer programming problem, which is solved using a multiparametric programming algorithm. The proposed method is illustrated through a number of examples.     

A splitting type algorithm for multi-valued complementarity problems

We consider a generalized complementarity problem whose cost mapping is multi-valued and is the sum of upper Z and antitone mappings. We suggest a simple splitting type algorithm which utilizes an extended Jacobi iteration. Its convergence is proved under mild assumptions. Preliminary results of numerical experiments confirm efficiency of the algorithm presented. This work was supported by RFBR–NNSF Grant No. 07-01-92101.     

On the computational complexity of piecewise-linear homotopy algorithms

We show that piecewise-linear homotopy algorithms may take a number of steps that grows exponentially with the dimension when solving a system of linear equations whose solution lies close to the starting point. Our examples are based on an example of Murty exhibiting exponential growth for Lemke's algorithm for the linear complementarity problem.This research was supported in part by NSF grant ECS-7921279 and by a Guggenheim Fellowship.     

A primal-dual approximation algorithm for generalized steiner network problems

We present the first polynomial-time approximation algorithm for finding a minimum-cost subgraph having at least a specified number of edges in each cut. This class of problems includes, among others, the generalized Steiner network problem, also called the survivable network design problem. Ifk is the maximum cut requirement of the problem, our solution comes within a factor of 2k of optimal. Our algorithm is primal-dual and shows the importance of this technique in designing approximation algorithms.Research supported by an NSF Graduate Fellowship, DARPA contracts N00014-91-J-1698 and N00014-92-J-1799, and AT&T Bell Laboratories.Research supported in part by Air Force contract F49620-92-J-0125 and DARPA contract N00014-92-J-1799.Part of this work was done while the author was visiting AT&T Bell Laboratories and Bellcore.     

一类广义隐互补问题的外梯度法

隐互补问题在自然科学中的诸多领域有着广泛的应用.本文研究了一类广义隐互补问题.本文将外梯度法应用到这类广义隐互补问题中,研究了在伪单调的条件下算法的收敛性,并证明了算法具有R-线性收敛性.     

Nonmonotone Inexact Newton Method for the Extended Linear Complementarity Problem

This paper presents a nonmonotone inexact Newton-type method for the extended linear complementarity problem (ELCP). We first reformulate the optimization system of the ELCP problem into a system of smoothed equations. Then we solve this system by a nonmonotone inexact Newton-type algorithm. The global convergence is obtained and numerical tests for some classes of ELCP include linear complementarity, horizontal linear complementarity, and generalized linear complementarity problems are also given to show the e?ciency of the proposed algorithm.     

Interpolation, correlation identities, and inequalities for infinitely divisible variables

We present an interpolation formula for the expectation of functions of infinitely divisible (i.d.) variables. This is then applied to study the association problem for i.d. vectors and to present new covariance expansions and correlation inequalities. Acknowledgements and Notes. The research of C. Houdré was supported in part by an NSF Mathematical Sciences Post-Doctoral Fellowship and by an NSF-NATO Postdoctoral Fellowship and by the NSF grant No. DMS-98032039. This research was completed while V. Pérez-Abreu was visiting the Georgia Institute of Technology.     

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

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

On weak generalized positive subdefinite matrices and the linear complementarity problem

In this article, we present a weaker version of the class of generalized positive subdefinite matrices introduced by Crouzeix and Komlósi [J.P. Crouzeix and S. Komlósi, The Linear Complementarity Problem and the Class of Generalized Positive Subdefinite Matrices, Applied Optimization, Vol. 59, Kluwer, Dordrecht, 2001, pp. 45–63], which is new in the literature, and obtain some properties of weak generalized positive subdefinite (WGPSBD) matrices. We show that this weaker class of matrices is also captured by row-sufficient matrices introduced by Cottle et al. [R.W. Cottle, J.S. Pang, and V. Venkateswaran, Sufficient matrices and the linear complementarity problem, Linear Algebra Appl. 114/115 (1989), pp. 231–249] and show that for WGPSBD matrices under appropriate assumptions, the solution set of a linear complementarity problem is the same as the set of Karush–Kuhn–Tucker-stationary points of the corresponding quadratic programming problem. This further extends the results obtained in an earlier paper by Neogy and Das [S.K. Neogy and A.K. Das, Some properties of generalized positive subdenite matrices, SIAM J. Matrix Anal. Appl. 27 (2006), pp. 988–995].     

一种新的向量互补问题

本文在实局部凸空间中引入了一种新的向量互补问题,这一向量互补问题不仅包含了由Ｙｕ和Ｙａｏ提出的广义向量互补问题由Ｃｈｅｎ和Ｙａｎｇ定义的弱向量互补问题,而且还包含了Ｉｓａｃ意义下的隐互补问题。本文还讨论了新的向量互补问题,向量变分不等式,向量单向极小化问题和最小元问题之间的关系,给出了这一向量互补问题解的存在定理。     

The basic theorem of complementarity revisited

The basic theorm of (linear) complementarity was stated in a 1971 paper [6] by B.C. Eaves who credited C.E. Lemke for giving a constructive proof based on his almost complementary pivot algorithm. This theorem asserts that associated with an arbitrary linear complementarity problem, a certain augmented problem always possesses a solution. Many well-known existence results pertaining to the linear complementarity problem are consequences of this fundamental theorem.In this paper, we explore some further implications of the basic theorem of complementarity and derive new existence results for the linear complementarity problem. Based on these results, conditions for the existence of a solution to a linear complementarity problem with a fully-semimonotone matrix are examined. The class of the linear complementarity problems with aG-matrix is also investigated.The work of this author was based on research supported by the National Science Foundation under grant ECS-8717968.     

A regularization semismooth Newton method based on the generalized Fischer–Burmeister function for -NCPs

We consider a regularization method for nonlinear complementarity problems with F being a P₀-function which replaces the original problem with a sequence of the regularized complementarity problems. In this paper, this sequence of regularized complementarity problems are solved approximately by applying the generalized Newton method for an equivalent augmented system of equations, constructed by the generalized Fischer–Burmeister (FB) NCP-functions φ_p with p>1. We test the performance of the regularization semismooth Newton method based on the family of NCP-functions through solving all test problems from MCPLIB. Numerical experiments indicate that the method associated with a smaller p, for example p[1.1,2], usually has better numerical performance, and the generalized FB functions φ_p with p[1.1,2) can be used as the substitutions for the FB function φ₂.