Finite-dimensional variational inequalities and complementarity problems. Vol. I. (English) Zbl 1062.90001

Springer Series in Operations Research. New York, NY: Springer (ISBN 0-387-95580-1/hbk). xxxiii, 624 p., I1-I69 p. (2003).
This is a joint review for Vols. I and II (see Zbl 1062.90002 below). Divided into two volumes, the book contains twelve main chapters, followed by an extensive bibliography, a summary of main results and key algorithms, and a subject index. The first volume consists of the first six chapters, which present the basic theory of variational inequalities (VIs) and complementarity problems (CPs). The second volume consists of the remaining six chapters, which present algorithms of various kinds for solving VIs and CPs. Besides the main text, each chapter contains (a) an extensive set of exercises, many of which are drawn from published papers that supplement the material in the text, and (b) a set of notes and comments that document historical accounts, give the sources for the results in the main text, and provide discussions and references on related topics and extensions. The bibliography contains more than 1.300 publications in the literature up to June 2002. This bibliography serves two purposes: one purpose is to find the source of the results in the chapters, wherever applicable: the other purpose is to find a documentation of papers written on the VI/CP and related topics.
Due to its comprehensiveness, each chapter of the book is by itself quite lengthy. Among the first six sections in Chapter 1. Sections 1.1, 1.2, 1.3, and 1.5 make up the basic introduction to the VI/CP. The source problems in Section 1.4 are of very diverse nature; they fall into several general categories: mathematical programming, economics, engineering and finance. Depending on an individual’s background, a reader can safely skip those subsections that are outside his/her interests; for instance, an economist can omit the subsection on frictional contact problems, a contact mechanist can omit the subsection on Nash-Cournot production models. Section 1.6 mainly gives the definition of several extended problems: except for (1.6.1), which is re-introduced and employed in Chapter 11, this section can be omitted at first reading.
Chapters 2 and 3 contain the basic theory of existence and multiplicity of solutions. Several sections contain review materials of well-known topics; these are included for the benefit of those readers who are unfamiliar with the background for the theory. Section 2.1 contains the review of degree theory, which is a basic mathematical tool that we employ throughout the book; due to its powerful implications, we recommend this to a reader who is interested in the theoretical part of the subject. Section 2.2, 2.3 (except Subsection 2.3.2), 2.4 and 2.5, (except Subsection 2.5.3) contain fundamental results. While Sections 2.6 and 2.8 can be skipped at first reading, Section 2.7 contains very specialized results for the discrete frictional contact problem and is included herein only to illustrate the application of the theory developed in the chapter to an important class of mechanical problems.
Section 3.1 in Chapter 3 introduces the class of B-differentiable functions that plays a fundamental role throughout the book. With the exception of the nonstandard SBCQ. Section 3.2 is a review of various well-known CQs in NLP. Except for the last two subsections in Section 3.3 and Subsection 3.51, which may be omitted at first reading, the remainder of this chapter contains important properties of solutions to the VI/CP.
Chapter 4 serves two purposes: One, it is a technical precursor to the next chapter; and two, it introduces the important classes of PA functions (Section 4.2) and \(\text{PC}^1\) functions (Section 4.6). Readers who are not interested in the sensitivity and stability theory of the VI/CP can skip most of this and the next chapter. Nevertheless, in order to appreciate the class of semismooth functions, which lies at the heart of the contemporary algorithms for solving VIs/CPs, and the regularity conditions, which are key to the convergence of these algorithms, the reader is advised to become familiar with certain developments in this chapter, such as the basic notion of coherent orientation of PA maps (Definition 4.2.3) and its matrix theoretic characterizations for the special maps \(\text{M}_{\text{K}}^{\text{nor}}\) and \(\text{M}_{\text{K}}^{\text{nat}}\) (Proposition 4.2.7) as well as the fundamental role of this notion in the globally unique solvability of AVIs (Theorem 4.3.2). The inverse function Theorem 4.6.5 for \(\text{PC}^1\) functions is of fundamental importance in nonsmooth analysis. Subsections 4.1.1 and 4.3.1 are interesting in their own right; but they are not needed in the remainder of the book.
Chapter 5 focuses on the single topic of sensitivity and stability of the VI/CP. While stability is the cornerstone to the fast convergence of Newton’s method, readers who are not interested in this specialized topic or in the advanced convergence theory of the mentioned method can skip this entire chapter. Notwithstanding this suggestion, Section 5.3 is of classical importance and contains the most basic results concerning the local analysis of an isolated solution.
Chapter 6 contains another significant yet specialized topic that can be omitted at first reading. From a computational point of view, an important goal of this chapter is to establish a sound basis for understanding the connection between the exact solutions to a given problem and the computed solutions of iterative methods under prescribed termination criteria used in practical implementation. As evidenced throughout the chapter and also in Section 12.6, the theory of error bounds has far-reaching consequences that extend beyond this goal. In Section 6.7, error bounds in designing algorithms that can identify active constraints accurately are studied resulting in enhanced theoretical properties of algorithms and holding promise for superior computational efficiency.
Of independent interest, Chapters 7 and 8 contain the preparatory materials for the two subsequent chapters. While Sections 7.1 and 7.4 are both concerned with the fundamentals of nonsmooth functions, the former pertains to general properties of nonsmooth functions, whereas the latter focuses on the semismooth functions. As far as specific algorithms go, Algorithms 7.3.1 and 7.5.1 in Sections 7.3 and 7.5 respectively, are the most basic and strongly recommended for anyone interested in the subsequent developments. The convergence of the former algorithm depends on the (strong) stability theory in Chapter 5, whereas that of the latter is rather simple, provided that one has a good understanding of semismoothness. In contrast to the previous two algorithms, Algorithm 7.2.17 is closest to a straightforward application of the classical Newton method for smooth systems of equations to the NCP.
The path search Newton method 8.1.9 is the earliest algorithm to be coded in the highly successful PATH computer software. Readers who are already familiar with the line search and/or trust region methods in standard nonlinear programming may wish to peruse Subsection 8.3.3 and skip the rest of Chapter 8 in order to proceed directly to the next chapter. When specialized to \(C^1\) optimization problems, as is the focus in Chapter 9 and 10 much of ihe material in Sections 8.3 and 8.4 is classical: these two sections basically offer a systematic treatment of known techniques and results and present them in a way that accommodates nonsmooth objective functions.
The last four chapters are the core of the algorithmic part of this book. While Chapter 9 focuses on the NCP, Chapter 10 is devoted to the VI. The first section of the former chapter presents a detailed exposition of algorithms based on the FB merit function and their convergence theory. The most basic algorithm, 9.1.10, is described in Subsection 9.1.1 and is accompanied by a comprehensive analysis. Algorithm 9.2.3, which combines the min function and the FB merit function in a line search method, is representative of a mixture of algorithms in one overall scheme. Example 9.3.3 contains several C-functions that can be used in place of the FB C-function. The box-constrained VI in Subsection 9.4.3 unifies the generalized problems in Section 9.4.
The development in Section 10.1 is very similar to that in Section 9.1.1; the only difference is that the analysis of the first section in Chapter 10 is tailored to the KKT system of a finitely representable VI. The other major development in this chapter is the D-gap function in Section 10.3, which is preceded by the preparatory discussion of the regularized gap function in Subsection 10.2.1. The implicit Lagrangian function presented in Subsection 10.3.1 is an important merit function for the NCP.
Chapter 11 presents interior and smoothing methods for solving CPs of different kinds, including KKT systems. Developed in the abstract setting of constrained equations, the basic interior point method for the implicit MiCP, Algorithm 11.5.1, is presented in Section 11.5. An extensive theoretical study of the latter problem is the subject of the previous Section 11.4: in which the important mixed \(P_0\) property is introduced (see Definition 11.4.1). A Newton smoothing method is outlined in Subsection 11.8.1; this method is applicable to smoothed reformulations of CPs using the smoothing functions discussed in Subsection 11.8.2, particularly those in Example 11.8.11.
The twelfth and last chapter discusses various specialized methods that are applicable principally to (pseudo) monotone VIs and NCPs of the \(P_0\) type. The first four sections of the chapter contain the basic methods and their convergence theories. The theory of maximal monotone operators in Subsection 12.3.1 plays a central role in the proximal point method that is the subject of Subsection 12.3.2. Bregman-based methods in Subsection 12.7.2 are well researched in the literature, whereas the interior barrier methods in Subsection 12.7.4 are recent entrants to the field.
The book is written very well and is an important contribution to the fields of VIs and CPs.


90-01 Introductory exposition (textbooks, tutorial papers, etc.) pertaining to operations research and mathematical programming
90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
65K05 Numerical mathematical programming methods
47J20 Variational and other types of inequalities involving nonlinear operators (general)


Zbl 1062.90002


Full Text: DOI