Finite-Dimensional Variational Inequalities and Complementarity Problems

by Pang, Jong-Shi; Facchinei, Francisco

• ISBN13: 9780387955803
• ISBN10: 0387955801
• Format: Hardcover
• Copyright: 2003-02-01
• Publisher: Springer Verlag

Summary

This comprehensive book presents a rigorous and state-of-the-art treatment of variational inequalities and complementarity problems in finite dimensions. This class of mathematical programming problems provides a powerful framework for the unified analysis and development of efficient solution algorithms for a wide range of equilibrium problems in economics, engineering, finance, and applied sciences. New research material and recent results, not otherwise easily accessible, are presented in a self-contained and consistent manner. The book is published in two volumes, with the first volume concentrating on the basic theory and the second on iterative algorithms. Both volumes contain abundant exercises and feature extensive bibliographies. Written with a wide range of readers in mind, including graduate students and researchers in applied mathematics, optimization, and operations research as well as computational economists and engineers, this book will be an enduring reference on the subject and provide the foundation for its sustained growth.

Table of Contents

Preface	v
Contents	xvii
Contents of Volume I	xxi
Acronyms	xxiii
Glossary of Notation	xxv
Numbering System	xxxiii
Local Methods for Nonsmooth Equations	625	(98)
Nonsmooth Analysis I: Clarke's Calculus	626	(12)
Basic Newton-type Methods	638	(25)
Piecewise smooth functions	656	(5)
Composite maps	661	(2)
A Newton Method for VIs	663	(11)
Nonsmooth Analysis II: Semismooth Functions	674	(18)
SC1 functions	686	(6)
Semismooth Newton Methods	692	(16)
Linear Newton approximation schemes	703	(5)
Exercises	708	(7)
Notes and Comments	715	(8)
Global Methods for Nonsmooth Equations	723	(70)
Path Search Algorithms	724	(12)
Dini Stationarity	736	(3)
Line Search Methods	739	(32)
Sequential convergence	753	(4)
Q-superlinear convergence	757	(7)
SC1 minimization	764	(2)
Application to a complementarity problem	766	(5)
Trust Region Methods	771	(15)
Exercise	786	(2)
Notes and Comments	788	(5)
Equation-Based Algorithms for CPs	793	(98)
Nonlinear Complementarity Problems	794	(58)
Algorithms based on the FB function	798	(11)
Pointwise FB regularity	809	(7)
Sequential FB regularity	816	(6)
Nonsingularity of Newton approximation	822	(4)
Boundedness of level sets	826	(7)
Some modifications	833	(6)
A trust region approach	839	(5)
Constrained methods	844	(8)
Global Algorithms Based on the min Function	852	(5)
More C-Functions	857	(8)
Extensions	865	(12)
Finite lower (or upper) bounds only	865	(1)
Mixed complementarity problems	866	(3)
Box constrained VIs	869	(8)
Exercises	877	(5)
Notes and Comments	882	(9)
Algorithms for VIs	891	(98)
KKT Conditions Based Methods	892	(20)
Using the FB function	892	(17)
Using the min function	909	(3)
Merit Functions for VIs	912	(18)
The regularized gap function	913	(8)
The linearized gap function	921	(9)
The D-Gap Merit Function	930	(17)
The implicit Lagrangian for the NCP	939	(8)
Merit Function Based Algorithms	947	(31)
Algorithms based on the D-gap function	947	(19)
The case of affine constraints	966	(3)
The case of a bounded K	969	(6)
Algorithms based on θc	975	(3)
Exercises	978	(3)
Notes and Comments	981	(8)
Interior and Smoothing Methods	989	(118)
Preliminary Discussion	991	(5)
The notion of centering	993	(3)
An Existence Theory	996	(7)
Applications to CEs	1000	(3)
A General Algorithmic Framework	1003	(9)
Assumptions on the potential function	1003	(3)
A potential reduction method for the CE	1006	(6)
Analysis of the Implicit MiCP	1012	(24)
The differentiable case	1016	(6)
The monotone case	1022	(9)
The KKT map	1031	(5)
IP Algorithms for the Implicit MiCP	1036	(17)
The NCP and KKT system	1043	(10)
The Ralph-Wright IP Approach	1053	(7)
Path-Following Noninterior Methods	1060	(12)
Smoothing Methods	1072	(20)
A Newton smoothing method	1078	(6)
A class of smoothing functions	1084	(8)
Exercises	1092	(5)
Notes and Comments	1097	(10)
Methods for Monotone Problems	1107
Projection Methods	1107	(18)
Basic fixed-point iteration	1108	(7)
Extragradient method	1115	(4)
Hyperplane projection method	1119	(6)
Tikhonov Regularization	1125	(10)
A regularization algorithm	1133	(2)
Proximal Point Methods	1135	(12)
Maximal monotone maps	1135	(6)
The proximal point algorithm	1141	(6)
Splitting Methods	1147	(17)
Douglas-Rachford splitting method	1147	(6)
Forward-backward splitting method	1153	(11)
Applications of Splitting Algorithms	1164	(12)
Projection algorithms revisited	1165	(6)
Applications of the Douglas-Rachford splitting	1171	(5)
Rate of Convergence Analysis	1176	(7)
Extragradient method	1178	(2)
Forward-backward splitting method	1180	(3)
Equation Reduction Methods	1183	(31)
Recession and conjugate functions	1184	(3)
Bregman-based methods	1187	(17)
Linearly constrained VIs	1204	(5)
Interior and exterior barrier methods	1209	(5)
Exercises	1214	(8)
Notes and Comments	1222
Bibliography for Volume II	1	(38)
Index of Definitions, Results, and Algorithms	39	(6)
Subject Index	45
Introduction	1	(124)
Problem Description	2	(6)
Relations Between Problem Classes	8	(4)
Integrability and the KKT System	12	(8)
Source Problems	20	(51)
Equivalent Formulations	71	(24)
Generalizations	95	(3)
Concluding Remarks	98	(1)
Exercises	98	(15)
Notes and Comments	113	(12)
Solution Analysis I	125	(118)
Degree Theory and Nonlinear Analysis	126	(19)
Existence Results	145	(9)
Monotonicity	154	(16)
Monotone CPs and AVIs	170	(15)
The VI (K, q, M) and Copositivity	185	(23)
Further Existence Results for CPs	208	(5)
A Frictional Contact Problem	213	(7)
Extended Problems	220	(6)
Exercises	226	(9)
Notes and Comments	235	(8)
Solution Analysis II	243	(96)
Bouligand Differentiable Functions	244	(8)
Constraint Qualifications	252	(14)
Local Uniqueness of Solutions	266	(23)
Nondegenerate Solutions	289	(3)
VIs on Cartesian Products	292	(17)
Connectedness of Solutions	309	(8)
Exercises	317	(13)
Notes and Comments	330	(9)
The Euclidean Projector and Piecewise Functions	339	(80)
Polyhedral Projection	340	(12)
Piecewise Affine Maps	352	(19)
Unique Solvability of AVIs	371	(5)
B-Differentiability under SBCQ	376	(8)
Piecewise Smoothness under CRCQ	384	(8)
Local Properties of PC1 Functions	392	(9)
Projection onto a Parametric Set	401	(6)
Exercises	407	(7)
Notes and Comments	414	(5)
Sensitivity and Stability	419	(112)
Sensitivity of an Isolated Solution	420	(7)
Solution Stability of B-Differentiable Equations	427	(18)
Solution Stability: The Case of a Fixed Set	445	(27)
Parametric Problems	472	(28)
Solution Set Stability	500	(16)
Exercises	516	(9)
Notes and Comments	525	(6)
Theory of Error Bounds	531
General Discussion	531	(8)
Pointwise and Local Error Bounds	539	(15)
Global Error Bounds for VIs/CPs	554	(21)
Monotone AVIs	575	(14)
Global Bounds via a Variational Principle	589	(7)
Analytic Problems	596	(4)
Identification of Active Constraints	600	(5)
Exact Penalization and Some Applications	605	(5)
Exercises	610	(6)
Notes and Comments	616
Bibliography for Volume I	1	(50)
Index of Definitions and Results	51	(6)
Subject Index	57