Practical Methods of Optimization.2nd.ed Fletcher R

【实例简介】
Fletcher R。 Practical Methods of Optimization.2nd.ed
Practical methods O Optimization Second edition R. Fletcher Department of Mathematics University of dundee, Scotland, UK A Wiley-Interscience Publication JOHn WileY sons Chichester. New York. Brisbane. Toronto. Singapore Copyright o 11987 by John Wiley Sons Ltd Reprinted March 1991 Reprinted july 1993 Reprinted January 1995 Reprinted January 1996 Reprinted January 1999 Reprinted in paperback May 2000 All rights reserved No part of this book may be reproduced by any means, or transmitted, or translated into a machine language without the wrtten permission of the publisher Library of Congress Cataloging in Publication Data: Fletcher, R.(Roger) Practical methods of optimization A wiley-Interscience publication Bibliography: p Includes index Mathematical optimization I. Title QA4025F5719871587-8126 ISBN0471915475 British Library Cataloguing in Publication Data: Fletcher. R. Practical methods of optimization 2nd ed 1. Mathematical optimization Tit. 515 QA4025 ISBN 0 471 5(cloth) isBn0 471 49463 1 (paper) Printed and bound in Great Britain by Bookcraft(Bath)Ltd Contents Preface Table of notation X111 part 1 UNCONSTRAINED OPTIMIZATION Chapter 1 Introduction 1. 1 History and Applications 1.2 Mathematical Background 336 Questions for Chapter 1 Chapter 2 Structure of Methods 2.1 Conditions for Local minima 2.2 Ad hoc Methods 16 2.3 Useful Algorithmic Properties 2.4 Quadratic Models 24 2: 5 Descent Methods and stability 26 2.6 Algorithms for the Line Search Subproblem 33 Questions for Chapter 2 Chapter 3 Newton-like Methods 444 3. 1 Newton's Method 3.2 Quasi-Newton Methods 49 3.3 Invariance, Metrics and Variational Properties 3.4 The Broyden Family 3.5 Numerical Experiments 3. 6 Other Formulae Questions for Chapter 3 Chapter 4 Conjugate Direction Methods 80 4.1 Conjugate Gradient Methods Contents 4.2 Direction Set Methods Questions for Chapter 4 Chapter 5 Restricted Step Methods 5.1 A Prototype algorithm 5.2 Levenberg-Marquardt Methods Questions for Chapter 5 10 Chapter 6 Sums of Squares and Nonlinear Equations 110 6.1 Over-determined Systems 6.2 Well-determined Systems 119 6.3 No-derivative Methods 129 Questions for Chapter 6 133 PART 2 CONSTRAINED OPTIMIZATION 137 Chapter 7 Introduction 139 7.1 Preview 139 7. 2 Elimination and Other Transformations 144 Questions for Chapter 7 149 Chapter 8 Linear Programming 150 8.1 Structure 150 8.2 The Simplex method 153 8.3 Other Lp Techniques 159 8.4 Feasible Points for Linear Constraints 162 8.5 Stable and Large-scale Linear Programming 168 8.6 Degeneracy 177 8.7 Polynomial Time Algorithms 183 Questions for Chapter 8 188 Chapter 9 The Theory of Constrained Optimization 195 9.1 agrange Mul plers 195 9.2 First Order conditions 201 9.3 Second Order Conditions 20′ 9.4 Convexity 213 9.5 Duality 219 Questions for Chapter 9 224 Chapter 10 Quadratic Programming 10.1 Equality Constraints 10.2 Lagrangian Methods 236 10.3 Active Set Methods 240 10.4 Advanced Features 245 Contents 10.5 Special QP Problems 247 10.6 Complementary Pivoting and Other Methods 250 Questions for Chapter 10 255 Chapter 11 General linearly Constrained optimization 259 11.1 Equality Constraints 259 11. 2 Inequality Constraints 264 11.3 Zigzagging 268 Questions for Chapter 11 275 Chapter 12 Nonlinear Programming 277 12. 1 Penalty and barrier functions 277 12.2 Multiplier Penalty Functions 287 12. 3 The L Exact Penalty Function 296 12. 4 The Lagrange-Newton Method (SQP 304 12.5 Nonlinear Elimination and Feasible Direction Methods 317 12.6 Other Methods 322 Questions for Chapter 12 325 Chapter 13 other Optimization problems 331 13.1 Integer Programming 331 13.2 Geometric Programming 339 13.3 Network Programming 344 Questions for Chapter 13 354 Chapter 14 Non-Smooth optimization 357 14.1 Introduction 357 14.2 Optimality conditions 364 14.3 Exact Penalty Functions 378 14.4 Algorithms 382 14.5 A Globally Convergent Prototype Algorithm. 397 14.6 Constrained Non-Smooth optimization 402 Questions for Chapter 14 414 References 417 Subject Index 430 Preface The subject of optimization is a fascinating blend of heuristics and rigour, of theory and experiment. It can be studied as a branch of pure mathematics, yet has applications in almost every branch of science and technology. This book aims to present those aspects of optimization methods which are currently of foremost importance in solving real life problems. I strongly believe that it is not possible to do this without a background of practical experience into how methods behave, and I have tried to keep practicality as my central theme Thus basic methods are described in conjunction with those heuristics which can be valuable in making the methods perform more reliably and efficiently In fact I have gone so far as to present comparative numerical studies, to give the feel for what is possible, and to show the importance(and difficulty) of assessing such evidence. Yet one cannot exclude the role of theoretical studies in optimization, and the scientist will always be in a better position to use numerical techniques effectively if he understands some of the basic theoretical background. I have tried to present such theory as shows how methods are derived, or gives insight into how they perform, whilst avoiding theory for the leory's sake Some people will approach this book looking for a suitable text for under- graduate and postgraduate classes. I have used this material (or a selection from it)at both levels, in introductory engineering courses, in Honours mathematics lectures, and in lecturing to M.Sc. and Ph D. students. In an attempt to cater for this diversity, I have used a Jekyll and Hyde style in the book, in which the more straightforward material is presented in simple terms, whilst some of the more difficult theoretical material is nonetheless presented rigorously, but can be avoided if need be. I have also tried to present worked examples for most of the basic methods. One observation of my own which I pass on for what it is worth is that the students gain far more from a course if they can be provided with computer subroutines for a few of the standard methods, with which they can perform simple experiments for themselves, to see for example how badly the steepest descent method handles rosenbrock's problem, and so on In addition to the worked examples each chapter is terminated by a set of questions which aim to not only illustrate but also extend the material in the P eface text. Many of the questions I have used in tutorial classes or examination papers. The reader may find a calculator (and possibly a programmable calculator) helpful in some cases. A few of the questions are taken from the Dundee Numerical Analysis M.Sc. examination, and are open book questions in the nature of a one day mini research project The second edition of the book combines the material in Volumes 1 and 2 of the first edition Thus unconstrained optimization is the subject of Part 1 and covers the basic theoretical background and standard techniques such as line search methods, Newton and quasi-Newton methods and conjugate direction methods. a feature not common in the literature is a comprehensive treatment of restricted step or trust region methods, which have very strong theoretical properties and are now preferred in a number of situations. The very important field of nonlinear equations and nonlinear least squares ( for data fitting applications) is also treated thoroughly. Part 2 covers constrained optimization which overall has a greater degree of complexity on account of the presence of the constraints. I have covered the theory of constrained optimization in a general (albeit standard)way, looking at the effect of first and second order perturbations at the solution. Some books prefer to emphasize the part played by convex analysis and duality in optimization problems. I also describe these features(in what I hope is a straightforward way) but give them lesser priority on account of their lack of generality Most finite dimensional problems of a continuous nature have been included in the book but I have generally kept away from problems of a discrete or combinatorial nature since they have an entirely different character and the choice of method can be very specialized. In this case the nearest thing to a general purpose method is the branch and bound method, and since this is a transformation to a sequence of continuous problems of the type covered in this volume, i have included a straightforward description of the technique. A feature of this book which i think is lacking in the literature is a treatment of non-differentiable optimization which is reasonably comprehensive and covers both theoretical and practical aspects adequately. i hope that the final chapter meets this need. The subject of geometric programming is also included in the book because I think that it is potentially valuable, and again I hope that this treatment will turn out to be more straightforward and appealing than others in the literature. The subject of nonlinear programming is covered in some detail but there are difficulties in that this is a very active rescarch area. to some extent therefore the presentation mirrors my assessment and prejudice as o how things will turn out, in the absence of a generally agreed point of view. However, I have also tried to present various alternative approaches and their merits and demerits. Linear constraint programming, on the other hand, is now well developed and here the difficulty is that there are two distinct points of view. One is the traditional approach in which algorithms are presented as generalizations of early linear programming methods which carry out pivoting in a tableau. The other is a more recent approach in terms of active set strategies 【实例截图】
【核心代码】