Nonlinear Programming and Variational Inequality Problems A Unified
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
- PDF / 36,701,350 Bytes
- 343 Pages / 439.37 x 666.142 pts Page_size
- 33 Downloads / 224 Views
Applied Optimization Volume 23
Series Editors: Panos M. Pardalos University of Florida, U.S.A. Donald Hearn University of Florida, U.SA.
The titles published in this series are listed at the end of this volume.
Nonlinear Programming and Variational Inequality Problems A Unified Approach
by
Michael Patriksson Chalmers University of Technology, Gothenburg, Sweden
Springer-Science+Business Media, B.V.
A C.I.P. Catalogue record for this book is available from the Library of Congress.
Printed on acid-free paper
All Rights Reserved ISBN 978-1-4419-4806-9 ISBN 978-1-4757-2991-7 (eBook) DOl 10.1007/978-1-4757-2991-7 DOI Sof'tcover reprint of the hardcover 1st edition 1999 © 1999 Springer Science+Business Media Dordrecht Originally published by Kluwer Academic Publishers 'in 1999.
No part of the material protected by this copyright notice may be reproduced or utilized in any form or by any means, electronic or mechanical, including photocopying, recording or by any information storage and retrieval system, without written permission from the copyright owner
To you; you know who
Contents Preface Notation 1 Introduction 1.1 The variational inequality problem 1.1.1 Instances of the problem. . 1.1.2 Example applications . . . 1.2 The cost approximation algorithm 1.2.1 The subproblem phase. 1.2.2 The updating phase 1.2.3 Discussion. 1.3 Scope and preview 1.3.1 Preview 1.3.2 Scope . . .
xi
xiii 1 1
2 8 13 13 20
22 26 26 36
2 Technical preliminaries 2.1 Solutions to the variational inequality problem 2.2 Solutions to the CA subproblem . . . . . . 2.3 A posteriori error bounds and lower bounds 2.4 Descent properties 2.5 Step length rules . . . . . . . . . . . . . . .
39
3 Instances of the cost approximation algorithm 3.1 Classic algorithms . . . . . . . . 3.1.1 Linearization methods . . . . . . . 3.1.2 Interior point algorithms . . . . . . 3.1.3 Jacobi and Gauss-Seidel methods 3.2 Regularization and proximal point methods 3.2.1 Regularization methods . . . . 3.2.2 Splitting methods . . . . . . . 3.3 Decomposition-coordination methods 3.3.1 A primal algorithm . . . . 3.3.2 A primal-dual algorithm. . . .
57 57 57 59
39
40 42
44 49
60 61 61 71
77 78 79
Nonlinear Programming and Variational Inequality Problems
viii
3.4 3.5 3.6
3.7 3.8
3.3.3 An augmented Lagrangean method. Decomposition of optimization problems . . Relationships among algorithm frameworks CA algorithms involving u . . . . 3.6.1 Sub gradient algorithms . 3.6.2 Perturbed CA algorithms Continuous CA algorithms. A final remark . . . . . . . . . .
80 81 83 87 87 88 90
92
4
Merit functions for variational inequality problems 95 4.1 Introduction....................... 95 4.2 A class of merit functions for variational inequalities 96 4.3 Properties of the merit function 'ljJ . . . . 99 4.4 Instances of the merit function 'ljJ . . . . . • 104 . 104 4.4.1 The primal and dual gap functions 4.4.2 Some differentiable merit functions 106 4.4.3 Unconstrained and complementarity formulations. 107 4.4.4 Merit functions for variational inequality p
