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.     

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.     

Functions Without Exceptional Family of Elements and Complementarity Problems

In Ref. 1, Isac, Bulavski, and Kalashnikov introduced the concept of exceptional family of elements for a continuous function f: R ⁿR ⁿ. It is known that, if there does not exist an exceptional family of elements for f, then the corresponding complementarity problem has a solution. In this paper, we show that several classes of nonlinear functions, known in complementarity theory or other domains, are functions without exceptional family of elements and consequently the corresponding complementarity problem is solvable. It is evident that the notion of exceptional family of elements provides an alternative way of determining whether or not the complementarity problem has a solution.     

Optimality for (<Emphasis Type="Italic">h,φ</Emphasis>)-multiobjective programming involving generalized type-I functions

Based upon Ben-Tal’s generalized algebraic operations, new classes of functions, namely (h,φ)-type-I, quasi (h,φ)-type-I, and pseudo (h,φ)-type-I, are defined for a multi-objective programming problem. Sufficient optimality conditions are obtained for a feasible solution to be a Pareto efficient solution for this problem. Some duality results are established by utilizing the above defined classes of functions, considering the concept of a Pareto efficient solution. This research is supported by National Science Foundation of China under Grant No. 69972036.     

Simplicial approximation of solutions to the nonlinear complementarity problem with lower and upper bounds

Ideas of a simplicial variable dimension restart algorithm to approximate zero points onR ⁿ developed by the authors and of a linear complementarity problem pivoting algorithm are combined to an algorithm for solving the nonlinear complementarity problem with lower and upper bounds. The algorithm can be considered as a modification of the2n-ray zero point finding algorithm onR ⁿ . It appears that for the new algorithm the number of linear programming pivot steps is typically less than for the2n-ray algorithm applied to an equivalent zero point problem. This is caused by the fact that the algorithm utilizes the complementarity conditions on the variables. This work is part of the VF-program “Equilibrium and Disequilibrium in Demand and Supply,” which has been approved by the Netherlands Ministry of Education and Sciences.     

Exceptional Family of Elements for a Variational Inequality Problem and its Applications

This paper introduces a new concept of exceptional family of elements (abbreviated, exceptional family) for a finite-dimensional nonlinear variational inequality problem. By using this new concept, we establish a general sufficient condition for the existence of a solution to the problem. Such a condition is used to develop several new existence theorems. Among other things, a sufficient and necessary condition for the solvability of pseudo-monotone variational inequality problem is proved. The notion of coercivity of a function and related classical existence theorems for variational inequality are also generalized. Finally, a solution condition for a class of nonlinear complementarity problems with so-called P _* -mappings is also obtained.     

Classes of functions and feasibility conditions in nonlinear complementarity problems

Given a mappingF from real Euclideann-space into itself, we investigate the connection between various known classes of functions and the nonlinear complementarity problem: Find anx ^* such thatFx ^* ? 0 andx ^* ? 0 are orthogonal. In particular, we study the extent to which the existence of au ? 0 withFu ? 0 (feasible point) implies the existence of a solution to the nonlinear complementarity problem, and extend, to nonlinear mappings, known results in the linear complementarity problem on P-matrices, diagonally dominant matrices with non-negative diagonal elements, matrices with off-diagonal non-positive entries, and positive semidefinite matrices.     

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.     

New Constrained Optimization Reformulation of Complementarity Problems

We suggest a reformulation of the complementarity problem CP(F) as a minimization problem with nonnegativity constraints. This reformulation is based on a particular unconstrained minimization reformulation of CP(F) introduced by Geiger and Kanzow as well as Facchinei and Soares. This allows us to use nonnegativity constraints for all the variables or only a subset of the variables on which the function F depends. Appropriate regularity conditions ensure that a stationary point of the new reformulation is a solution of the complementarity problem. In particular, stationary points with negative components can be avoided in contrast to the reformulation as unconstrained minimization problem. This advantage will be demonstrated for a class of complementarity problems which arise when the Karush–Kuhn–Tucker conditions of a convex inequality constrained optimization problem are considered.     

<Emphasis FontCategory="NonProportional">L</Emphasis>-Matrices and solvability of linear complementarity problems by a linear program-Matrices and solvability of linear complementarity problems by a linear program

The classes ofL ₁-matrices,L ₂-matrices,L ₃-matrices andW-matrices are introduced to study solvability of a linear complementarity problem via solving a linear program. Three sufficient conditions are presented to guarantee that a linear complementarity problem is solvable via a linear program. The new sufficient conditions are weaker than the ones introduced by Mangasarian. This fact is also illustrated by an example. Partially supported by NSFC. This author is also with College of Business Administration of Human University as a Lotus chair professor.     

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 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.     

GAUSSIAN PIVOTING METHOD FORSOLVING LINEAR COMPLEMENTARITY PROBLEM

In this paper, a new direct algorithm for solving linear complementarity problem with Z-matrix is proposed. The algorithm exhibits either a solution or its nonexistence after at most n steps (where n is the dimension of the problem) and the computational complexity is at most 1/3n^2 O(n^2)     

Growth Behavior of Two Classes of Merit Functions for Symmetric Cone Complementarity Problems

In the solution methods of the symmetric cone complementarity problem (SCCP), the squared norm of a complementarity function serves naturally as a merit function for the problem itself or the equivalent system of equations reformulation. In this paper, we study the growth behavior of two classes of such merit functions, which are induced by the smooth EP complementarity functions and the smooth implicit Lagrangian complementarity function, respectively. We show that, for the linear symmetric cone complementarity problem (SCLCP), both the EP merit functions and the implicit Lagrangian merit function are coercive if the underlying linear transformation has the P-property; for the general SCCP, the EP merit functions are coercive only if the underlying mapping has the uniform Jordan P-property, whereas the coerciveness of the implicit Lagrangian merit function requires an additional condition for the mapping, for example, the Lipschitz continuity or the assumption as in (45). The authors would like to thank the two anonymous referees for their helpful comments which improved the presentation of this paper greatly. The research of J.-S. Chen was partially supported by National Science Council of Taiwan.     

Solution of nonsymmetric linear complementarity problems by iterative methods

Convergence is established for iterative algorithms for the solution of the nonsymmetric linear complementarity problem of findingz such thatMz+q0,z0,z ^T(Mz+q)=0, whereM is a givenn×n real matrix, not necessarily symmeetric, andq is a givenn-vector. It is first shown that, if the spectral radius of a matrix related toM is less than one, then the iterates generated by the general algorithm converge to a solution of the linear complementarity problem. It turns out that convergence properties are quite similar to those of linear systems of equations. As specific cases, two important classes of matrices, Minkowski matrices and quasi-dominant diagonal matrices, are shown to satisfy this convergence condition.The author is grateful to Professor O. L. Mangasarian and the referees for their substantive suggestions and corrections.     

Generalized -complementarity problems in Banach spaces

In this paper, a class of generalized f-complementarity problems and three classes of variational inequalities are introduced in real Banach spaces, and the equivalences among them are established under certain conditions. Several coercivity conditions are introduced for the existence of solutions of the generalized f-complementarity problem. Under some suitable assumptions, it is shown that each of these coercivity conditions is equivalent to the nonemptyness and boundedness of the solution set for the generalized f-complementarity problem in infinite-dimensional Banach spaces, and even the nonemptyness and compactness of the solution set for the generalized f-complementarity problem in finite-dimensional spaces. The existence of least elements for the feasible set of the generalized f-complementarity problem is also presented under suitable conditions.     

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.     

The linear ordering problem: Instances,search space analysis and algorithms

The linear ordering problem is an NP-hard problem that arises in a variety of applications. Due to its interest in practice, it has received considerable attention and a variety of algorithmic approaches to its solution have been proposed. In this paper we give a detailed search space analysis of available benchmark instance classes that have been used in various researches. The large fitness-distance correlations observed for many of these instances suggest that adaptive restart algorithms like iterated local search or memetic algorithms, which iteratively generate new starting solutions for a local search based on previous search experience, are promising candidates for obtaining high performing algorithms. We therefore experimentally compared two such algorithms and the final experimental results suggest that, in particular, the memetic algorithm is a new state-of-the-art approach to the linear ordering problem.     

On the Local Uniqueness of Solutions of Variational Inequalities Under H-Differentiability

In this paper, we give some sufficient conditions for the local uniqueness of solutions to nonsmooth variational inequalities where the underlying functions are H-differentiable and the underlying set is a closed convex set/polyhedral set/box/polyhedral cone. We show how the solution of a linearized variational inequality is related to the solution of the variational inequality. These results extend/unify various similar results proved for C ¹ and locally Lipschitzian variational inequality problems. When specialized to the nonlinear complementarity problem, our results extend/unify those of C ² and C ¹ nonlinear complementarity problems.     

On sufficiency and duality in multiobjective programming problem under generalized <Emphasis Type="Italic">α</Emphasis>-type I univexity

In this paper, we are concerned with the multiobjective programming problem with inequality constraints. We introduce new classes of generalized α-univex type I vector valued functions. A number of Kuhn–Tucker type sufficient optimality conditions are obtained for a feasible solution to be an efficient solution. The Mond–Weir type duality results are also presented.