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.     

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.     

A continuation method for linear complementarity problems with P 0 matrix

In this article, we propose a new continuation method for solving the linear complementarity problem (LCP). The method solves one system of linear equations and carries out only a one-line search at each iteration. The continuation method is based on a modified smoothing function. The existence and continuity of a smooth path for solving the LCP with a P ₀ matrix are discussed. We investigate the boundedness of the iteration sequence generated by our continuation method under the assumption that the solution set of the LCP is nonempty and bounded. It is shown to converge to an LCP solution globally linearly and locally superlinearly without the assumption of strict complementarity at the solution under suitable assumption. In addition, some numerical results are also reported in this article.     

Solution Sets of Quadratic Complementarity Problems

In this paper, we study quadratic complementarity problems, which form a subclass of nonlinear complementarity problems with the nonlinear functions being quadratic polynomial mappings. Quadratic complementarity problems serve as an important bridge linking linear complementarity problems and nonlinear complementarity problems. Various properties on the solution set for a quadratic complementarity problem, including existence, compactness and uniqueness, are studied. Several results are established from assumptions given in terms of the comprising matrices of the underlying tensor, henceforth easily checkable. Examples are given to demonstrate that the results improve or generalize the corresponding quadratic complementarity problem counterparts of the well-known nonlinear complementarity problem theory and broaden the boundary knowledge of nonlinear complementarity problems as well.     

Error bounds for nondegenerate monotone linear complementarity problems

Error bounds and upper Lipschitz continuity results are given for monotone linear complementarity problems with a nondegenerate solution. The existence of a nondegenerate solution considerably simplifies the error bounds compared with problems for which all solutions are degenerate. Thus when a point satisfies the linear inequalities of a nondegenerate complementarity problem, the residual that bounds the distance from a solution point consists of the complementarity condition alone, whereas for degenerate problems this residual cannot bound the distance to a solution without adding the square root of the complementarity condition to it. This and other simplified results are a consequence of the polyhedral characterization of the solution set as the intersection of the feasible region {zMz + q 0, z 0} with a single linear affine inequality constraint.This material is based on research supported by National Science Foundation Grants CCR-8723091 and DCR-8521228 and Air Force Office of Scientific Research Grant AFOSR-86-0172.     

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.     

Robustness and nondegenerateness for linear complementarity problems

In this paper the main focus is on a stability concept for solutions of a linear complementarity problem. A solution of such a problem is robust if it is stable against slight perturbations of the data of the problem. Relations are investigated between the robustness, the nondegenerateness and the isolatedness of solutions. It turns out that an isolated nondegenerate solution is robust and also that a robust nondegenerate solution is isolated. Since the class of linear complementarity problems with only robust solutions or only nondegenerate solutions is not an open set, attention is paid to Garcia's classG _n of linear complementarity problems. The nondegenerate problems inG _n form an open set.     

Exceptional family and solvability of copositive complementarity problems

In this paper, by extending the concept of exceptional family to complementarity problems over the cone of symmetric copositive real matrices, we propose an existence theorem of a solution to the copositive complementarity problem. Extensions of Isac–Carbone?s condition, Karamardian?s condition, weakly properness and coercivity are also introduced. Several applications of these results are presented, and we prove that without exceptional family is a sufficient and necessary condition for the solvability of pseudomonotone copositive complementarity problems.     

On the ERM formulation and a stochastic approximation algorithm of the stochastic-R_0 EVLCP

In this paper, a class of stochastic extended vertical linear complementarity problems is studied as an extension of the stochastic linear complementarity problem. The expected residual minimization (ERM) formulation of this stochastic extended vertical complementarity problem is proposed based on an NCP function. We study the corresponding properties of the ERM problem, such as existence of solutions, coercive property and differentiability. Finally, we propose a descent stochastic approximation method for solving this problem. A comprehensive convergence analysis is given. A number of test examples are constructed and the numerical results are presented.     

An extension of the Jacobi algorithm for multi-valued mixed complementarity problems

We consider a generalized mixed complementarity problem (MCP) with box constraints and multi-valued cost mapping. We introduce a concept of an upper Z-mapping, which generalizes the well-known concept of the single-valued Z-mapping and involves the diagonal multi-valued mappings, and suggest an extension of the Jacobi algorithm for the above problem containing a composition of such mappings. Being based on its convergence theorem, we establish several existence and uniqueness results. Some examples of the applications are also given.     

Generalized linear complementarity problems treated without fixed-point theory

We study the (monotone) linear complementarity problem in reflexive Banach space. The problem is treated as a quadratic program and shown to satisfy appropriate constraint qualifications. This leads to a theory of the generalized monotone linear complementarity problem which is independent of Brouwer's fixed-point theorem. Certain related results on linear systems are given. The final section concerns copositive operators.This research was partially supported by NSERC Grant No. A-5516.The author thanks the referee for his painstaking and thorough comments on this paper.     

Existence-Uniqueness Problems For Infinite Dimensional Stochastic Differential Equations With Delays

The main aim of this paper is to develop the basic theory of a class of infinite dimensional stochastic differential equations with delays (IDSDEs) under local Lipschitz conditions. Firstly, we establish a global existence-uniqueness theorem for the IDSDEs under the global Lipschitz condition in \(C\) without the linear growth condition. Secondly, the non-continuable solution for IDSDEs is given under the local Lipschitz condition in \(C\). Then, the classical Itô's formula is improved and a global existence theorem for IDSDEs is obtained. Our new theorems give better results while conditions imposed are much weaker than some existing results. For example, we need only the local Lipschitz condition in \(C\) but neither the linear growth condition nor the continuous condition on the time \(t\). Finally, two examples are provided to show the effectiveness of the theoretical results.     

Numerical validation of solutions of linear complementarity problems

Summary. This paper proposes a validation method for solutions of linear complementarity problems. The validation procedure consists of two sufficient conditions that can be tested on a digital computer. If the first condition is satisfied then a given multidimensional interval centered at an approximate solution of the problem is guaranteed to contain an exact solution. If the second condition is satisfied then the multidimensional interval is guaranteed to contain no exact solution. This study is based on the mean value theorem for absolutely continuous functions and the reformulation of linear complementarity problems as nonsmooth nonlinear systems of equations. Received August 21, 1997 / Revised version July 2, 1998     

Multiple solutions of semilinear degenerate elliptic boundary value problems

The purpose of this paper is to study a class of semilinear elliptic boundary value problems with degenerate boundary conditions which include as particular cases the Dirichlet problem and the Robin problem. The approach here is based on the super‐sub‐solution method in the degenerate case, and is distinguished by the extensive use of an L^p Schauder theory elaborated for second‐order, elliptic differential operators with discontinuous zero‐th order term. By using Schauder's fixed point theorem, we prove that the existence of an ordered pair of sub‐ and supersolutions of our problem implies the existence of a solution of the problem. The results extend an earlier theorem due to Kazdan and Warner to the degenerate case. © 2011 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim     

The theory of linear programming:skew symmetric self-dual problems and the central path *

The literature in the field of interior point methods for linear programming has been almost exclusively algorithm oriented. Recently Güler, Roos, Terlaky and Vial presented a complete duality theory for linear programming based on the interior point approach. In this paper we present a more simple approach which is based on an embedding of the primal problem and its dual into a skew symmetric self-dual problem. This embedding is essentially due Ye, Todd and Mizuno

First we consider a skew symmetric self-dual linear program. We show that the strong duality theorem trivally holds in this case. Then, using the logarithmic barrier problem and the central path, the existence of a strictly complementary optimal solution is proved. Using the embedding just described, we easily obtain the strong duality theorem and the existence of strictly complementary optimal solutions for general linear programming problems     

An iterative method for generalized nonlinear complementarity problems

An iterative method for solving generalized nonlinear complementarity problems (Ref. 1) involving stronglyK-copositive operators is introduced. Conditions are presented which guarantee the convergence of the method; in addition, the sequence of iterates is used to prove the existence of a solution to the problem under conditions not included in the previous study. Separate consideration is given to the generalized linear complementarity problem.This research was partially supported by National Science Foundation, Grant No. GP-16293. This paper constitutes part of the junior author's doctoral thesis written at Rensselaer Polytechnic Institute. Research support was provided by an NDEA Fellowship and an RPI Fellowship.     

Solution of the complex linear complementarity problem

In an earlier paper, it was shown that the linear and quadratic programming problems in complex space could be unified in the “complex linear complementarity problem” (complex LCP). An existence theory for this problem was provided. The present paper addresses the problem of actually solving the complex LCP and hence complex linear and quadratic programs as well. Two solution procedures are described and an example is given.     

解线性互补问题的预处理加速模Gauss-Seidel迭代方法

本文提出了解线性互补问题的预处理加速模系Gauss-Seidel迭代方法,当线性互补问题的系统矩阵是M-矩阵时证明了方法的收敛性,并给出了该预处理方法关于原方法的一个比较定理.数值实验显示该预处理迭代方法明显加速了原方法的收敛.     

Power iteration and inverse power iteration for eigenvalue complementarity problem

In this paper, an inverse complementarity power iteration method (ICPIM) for solving eigenvalue complementarity problems (EiCPs) is proposed. Previously, the complementarity power iteration method (CPIM) for solving EiCPs was designed based on the projection onto the convex cone K. In the new algorithm, a strongly monotone linear complementarity problem over the convex cone K is needed to be solved at each iteration. It is shown that, for the symmetric EiCPs, the CPIM can be interpreted as the well‐known conditional gradient method, which requires only linear optimization steps over a well‐suited domain. Moreover, the ICPIM is closely related to the successive quadratic programming (SQP) via renormalization of iterates. The global convergence of these two algorithms is established by defining two nonnegative merit functions with zero global minimum on the solution set of the symmetric EiCP. Finally, some numerical simulations are included to evaluate the efficiency of the proposed algorithms.     

Overlapping restricted additive Schwarz method applied to the linear complementarity problem with?an?H-matrix

In this paper, a restricted additive Schwarz method is introduced for solving the linear complementarity problem that involves an H ₊-matrix. We show that the sequence generated by the restricted additive Schwarz method converges to the unique solution of the problem without any restriction on the initial point. Moreover, the comparison theorem is given between different versions of the restricted additive Schwarz method by using the weighted max-norm. We also show that the restricted additive Schwarz method is much better than the corresponding additive Schwarz variants in terms of the iteration number and the execution time.