共查询到20条相似文献,搜索用时 46 毫秒
1.
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. 相似文献
2.
The nonlinear complementarity problem is generalized by replacing the usual nonnegative ordering ofR
n
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. 相似文献
3.
Bidushi Chakraborty Sudarshan Nanda Mahendra Prasad Biswal 《Mediterranean Journal of Mathematics》2005,2(3):291-299
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. 相似文献
4.
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. 相似文献
5.
Monotone generalized variational inequalities and generalized complementarity problems 总被引:1,自引:0,他引:1
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. 相似文献
6.
The generalized linear complementarity problem revisited 总被引:5,自引:0,他引:5
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. 相似文献
7.
M. A. Tawhid 《Computational Optimization and Applications》2008,39(1):51-74
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
0-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
1, semismooth, and locally Lipschitzian. 相似文献
8.
为了高效求解中小型线性互补问题,本文提出了改进的分块模方法,并证明了关于严格对角占优(对角元素均为正数)线性互补问题的收敛性.对于广义对角占优线性互补问题,先将其转化为严格对角占优线性互补问题,再采用改进的分块模方法求解.数值结果表明,改进的分块模方法在求解广义对角占优线性互补问题时在内迭代次数和计算时间上均明显优于分... 相似文献
9.
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. 相似文献
10.
Igor V. Konnov 《Optimization Letters》2009,3(4):573-582
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. 相似文献
11.
Michael J. Todd 《Mathematical Programming》1982,24(1):216-224
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. 相似文献
12.
David P. Williamson Michel X. Goemans Milena Mihail Vijay V. Vazirani 《Combinatorica》1995,15(3):435-454
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. 相似文献
13.
隐互补问题在自然科学中的诸多领域有着广泛的应用.本文研究了一类广义隐互补问题.本文将外梯度法应用到这类广义隐互补问题中,研究了在伪单调的条件下算法的收敛性,并证明了算法具有R-线性收敛性. 相似文献
14.
Zhensheng Yu Yangchen Liu Xinyue Gan 《Numerical Functional Analysis & Optimization》2017,38(11):1458-1472
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. 相似文献
15.
Interpolation, correlation identities, and inequalities for infinitely divisible variables 总被引:1,自引:0,他引:1
Christian Houdré Victor Pérez-Abreu Donatas Surgailis 《Journal of Fourier Analysis and Applications》1998,4(6):651-668
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. 相似文献
16.
17.
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]. 相似文献
18.
一种新的向量互补问题 总被引:1,自引:1,他引:0
本文在实局部凸空间中引入了一种新的向量互补问题,这一向量互补问题不仅包含了由Yu和Yao提出的广义向量互补问题由Chen和Yang定义的弱向量互补问题,而且还包含了Isac意义下的隐互补问题。本文还讨论了新的向量互补问题,向量变分不等式,向量单向极小化问题和最小元问题之间的关系,给出了这一向量互补问题解的存在定理。 相似文献
19.
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. 相似文献
20.
We consider a regularization method for nonlinear complementarity problems with F being a P0-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 φ2. 相似文献