Finite-Dimensional Variational Inequalities and Complementarity Problems

by Facchinei, Francisco; Pang, Jong-Shi

• ISBN13: 9780387955810
• ISBN10: 038795581X
• 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.

Author Biography

 Jong-Shi Pang was awarded the 2003 Dantzig Prize, the worlds top prize in the area of Mathematical Programming.

Table of Contents

Preface	v
Contents	xvii
Contents of Volume II	xxi
Acronyms	xxiii
Glossary of Notation	xxv
Numbering System	xxxiii
Introduction	1	(124)
Problem Description	2	(6)
Affine problems	7	(1)
Relations Between Problem Classes	8	(4)
Integrability and the KKT System	12	(8)
Constrained optimization problems	13	(5)
The Karush-Kuhn-Tucker system	18	(2)
Source Problems	20	(51)
Saddle problems	21	(3)
Nash equilibrium problems	24	(2)
Nash-Cournot production/distribution	26	(10)
Economic equilibrium problems	36	(5)
Traffic equilibrium models	41	(5)
Frictional contact problems	46	(5)
Elastoplastic structural analysis	51	(4)
Nonlinear obstacle problems	55	(3)
Pricing American options	58	(7)
Optimization with equilibrium constraints	65	(2)
CPs in SPSD matrices	67	(4)
Equivalent Formulations	71	(24)
Equation reformulations of the NCP	71	(5)
Equation reformulations of the VI	76	(11)
Merit functions	87	(8)
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)
Degree theory	126	(8)
Global and local homeomorphisms	134	(4)
Elementary set-valued analysis	138	(3)
Fixed-point theorems	141	(2)
Contractive mappings	143	(2)
Existence Results	145	(9)
Applications to source problems	150	(4)
Monotonicity	154	(16)
Plus properties and F-uniqueness	162	(4)
The dual gap function	166	(2)
Boundedness of solutions	168	(2)
Monotone CPs and AVIs	170	(15)
Properties of cones	171	(4)
Existence results	175	(5)
Polyhedrality of the solution set	180	(5)
The VI (K, q, M) and Copositivity	185	(23)
The CP (K, q, M)	192	(7)
The AVI (K, q, M)	199	(3)
Solvability in terms of feasibility	202	(6)
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)
The critical cone	267	(4)
Conditions for local uniqueness	271	(8)
Local uniqueness in terms of KKT triples	279	(4)
Local uniqueness theory in NLP	283	(4)
A nonsmooth-equation approach	287	(2)
Nondegenerate Solutions	289	(3)
VIs on Cartesian Products	292	(17)
Semicopositive matrices	294	(4)
P properties	298	(11)
Connectedness of Solutions	309	(8)
Weakly univalent functions	310	(7)
Exercises	317	(13)
Notes and Comments	330	(9)
The Euclidean Projector and Piecewise Functions	339	(80)
Polyhedral Projection	340	(12)
The normal manifold	345	(7)
Piecewise Affine Maps	352	(19)
Coherent orientation	356	(15)
Unique Solvability of AVIs	371	(5)
Inverse of MKnor	374	(2)
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)
Characterizations in terms of the B-derivative	439	(4)
Extensions to locally Lipschitz functions	443	(2)
Solution Stability: The Case of a Fixed Set	445	(27)
The case of a finitely representable set	452	(10)
The NCP and the KKT system	462	(7)
Strong stability under CRCQ	469	(3)
Parametric Problems	472	(28)
Directional differentiability	482	(7)
The strong coherent orientation condition	489	(7)
PC1 multipliers and more on SCOC	496	(4)
Solution Set Stability	500	(16)
Semistability	503	(6)
Solvability of perturbed problems and stability	509	(3)
Partitioned VIs with P0 pairs	512	(4)
Exercises	516	(9)
Notes and Comments	525	(6)
Theory of Error Bounds	531
General Discussion	531	(8)
Pointwise and Local Error Bounds	539	(15)
Semistability and error bounds	539	(5)
Local error bounds for KKT triples	544	(4)
Linearly constrained monotone composite VIs	548	(6)
Global Error Bounds for VIs/CPs	554	(21)
Without Lipschitz continuity	557	(7)
Affine problems	564	(11)
Monotone AVIs	575	(14)
Convex quadratic programs	586	(3)
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
Local Methods for Nonsmooth Equations	625	(98)
Nonsmooth Analysis I: Clarke's Calculus	626	(12)
Basic Newton-type Methods	638	(25)
A Newton Method for VIs	663	(11)
Nonsmooth Analysis II: Semismooth Functions	674	(18)
Semismooth Newton Methods	692	(16)
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)
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)
Global Algorithms Based on the min Function	852	(5)
More C-Functions	857	(8)
Extensions	865	(12)
Exercises	877	(5)
Notes and Comments	882	(9)
Algorithms for VIs	891	(98)
KKT Conditions Based Methods	892	(20)
Merit Functions for VIs	912	(18)
The D-Gap Merit Function	930	(17)
Merit Function Based Algorithms	947	(31)
Exercises	978	(3)
Notes and Comments	981	(8)
Interior and Smoothing Methods	989	(118)
Preliminary Discussion	991	(5)
An Existence Theory	996	(7)
A General Algorithmic Framework	1003	(9)
Analysis of the Implicit MiCP	1012	(24)
IP Algorithms for the Implicit MiCP	1036	(17)
The Ralph-Wright IP Approach	1053	(7)
Path-Following Noninterior Methods	1060	(12)
Smoothing Methods	1072	(20)
Excercises	1092	(5)
Notes and Comments	1097	(10)
Methods for Monotone Problems	1107
Projection Methods	1107	(18)
Tikhonov Regularization	1125	(10)
Proximal Point Methods	1135	(12)
Splitting Methods	1147	(17)
Applications of Splitting Algorithms	1164	(12)
Rate of Convergence Analysis	1176	(7)
Equation Reduction Methods	1183	(31)
Exercises	1214	(8)
Notes and Comments	1222
Bibliography for Volume II	1	(38)
Index of Definitions, Results, and Algorithms	39	(6)
Subject Index	45