Complementarity problems.

*(English)*Zbl 0795.90072
Lecture Notes in Mathematics. 1528. Berlin: Springer-Verlag. vi, 297 p. (1992).

Given a mapping \(f: R^ n_ +\to R^ n\), the problem of finding an \(x\in R^ n_ +\) such that \(f(x)\in R^ n_ +\) and \(x^ T f(x)= 0\) is called the complementarity problem. The importance of the complementarity problem lies in the fact that its form is fairly general in the sense that several problems in different fields such as mathematical programming, game theory, mechanics, engineering, economics, fixed point theory, etc. can, by appropriate choice of \(f\), be so posed. Special instances of the complementarity problem can be found in the mathematical literature as early as 1940, but the problem received little attention until the mid 1960’s at which time it became an object of study on its own right. Dorn’s paper [W. S. Dorn, SIAM J. Appl. Math. 9, 51-54 (1961; Zbl 0104.144)] was the first step in treating the complementarity problem as an independent problem. Since then the theory of the complementarity problem has known a strong and ascending development. During the past three decades (1961-1991), a number of important results have been established dealing with both the computational and theoretical (uniqueness and existence) aspects of the above problem as well as of its linear form, called the linear complementarity problem [see R. W. Cottle, J. S. Pang and R. E. Stone, ‘The linear complementarity problem’ (1992; Zbl 0757.90078)]. In many of the works, attempts have been made to apply existence theorems of the complementarity problem to solve problems in other fields.

The study of the complementarity problem entered into a new phase when S. Karamardian [Math. Programming 2, 107-129 (1972; Zbl 0247.90058)] and B. C. Eaves [Math. Programming 1, 68-75 (1971; Zbl 0227.90044)] showed that the complementarity problem is closely related to two other problems: the solution of variational inequalities and the determination of the fixed point for a given map. Thus, just like in mathematical programming, the existence theorems and the methods used in the study of the last two problems are widely used in Complementarity Theory and conversely, the ideas and the methods developed specially for complementarity problems are used to solve variational inequalities or to solve fixed point problems.

Various extensions and generalizations of the above complementarity problem have also been studied. These include the generalized complementarity problem (when the nonnegative orthant \(R^ n_ +\) is replaced by a closed convex cone), the multivalued complementarity problem (when \(F\) is a multivalued map), the parametric complementarity problem (when \(x\) is a function of a parameter), the implicit complementarity problem, and complementarity problems in abstract spaces (when \(R^ n\) is replaced by either a Banach space, or a Hilbert space, or a Hausdorff topological vector space or a topological vector lattice).

Books were published on linear and nonlinear complementarity problems in finite-dimensional spaces. The present book is probably the first one on complementarity problems in infinite-dimensional spaces. It is the principal aim of the author to present all principal mathematical aspects about the complementarity problems in its various forms in infinite- dimensional spaces. But he has not completely neglected the finite- dimensional case and presents several important results about the linear or the nonlinear complementarity problems specifically obtained for this case.

In Chapter 1 the definitions of the principal complementarity problems which are discussed in detail in subsequent chapters, are given. The entire class of complementarity problems is divided into two subclasses: the Topological Complementarity Problem and the Order Complementarity Problem. The topological complementarity problem includes the generalized complementarity problem [S. Karamardian, J. Optimization Theory Appl. 8, 161-168 (1971; Zbl 0218.90052)], the generalized multivalued complementarity problems [see, e.g., R. Saigal, Math. Oper. Res. 1, 260-266 (1976; Zbl 0363.90091)], the parametric complementarity problem and the implicit complementarity problem. The order complementarity problem which is defined over a vector lattice [see, e.g., J. M. Borwein and M. A. H. Dempster, Math. Oper. Res. 14, No. 3, 534-558 (1989; Zbl 0694.90094)] is of recent development and has not received much attention.

In Chapter 2, the author gives an exhaustive list of examples of problems from other fields such as mathematical programming, game theory, mechanics, economics etc., which have as mathematical model a specific complementarity problem. Many interesting applications are described and through this, a reader will have a good insight into the wide applicability of the theory of the complementarity problem.

Chapter 3 is devoted to the study of the important mathematical problems such as variational inequalities over a locally convex space, the least element problem [R. W. Cottle and J. S. Pang, Math. Oper. Res. 3, 155-170 (1978; Zbl 0385.90077)] etc. which are equivalent to the complementarity problem. This study helps in obtaining many new methods to solve complementarity problems.

In Chapter 4, the author considers the general complementarity problem defined over a cone domain in different settings such as the finite- dimensional Euclidean space \(R^ n\), Hilbert spaces, Banach spaces and locally convex spaces. The existence and uniqueness of a solution to this problem is examined and some remarkable properties of the solution set are investigated.

The order complementarity problem is studied in Chapter 5 and the implicit complementarity problem is discussed in Chapter 6. Since these two problems are mathematically not easily tractable, much literature does not exist over these two problems. The author has tried his best to include whatever material available at his disposal and presented many new results, thus paving the way for further research on these topics.

In Chapter 7, the author introduces the concept of isotone projection cone in a Hilbert space and applies this notion to study the generalized complementarity problem in a Hilbert space ordered by an isotone projection cone. This is a completely new approach in the complementarity theory and an attractive area for further research.

The author presents in Chapter 8, the last and the longest chapter of the book, several topics which are not considered in previous chapters and can be hopefully developed in future research. Among these, some important topics are: (a) the extension and use of the notion of the stationary point (given a convex set \(C\) in \(R^ n\), and a map \(f: C\to R^ n\), a point \(x\in C\) is called a stationary point of the pair \((f,C)\) if \((v- x)^ T f(x)\geq 0\) for all \(v\in C\)) for solving general multivalued complementarity problems, (b) the multivalued order complementarity problem, (c) the use of alternative theorems for variational inequalities [see J. M. Borwein, Lect. Notes Econ. Math. Systems 259, 194-203 (1985; Zbl 0591.90088)] to obtain new existence theorems for the complementarity problem, and (d) the vector complementarity problem [see G. Chen and X. Yang, J. Math. Anal. Appl. 153, No. 1, 136-158 (1990; Zbl 0712.90083)].

This book is not a text book but a lecture note on various aspects of the celebrated complementarity problem, and can be considered as an outstanding addition to the literature of the Complementarity Theory. The broad field of the complementarity problem is now enormous. No book could possibly contain all of the important aspects. Except for numerical methods the present note covers all principal features. A lot of new material is presented. The author is an authority in the subject matter and reports on the state of the art. There is a thorough bibliography containing over 400 references to the literature. The book is clearly written and well arranged. The style is readable and stimulating. It will serve the purpose of a good reference book for those already sincerely interested in the subject.

The study of the complementarity problem entered into a new phase when S. Karamardian [Math. Programming 2, 107-129 (1972; Zbl 0247.90058)] and B. C. Eaves [Math. Programming 1, 68-75 (1971; Zbl 0227.90044)] showed that the complementarity problem is closely related to two other problems: the solution of variational inequalities and the determination of the fixed point for a given map. Thus, just like in mathematical programming, the existence theorems and the methods used in the study of the last two problems are widely used in Complementarity Theory and conversely, the ideas and the methods developed specially for complementarity problems are used to solve variational inequalities or to solve fixed point problems.

Various extensions and generalizations of the above complementarity problem have also been studied. These include the generalized complementarity problem (when the nonnegative orthant \(R^ n_ +\) is replaced by a closed convex cone), the multivalued complementarity problem (when \(F\) is a multivalued map), the parametric complementarity problem (when \(x\) is a function of a parameter), the implicit complementarity problem, and complementarity problems in abstract spaces (when \(R^ n\) is replaced by either a Banach space, or a Hilbert space, or a Hausdorff topological vector space or a topological vector lattice).

Books were published on linear and nonlinear complementarity problems in finite-dimensional spaces. The present book is probably the first one on complementarity problems in infinite-dimensional spaces. It is the principal aim of the author to present all principal mathematical aspects about the complementarity problems in its various forms in infinite- dimensional spaces. But he has not completely neglected the finite- dimensional case and presents several important results about the linear or the nonlinear complementarity problems specifically obtained for this case.

In Chapter 1 the definitions of the principal complementarity problems which are discussed in detail in subsequent chapters, are given. The entire class of complementarity problems is divided into two subclasses: the Topological Complementarity Problem and the Order Complementarity Problem. The topological complementarity problem includes the generalized complementarity problem [S. Karamardian, J. Optimization Theory Appl. 8, 161-168 (1971; Zbl 0218.90052)], the generalized multivalued complementarity problems [see, e.g., R. Saigal, Math. Oper. Res. 1, 260-266 (1976; Zbl 0363.90091)], the parametric complementarity problem and the implicit complementarity problem. The order complementarity problem which is defined over a vector lattice [see, e.g., J. M. Borwein and M. A. H. Dempster, Math. Oper. Res. 14, No. 3, 534-558 (1989; Zbl 0694.90094)] is of recent development and has not received much attention.

In Chapter 2, the author gives an exhaustive list of examples of problems from other fields such as mathematical programming, game theory, mechanics, economics etc., which have as mathematical model a specific complementarity problem. Many interesting applications are described and through this, a reader will have a good insight into the wide applicability of the theory of the complementarity problem.

Chapter 3 is devoted to the study of the important mathematical problems such as variational inequalities over a locally convex space, the least element problem [R. W. Cottle and J. S. Pang, Math. Oper. Res. 3, 155-170 (1978; Zbl 0385.90077)] etc. which are equivalent to the complementarity problem. This study helps in obtaining many new methods to solve complementarity problems.

In Chapter 4, the author considers the general complementarity problem defined over a cone domain in different settings such as the finite- dimensional Euclidean space \(R^ n\), Hilbert spaces, Banach spaces and locally convex spaces. The existence and uniqueness of a solution to this problem is examined and some remarkable properties of the solution set are investigated.

The order complementarity problem is studied in Chapter 5 and the implicit complementarity problem is discussed in Chapter 6. Since these two problems are mathematically not easily tractable, much literature does not exist over these two problems. The author has tried his best to include whatever material available at his disposal and presented many new results, thus paving the way for further research on these topics.

In Chapter 7, the author introduces the concept of isotone projection cone in a Hilbert space and applies this notion to study the generalized complementarity problem in a Hilbert space ordered by an isotone projection cone. This is a completely new approach in the complementarity theory and an attractive area for further research.

The author presents in Chapter 8, the last and the longest chapter of the book, several topics which are not considered in previous chapters and can be hopefully developed in future research. Among these, some important topics are: (a) the extension and use of the notion of the stationary point (given a convex set \(C\) in \(R^ n\), and a map \(f: C\to R^ n\), a point \(x\in C\) is called a stationary point of the pair \((f,C)\) if \((v- x)^ T f(x)\geq 0\) for all \(v\in C\)) for solving general multivalued complementarity problems, (b) the multivalued order complementarity problem, (c) the use of alternative theorems for variational inequalities [see J. M. Borwein, Lect. Notes Econ. Math. Systems 259, 194-203 (1985; Zbl 0591.90088)] to obtain new existence theorems for the complementarity problem, and (d) the vector complementarity problem [see G. Chen and X. Yang, J. Math. Anal. Appl. 153, No. 1, 136-158 (1990; Zbl 0712.90083)].

This book is not a text book but a lecture note on various aspects of the celebrated complementarity problem, and can be considered as an outstanding addition to the literature of the Complementarity Theory. The broad field of the complementarity problem is now enormous. No book could possibly contain all of the important aspects. Except for numerical methods the present note covers all principal features. A lot of new material is presented. The author is an authority in the subject matter and reports on the state of the art. There is a thorough bibliography containing over 400 references to the literature. The book is clearly written and well arranged. The style is readable and stimulating. It will serve the purpose of a good reference book for those already sincerely interested in the subject.

Reviewer: J.Parida (Rourkela)

##### MSC:

90C33 | Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) |

90C20 | Quadratic programming |

90-02 | Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming |

90C48 | Programming in abstract spaces |

47H10 | Fixed-point theorems |

49-02 | Research exposition (monographs, survey articles) pertaining to calculus of variations and optimal control |

74K99 | Thin bodies, structures |

49J40 | Variational inequalities |