I am pleased to announce that the book The Traffic Assignment Problem: Models and Methods by Michael Patriksson was published in November 1998. PUBLISHING INFORMATION: Publisher: Kluwer Academic Publishers, Dordrecht, The Netherlands Home page: http://www.wkap.nl Series: Applied Optimization, vol 23 ISBN: 0-7923-5455-9 (bound) List price: USD 168 PREFACE: Since I started working in the area of nonlinear programming and, later on, variational inequality problems, I have frequently been surprised to find that many algorithms, however scattered in numerous journals, monographs and books, and described rather differently, are closely related to each other. This book is meant to help the reader understand and relate algorithms to each other in some intuitive fashion, and represents, in this respect, a consolidation of the field. The framework of algorithms presented in this book is called Cost Approximation. (The preface of the Ph.D. thesis [Pat93d] explains the background to the work that lead to the thesis, and ultimately to this book.) It describes, for a given formulation of a variational inequality or nonlinear programming problem, an algorithm by means of approximating mappings and problems, a principle for the update of the iteration points, and a merit function which guides and monitors the convergence of the algorithm. One purpose of this book is to offer this framework as an intuitively appealing tool for describing an algorithm. One of the advantages of the framework, or any reasonable framework for that matter, is that two algorithms may be easily related and compared through its use. This framework is particular in that it covers a vast number of methods, while still being fairly detailed; the level of abstraction is in fact the same as that of the original problem statement. Another purpose of the book is to provide a convergence analysis of the algorithms in the framework. The analysis is performed under different interesting combinations of choices of implementation and under different combinations of assumptions on the problem being solved and the algorithm devised for it. The analysis compares favourably with previous attempts to describe algorithms for nonlinear programs and variational inequality problems in a common framework, and establishes the convergence both of new versions of existing algorithms and of methods previously unpublished. A fairly detailed, and to a large degree non-technical, summary of the contents of the book can be found in Section 1.3. This book can be used in postgraduate courses in nonlinear optimization. If the focus is on algorithm theory, then the prerequisites to (or the first parts of) such a course should cover the fundamental theory of convex analysis (recommended: Rockafellar [Roc70a] or Hiriart-Urruty and Lemaréchal [HiL93a]) and nonlinear optimization (recommended: Bazaraa et al. [BSS93] or Bertsekas [Ber95]). In this case, a course focusing on Chapters 1-4, 7 and the first two sections of Chapter 9 covers some of the fundamentals of nonlinear optimization and variational inequality problems, with emphasis on the theoretical properties of them in association with the construction of algorithms. A course oriented more towards the numerical aspects of large-scale nonlinear optimization can be based on this book, then requiring a background in numerical analysis and computing (recommended: Bertsekas and Tsitsiklis [BeT89]). In this case, a course would concentrate mostly on Chapters 5-6, 8, and 9, which include convergence analyses and adaptations of algorithms to problems whose forms typically are found in large-scale settings. With over 800 references, the book also serves as a reference source for algorithms for the solution of nonlinear optimization and variational inequality problems. CONTENTS: Preface xi Notation xiii 1 Introduction 1 2 Technical preliminaries 39 3 Instances of the cost approximation algorithm 57 4 Merit functions for variational inequality problems 95 5 Convergence of the CA algorithm for nonlinear programs 135 6 Convergence of the CA algorithm for variational inequality problems 169 7 Finite identification of active constraints and solutions 191 8 Parallel and sequential decomposition CA algorithms 211 9 A column generation/simplicial decomposition algorithm 253 A Definitions 277 References 283 Index 325 For more information, please contact: Michael Patriksson Department of Mathematics Chalmers University of Technology S-412 96 Gothenburg SWEDEN Email: mipat@math.chalmers.se Home page: http://www.math.chalmers.se/~mipat Fax: +46 31 161973 Phone: +46 31 7723529