Pratical Method of Optimizayion

本书详细描述了最优化方法以及实际应用，方法很全，讲解很细致Practical methodsofOptimizationSecond editionR. FletcherDepartment of mathematicsUniversity of Dundee, Scotland, UKA Wiley-Interscience PublicationJOHN WIleY sonsChichester. New York. Brisbane. Toronto. SingaporeCopyright o 11987 by John Wiley Sons LtdReprinted March 1991Reprinted July 1993Reprinted January 1995Reprinted January 1996Reprinted January 1999Reprinted in paperback May 2000All rights reservedNo part of this book may be reproduced by any means,or transmitted or translated into a machine languagewithout the wrtten permission of the publisherLibrary of Congress Cataloging in Publication Data:Fletcher, R. (roger)Practical methods of optimization"A Wiley-Interscience publicationBibliography: pIncludes indexMathematical optimizationI. TitleQA4025F57198751587-8126ISBN0471915475Briash Library Cataloguing in Publication DataFletcher. RPractical methods of optimization2nd ed1. Mathematical optimizationI. Title5l5QA402.5IsBN0 471915475(cloth)isBN0 471 49463 1(paper)Printed and bound in Great Britain by Bookcraft( Bath)LtdContentsPrefaceTable of NotationX111PART 1 UNCONSTRAINED OPTIMIZATIONChapter 1 Introduction1. 1 History and applications1.2 Mathematical BackgroundQuestions for Chapter 1Chapter 2 Structure of Methods2.1 Conditions for Local minima2. 2 Ad hoc Methods22692.3 Useful Algorithmic Properties2.4 Quadratic Models242 5 Descent methods and stabilit262.6 Algorithms for the Line Search SubproblemQuestions for Chapter 2Chapter 3 Newton-like Methods30443. 1 Newtons Method3.2 Quasi-Newton Methods3.3 Invariance, Metrics and Variational Properties573.4 The broyden family623.5 Numerical Experiments3.6 Other Formulae72Questions for Chapter 374Chapter 4 Conjugate Direction Methods4.1 Conjugate Gradient Methods88Contents4.2 Direction Set Method sQuestions for Chapter 492Chapter 5 Restricted Step Methods955.1 A Prototype Algorithm955.2 Levenberg-Marquardt MethodsQuestions for Chapter 5108Chapter 6 Sums of Squares and nonlinear Equations.1106.1 Over-determined Systems1106.2 Well-determined Systems1196.3 No-derivative methodsQuestions for Chapter 6133PART 2 CONSTRAINED OPTIMIZATION137Chapter 7 Introduction1397.1 Preview1397.2 Elimination and Other Transformations144Questions for Chapter 7149Chapter 8 Linear Programming1508.1 Structure1508.2 The Simplex Method1538.3 Other LP Techniques1598.4 Feasible points for Linear constraints1628.5 Stable and Large-scale Linear Programming1688.7 Polynomial Time Algorithms8.6 Degeneracy177183Questions for Chapter 8188Chapter 9 The Theory of Constrained Optimization1959.1 Lagrange Multipliers1959.2 First Order Conditions9. 3 Second Order Conditions2079 4 Convexityy2139.5 Duality219Questions for Chapter 9224Chapter 10 Quadratic Programming10.1 Equality Constraints2210.2 Lagrangian Methods23610.3 Active Set Methods24010.4 Advanced Features245Contents10.5 Special QP Problems24710.6 Complementary Pivoting and other methods250Questions for Chapter 10255Chapter 11 General linearly Constrained Optimization25911. 1 Equality Constraints25911.2 Inequality Constraints26411.3 Zigzagging268Questions for Chapter 11275Chapter 12 Nonlinear Programming27712.1 Penalty and Barrier Functions27712.2 Multiplier Penalty Functions12. 3 The L, Exact Penalty Function29612.4 The Lagrange-Newton Method (sQp)30412.5 Nonlinear elimination and feasible direction Methods31712.6 Other Methods322Questions for Chapter 12325Chapter 13 Other Optimization Problems33113. 1 Integer Programming33113.2 Geometric Programming33913.3 Network Programming344Questions for Chapter 13354Chapter 14 Non-Smooth Optimization35714.1 Introduction35714.2 Optimality Conditions36414.3 Exact Penalty Functions37814.4 Algorithms38214.5 A Globally Convergent Prototype Algorithm39714.6 Constrained Non-Smooth Optimization402Questions for Chapter 14414References417Subject Index430PrefaceThe subject of optimization is a fascinating blend of heuristics and rigour, oftheory and experiment It can be studied as a branch of pure mathematics, yethas applications in almost every branch of science and technology. This bookaims to present those aspects of optimization methods which are currently offoremost importance in solving real life problems. I strongly believe that it isnot possible to do this without a background of practical experience into howmethods behave, and i have tried to keep practicality as my central themeThus basic methods are described in conjunction with those heuristics whichcan be valuable in making the methods perform more reliably and efficientlyIn fact I have gone so far as to present comparative numerical studies, to givethe feel for what is possible, and to show the importance(and difiiculty)ofassessing such evidence Yet one cannot exclude the role of theoretical studiesin optimization and the scientist will always be in a better position to usenumerical techniques effectively if he understands some of the basic theoreticalbackground. I have tried to present such theory as shows how methods arederived, or gives insight into how they perform, whilst avoiding theory fortheory's sakeSome people will approach this book looking for a suitable text for under-graduate and postgraduate classes. i have used this material (or a selectionfrom it)at both levels, in introductory engineering courses, in Honoursmathematics lectures, and in lecturing to M.Sc. and Ph.D. students. In anattempt to cater for this diversity, i have used a Jekyll and Hyde style in thebook, in which the more straightforward material is presented in simple termswhilst some of the more difficult theoretical material is nonetheless presentedrigorously, but can be avoided if need be. I have also tried to present workedexamples for most of the basic methods one observation of my own which Ipass on for what it is worth is that the students gain far more from a course ifthey can be provided with computer subroutines for a few of the standardmethods, with which they can perform simple experiments for themselves, tosee for example how badly the steepest descent method handles rosenbrock'sproblem, and so onIn addition to the worked examples, each chapter is terminated by a set ofquestions which aim to not only illustrate but also extend the material in thePrefacetext. Many of the questions I have used in tutorial classes or examinationpapers. The reader may find a calculator (and possibly a programmablecalculator) helpful in some cases. A few of the questions are taken from theDundee Numerical Analysis M.Sc. examination, and are open book questionsin the nature of a one day mini research pro jectThe second edition of the book com bines the material in volumes 1 and 2of the first edition. Thus unconstrained optimization is the subject of Part 1and covers the basic theoretical background and standard techniques such asline search methods, Newton and quasi-Newton methods and conjugatedirection methods. a feature not common in the literature is a comprehensivetreatment of restricted step or trust region methods, which have very strongtheoretical properties and are now preferred in a number of situations. Thevery important field of nonlinear equations and nonlinear least squares(fordata fitting applications is also treated thoroughly. Part 2 covers constrainedoptimization which overall has a greater degree of complexity on account ofthe presence of the constraints. I have covered the theory of constrainedoptimization in a general(albeit standard) way, looking at the effect of first andsecond order perturbations at the solution. Some books prefer to emphasizethe part played by convex analysis and duality in optimization problems. I alsodescribe these features(in what I hope is a straightforward way)but give themlesser priority on account of their lack of generalityMost finite dimensional problems of a continuous nature have been includedin the book but i have generally kept away from problems of a discrete orcombinatorial nature since they have an entirely different character and thechoice of method can be very specialized. In this case the nearest thing to ageneral purpose method is the branch and bound method, and since this is atransformation to a sequence of continuous problems of the type covered inthis volume, I have included a straightforward description of the techniqueA feature of this book which i think is lacking in the literature is a treatmentofnon-differentiable optimization which is reasona bly comprehensive and coversboth theoretical and practical aspects adequately. i hope that the final chaptermeets this need. The sub ject of geometric programming is also included in thebook because I think that it is potentially valuable, and again I hope that thistreatment will turn out to be more straightforward and appealing than othersin the literature. The subject of nonlinear programming is covered in somedetail but there are difficulties in that this is a very active rescarch area. tosome extent therefore the presentation mirrors my assessment and prejudice asto 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 theirmerits and demerits. Linear constraint programming, on the other hand, is nowwell developed and here the difficulty is that there are two distinct points ofview. One is the traditional approach in which algorithms are presented asgeneralizations of early linear programming methods which carry out pivotingin a tableau. The other is a more recent approach in terms of active set strategies:PrefaceI regard this as more intuitive and flexible and have therefore emphasized italthough both methods are presented and their relationship is exploredThis second edition has given me the opportunity to improve the presentationof some parts of the book and to introduce new developments and a certainamount of new material. In Part 1 the description of line searches is improvedand some new results are included. The variational properties of the BFGS andDFP methods are now described in some detail. More simple proofs of theproperties of trust region methods are given. Recent developments in hybridmethods for nonlinear least squares are described a thorough treatment of theDennis-More theorem characterizing superlinear con vergence in nonlinearsystems is given and its significance is discussed. In part 2 the treatment oflinear programming has been extended considerably and includes new methodsfor stable updating of LU factors and the reliable treatment of degeneracy. also,important recent developments in polynomial time algorithms are describedand discussed, including ellipsoid algorithms and Karmarkar's method. Thetreatment of quadratic programming now includes a description of range spaceand dual active set methods. For general linear constraint programming somenew theorems are given, including convergence proofs for a trust region methodThe chapter on nonlinear programming now includes an extra section givinga direct treatment of the Li exact penalty function not requiring any convexanalysis. New developments in sequential quadratic programming(SQP)aredescribed particularly for the case that only the reduced Hessian matrix is usedA completely new section on network programming is given relating numericallinear algebraic and graph theoretic concepts and showing their application invarious types of optimization problem For non-smooth optimization Os bornesconcept of structure functionals is used to unify the treatment of regularity forsecond order conditions and to show the equivalence to nonlinear programming.It is also used to demonstrate the second order convergence of a non-smoothSQP algorithm. The Maratos effect and the use of second order correctionsare described. Finally a new section giving optimality conditions for constrainedcomposite non-smooth optimization is included a considerable number of newexercises is also givenIt is a great pleasure to me to acknowledge those many people who haveinfluenced my thinking and contributed to my often inadequate knowledgeAmongst many I must single out the assistance and encouragement given tome by Professor M. J D. Powell, my former colleague at AERE Harwell, andone whose contributions to the sub ject are unsurpassed i am also indebted toProfessor A R. Mitchell and other members of the University of Dundee forproviding the stimulating and yet relaxed environment in which this book wasprepared. I also wish to thank Professor D S Jones for his interest andencouragement in publishing the book and drs m.P. Jackson, G.A. Watsonand r s. womersley for their constructive advice on the contents. I gratefullacknowledge those various people who have taken the trouble to write orotherwise inform me of errors, misconceptions, etc, in text. whilst this new