Finite-Dimensional Variational Inequalities and Complementarity Problems Volume 2

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. Preface......Page 6 Contents......Page 18 Contents of Volume I......Page 22 Acronyms......Page 24 Glossary of Notation......Page 26 Numbering System......Page 34 7 Local Methods for Nonsmooth Equations......Page 36 7.1 Nonsmooth Analysis I: Clarke’s Calculus......Page 37 7.2 Basic Newton-type Methods......Page 49 7.2.1 Piecewise smooth functions......Page 67 7.2.2 Composite maps......Page 72 7.3 A Newton Method for VIs......Page 74 7.4 Nonsmooth Analysis II: Semismooth Functions......Page 85 7.4.1 SC[sup(1)] functions......Page 97 7.5 Semismooth Newton Methods......Page 103 7.5.1 Linear Newton approximation schemes......Page 114 7.6 Exercises......Page 119 7.7 Notes and Comments......Page 126 8 Global Methods for Nonsmooth Equations......Page 134 8.1 Path Search Algorithms......Page 135 8.2 Dini Stationarity......Page 147 8.3 Line Search Methods......Page 150 8.3.1 Sequential convergence......Page 164 8.3.2 Q-superlinear convergence......Page 168 8.3.3 SC[sup(1)] minimization......Page 175 8.3.4 Application to a complementarity problem......Page 177 8.4 Trust Region Methods......Page 182 8.5 Exercise......Page 197 8.6 Notes and Comments......Page 199 9 Equation-Based Algorithms for CPs......Page 204 9.1 Nonlinear Complementarity Problems......Page 205 9.1.1 Algorithms based on the FB function......Page 209 9.1.2 Pointwise FB regularity......Page 220 9.1.3 Sequential FB regularity......Page 227 9.1.4 Nonsingularity of Newton approximation......Page 233 9.1.5 Boundedness of level sets......Page 237 9.1.6 Some modifications......Page 244 9.1.7 A trust region approach......Page 250 9.1.8 Constrained methods......Page 255 9.2 Global Algorithms Based on the min Function......Page 263 9.3 More C-Functions......Page 268 9.4.1 Finite lower (or upper) bounds only......Page 276 9.4.2 Mixed complementarity problems......Page 277 9.4.3 Box constrained VIs......Page 280 9.5 Exercises......Page 288 9.6 Notes and Comments......Page 293 10 Algorithms for VIs......Page 302 10.1.1 Using the FB function......Page 303 10.1.2 Using the min function......Page 320 10.2 Merit Functions for VIs......Page 323 10.2.1 The regularized gap function......Page 324 10.2.2 The linearized gap function......Page 332 10.3 The D-Gap Merit Function......Page 341 10.3.1 The implicit Lagrangian for the NCP......Page 350 10.4.1 Algorithms based on the D-gap function......Page 358 10.4.2 The case of affine constraints......Page 377 10.4.3 The case of a bounded K......Page 380 10.4.4 Algorithms based on θ[sub(c)]......Page 386 10.5 Exercises......Page 389 10.6 Notes and Comments......Page 392 11 Interior and Smoothing Methods......Page 400 11.1 Preliminary Discussion......Page 402 11.1.1 The notion of centering......Page 404 11.2 An Existence Theory......Page 407 11.2.1 Applications to CEs......Page 411 11.3.1 Assumptions on the potential function......Page 414 11.3.2 A potential reduction method for the CE......Page 417 11.4 Analysis of the Implicit MiCP......Page 423 11.4.1 The differentiable case......Page 427 11.4.2 The monotone case......Page 433 11.4.3 The KKT map......Page 442 11.5 IP Algorithms for the Implicit MiCP......Page 447 11.5.1 The NCP and KKT system......Page 454 11.6 The Ralph-Wright IP Approach......Page 464 11.7 Path-Following Noninterior Methods......Page 471 11.8 Smoothing Methods......Page 483 11.8.1 A Newton smoothing method......Page 489 11.8.2 A class of smoothing functions......Page 495 11.9 Excercises......Page 503 11.10 Notes and Comments......Page 508 12.1 Projection Methods......Page 518 12.1.1 Basic fixed-point iteration......Page 519 12.1.2 Extragradient method......Page 526 12.1.3 Hyperplane projection method......Page 530 12.2 Tikhonov Regularization......Page 536 12.2.1 A regularization algorithm......Page 544 12.3.1 Maximal monotone maps......Page 546 12.3.2 The proximal point algorithm......Page 552 12.4.1 Douglas-Rachford splitting method......Page 558 12.4.2 Forward-backward splitting method......Page 564 12.5 Applications of Splitting Algorithms......Page 575 12.5.1 Projection algorithms revisited......Page 576 12.5.2 Applications of the Douglas-Rachford splitting......Page 582 12.6 Rate of Convergence Analysis......Page 587 12.6.1 Extragradient method......Page 589 12.6.2 Forward-backward splitting method......Page 591 12.7 Equation Reduction Methods......Page 594 12.7.1 Recession and conjugate functions......Page 595 12.7.2 Bregman-based methods......Page 598 12.7.3 Linearly constrained VIs......Page 615 12.7.4 Interior and exterior barrier methods......Page 620 12.8 Exercises......Page 625 12.9 Notes and Comments......Page 633 Bibliography for Volume II......Page 646 Index of Definitions, Results, and Algorithms......Page 684 C......Page 690 E......Page 692 F......Page 693 I......Page 694 L......Page 695 M......Page 696 N......Page 697 P......Page 698 S......Page 699 V......Page 701 Z......Page 702 The?nite-dimensional nonlinear complementarity problem (NCP) is a s- tem of?nitely many nonlinear inequalities in?nitely many nonnegative variables along with a special equation that expresses the complementary relationship between the variables and corresponding inequalities. This complementarity condition is the key feature distinguishing the NCP from a general inequality system, lies at the heart of all constrained optimi- tion problems in?nite dimensions, provides a powerful framework for the modeling of equilibria of many kinds, and exhibits a natural link between smooth and nonsmooth mathematics. The?nite-dimensional variational inequality (VI), which is a generalization of the NCP, provides a broad unifying setting for the study of optimization and equilibrium problems and serves as the main computational framework for the practical solution of a host of continuum problems in the mathematical sciences. The systematic study of the?nite-dimensional NCP and VI began in the mid-1960s; in a span of four decades, the subject has developed into a very fruitful discipline in the?eld of mathematical programming. The - velopments include a rich mathematical theory, a host of e?ective solution algorithms, a multitude of interesting connections to numerous disciplines, and a wide range of important applications in engineering and economics. As a result of their broad associations, the literature of the VI/CP has bene?ted from contributions made by mathematicians (pure, applied, and computational), computer scientists, engineers of many kinds (civil, ch- ical, electrical, mechanical, and systems), and economists of diverse exp- tise (agricultural, computational, energy,?nancial, and spatial). This two volume work presents a comprehensive treatment of the finite dimensional variational inequality and complementarity problem, covering the basic theory, iterative algorithms, and important applications. The authors provide a broad coverage of the finite dimensional variational inequality and complementarity problem beginning with the fundamental questions of existence and uniqueness of solutions, presenting the latest algorithms and results, extending into selected neighboring topics, summarizing many classical source problems, and suggesting novel application domains. This first volume contains the basic theory of finite dimensional variational inequalities and complementarity problems. This book should appeal to mathematicians, economists, and engineers working in the field. A set price of EUR 199 is offered for volume I and II bought at the same time. Please order at: orders@springer.de This is the first of two chapters in which we develop numerical methods for the solution of systems of nonsmooth equations of the form G(x) = 0. (7.0.1) where G :  \symbol\ IRn  IRn is locally Lipschitz on the open set .