2

Engineering Optimization: Theory and Practice, Fourth Edition

830 Pages · 2009 · 4.53 MB · English

  • Engineering Optimization: Theory and Practice, Fourth Edition

    Engineering Optimization


    Engineering Optimization: Theory and Practice, FouSritnhg iEredsuit Sio. Rnao


    Copyright © 2009 by John Wiley & Sons, Inc. Engineering Optimization


    Theory and Practice


    Fourth Edition


    Singiresu S. Rao


    JOHN WILEY & SONS, INC. Thisbookisprintedonacid-freepaper.


    Copyright(cid:2)c 2009byJohnWiley&Sons,Inc.Allrightsreserved


    PublishedbyJohnWiley&Sons,Inc.,Hoboken,NewJersey


    PublishedsimultaneouslyinCanada


    Nopartofthispublication maybe reproduced,stored inaretrievalsystem,or transmittedinanyformor


    byanymeans,electronic,mechanical,photocopying,recording,scanning,orotherwise,exceptaspermitted


    underSection107or108ofthe1976UnitedStatesCopyrightAct,withouteitherthepriorwrittenpermission


    ofthePublisher,orauthorizationthroughpaymentoftheappropriateper-copyfeetotheCopyrightClearance


    Center, 222 Rosewood Drive,Danvers, MA 01923, (978) 750–8400, fax(978) 646–8600, or on the web


    at www.copyright.com. Requests to the Publisher for permission should be addressed to the Permissions


    Department, John Wiley & Sons, Inc., 111 River Street, Hoboken, NJ 07030, (201) 748–6011, fax (201)


    748–6008,oronlineatwww.wiley.com/go/permissions.


    LimitofLiability/DisclaimerofWarranty:Whilethepublisherandtheauthorhaveusedtheirbesteffortsin


    preparingthisbook,theymakenorepresentationsorwarrantieswithrespecttotheaccuracyorcompleteness


    of the contents of this book and specifically disclaim any implied warranties of merchantability or fitness


    foraparticularpurpose.Nowarrantymaybecreatedorextendedbysalesrepresentativesorwrittensales


    materials. The advice and strategies contained herein may not be suitable for your situation. You should


    consultwithaprofessionalwhereappropriate.Neitherthepublishernortheauthorshallbeliableforanyloss


    of profitor any other commercialdamages, including but notlimitedto special,incidental, consequential,


    orotherdamages.


    Forgeneralinformationaboutourotherproductsandservices,pleasecontactourCustomerCareDepartment


    within the United States at (800) 762–2974, outside the United States at (317) 572–3993 or fax (317)


    572–4002.


    Wiley also publishes its books in a variety of electronic formats. Some content that appears in print may


    not be available in electronic books. For more information about Wiley products, visit our web site at


    www.wiley.com.


    LibraryofCongressCataloging-in-PublicationData:


    Rao,S.S.


    Engineeringoptimization:theoryandpractice/SingiresuS.Rao.–4thed.


    p.cm.


    Includesindex.


    ISBN978-0-470-18352-6(cloth)


    1. Engineering—Mathematicalmodels.2. Mathematicaloptimization.I.Title.


    TA342.R362009


    620.001′5196—dc22


    2009018559


    PrintedintheUnitedStatesofAmerica


    10987654321 Contents


    Preface xvii


    1 Introduction to Optimization 1


    1.1 Introduction 1


    1.2 Historical Development 3


    1.3 Engineering Applicationsof Optimization 5


    1.4 Statement of an Optimization Problem 6


    1.4.1 Design Vector 6


    1.4.2 Design Constraints 7


    1.4.3 Constraint Surface 8


    1.4.4 ObjectiveFunction 9


    1.4.5 ObjectiveFunction Surfaces 9


    1.5 Classification of Optimization Problems 14


    1.5.1 Classification Based on the Existenceof Constraints 14


    1.5.2 Classification Based on the Nature of the Design Variables 15


    1.5.3 Classification Based on the Physical Structure of the Problem 16


    1.5.4 Classification Based on the Nature of the EquationsInvolved 19


    1.5.5 Classification Based on the Permissible Values of theDesign Variables 28


    1.5.6 Classification Based on the DeterministicNature of the Variables 29


    1.5.7 Classification Based on the Separability of the Functions 30


    1.5.8 Classification Based on the Number of Objective Functions 32


    1.6 Optimization Techniques 35


    1.7 Engineering Optimization Literature 35


    1.8 Solution of Optimization Problems Using MATLAB 36


    References and Bibliography 39


    Review Questions 45


    Problems 46


    2 Classical Optimization Techniques 63


    2.1 Introduction 63


    2.2 Single-Variable Optimization 63


    2.3 MultivariableOptimizationwith No Constraints 68


    2.3.1 Semidefinite Case 73


    2.3.2 Saddle Point 73


    2.4 MultivariableOptimizationwith EqualityConstraints 75


    2.4.1 Solution by Direct Substitution 76


    2.4.2 Solution by the Method of Constrained Variation 77


    2.4.3 Solution by the Method of Lagrange Multipliers 85


    vii viii Contents


    2.5 MultivariableOptimization with Inequality Constraints 93


    2.5.1 Kuhn–TuckerConditions 98


    2.5.2 Constraint Qualification 98


    2.6 Convex Programming Problem 104


    References and Bibliography 105


    Review Questions 105


    Problems 106


    3 Linear Programming I: Simplex Method 119


    3.1 Introduction 119


    3.2 Applicationsof Linear Programming 120


    3.3 Standard Form of a Linear Programming Problem 122


    3.4 Geometry of Linear Programming Problems 124


    3.5 Definitionsand Theorems 127


    3.6 Solutionof a System of Linear Simultaneous Equations 133


    3.7 Pivotal Reduction of a General System of Equations 135


    3.8 Motivationof theSimplex Method 138


    3.9 Simplex Algorithm 139


    3.9.1 Identifying an Optimal Point 140


    3.9.2 Improving a Nonoptimal Basic Feasible Solution 141


    3.10 Two Phases of the Simplex Method 150


    3.11 MATLABSolution of LP Problems 156


    References and Bibliography 158


    Review Questions 158


    Problems 160


    4 Linear Programming II:Additional Topics and Extensions 177


    4.1 Introduction 177


    4.2 Revised Simplex Method 177


    4.3 Dualityin Linear Programming 192


    4.3.1 Symmetric Primal–Dual Relations 192


    4.3.2 General Primal–Dual Relations 193


    4.3.3 Primal–Dual Relations When the Primal Is in Standard Form 193


    4.3.4 Duality Theorems 195


    4.3.5 Dual Simplex Method 195


    4.4 DecompositionPrinciple 200


    4.5 Sensitivityor PostoptimalityAnalysis 207


    4.5.1 Changes in the Right-Hand-Side Constants b 208


    i


    4.5.2 Changes in the Cost Coefficients c 212


    j


    4.5.3 Addition of New Variables 214


    4.5.4 Changes in the Constraint Coefficients a 215


    ij


    4.5.5 Addition of Constraints 218


    4.6 TransportationProblem 220 Contents ix


    4.7 Karmarkar’s Interior Method 222


    4.7.1 Statement of the Problem 223


    4.7.2 Conversion of an LP Problem into the Required Form 224


    4.7.3 Algorithm 226


    4.8 Quadratic Programming 229


    4.9 MATLAB Solutions 235


    References and Bibliography 237


    Review Questions 239


    Problems 239


    5 Nonlinear Programming I: One-Dimensional Minimization Methods 248


    5.1 Introduction 248


    5.2 Unimodal Function 253


    ELIMINATION METHODS 254


    5.3 Unrestricted Search 254


    5.3.1 Search with Fixed Step Size 254


    5.3.2 Search with Accelerated Step Size 255


    5.4 ExhaustiveSearch 256


    5.5 Dichotomous Search 257


    5.6 Interval Halving Method 260


    5.7 Fibonacci Method 263


    5.8 Golden Section Method 267


    5.9 Comparison of Elimination Methods 271


    INTERPOLATION METHODS 271


    5.10 Quadratic Interpolation Method 273


    5.11 Cubic Interpolation Method 280


    5.12 Direct Root Methods 286


    5.12.1 Newton Method 286


    5.12.2 Quasi-Newton Method 288


    5.12.3 Secant Method 290


    5.13 Practical Considerations 293


    5.13.1 How to Make the Methods Efficient and More Reliable 293


    5.13.2 Implementation in MultivariableOptimization Problems 293


    5.13.3 Comparison of Methods 294


    5.14 MATLAB Solution of One-Dimensional MinimizationProblems 294


    References and Bibliography 295


    Review Questions 295


    Problems 296 x Contents


    6 Nonlinear Programming II: Unconstrained Optimization Techniques 301


    6.1 Introduction 301


    6.1.1 Classification of Unconstrained MinimizationMethods 304


    6.1.2 General Approach 305


    6.1.3 Rate of Convergence 305


    6.1.4 Scaling of Design Variables 305


    DIRECT SEARCH METHODS 309


    6.2 Random Search Methods 309


    6.2.1 Random Jumping Method 311


    6.2.2 Random Walk Method 312


    6.2.3 Random Walk Method with Direction Exploitation 313


    6.2.4 Advantages of Random Search Methods 314


    6.3 Grid Search Method 314


    6.4 UnivariateMethod 315


    6.5 Pattern Directions 318


    6.6 Powell’s Method 319


    6.6.1 Conjugate Directions 319


    6.6.2 Algorithm 323


    6.7 Simplex Method 328


    6.7.1 Reflection 328


    6.7.2 Expansion 331


    6.7.3 Contraction 332


    INDIRECT SEARCH (DESCENT) METHODS 335


    6.8 Gradient of a Function 335


    6.8.1 Evaluation of the Gradient 337


    6.8.2 Rate of Change of a Function along a Direction 338


    6.9 Steepest Descent (Cauchy) Method 339


    6.10 ConjugateGradient (Fletcher–Reeves) Method 341


    6.10.1 Development of the Fletcher–Reeves Method 342


    6.10.2 Fletcher–Reeves Method 343


    6.11 Newton’s Method 345


    6.12 Marquardt Method 348


    6.13 Quasi-NewtonMethods 350


    6.13.1 Rank 1 Updates 351


    6.13.2 Rank 2 Updates 352


    6.14 Davidon–Fletcher–PowellMethod 354


    6.15 Broyden–Fletcher–Goldfarb–ShannoMethod 360


    6.16 Test Functions 363


    6.17 MATLABSolution of Unconstrained Optimization Problems 365


    References and Bibliography 366


    Review Questions 368


    Problems 370 Contents xi


    7 Nonlinear Programming III: Constrained Optimization Techniques 380


    7.1 Introduction 380


    7.2 Characteristics of a Constrained Problem 380


    DIRECT METHODS 383


    7.3 Random Search Methods 383


    7.4 Complex Method 384


    7.5 Sequential Linear Programming 387


    7.6 Basic Approach in the Methods of Feasible Directions 393


    7.7 Zoutendijk’sMethod of Feasible Directions 394


    7.7.1 Direction-FindingProblem 395


    7.7.2 Determination of Step Length 398


    7.7.3 Termination Criteria 401


    7.8 Rosen’s Gradient Projection Method 404


    7.8.1 Determination of Step Length 407


    7.9 Generalized Reduced Gradient Method 412


    7.10 Sequential Quadratic Programming 422


    7.10.1 Derivation 422


    7.10.2 Solution Procedure 425


    INDIRECT METHODS 428


    7.11 Transformation Techniques 428


    7.12 Basic Approach of thePenalty Function Method 430


    7.13 Interior Penalty Function Method 432


    7.14 Convex Programming Problem 442


    7.15 Exterior Penalty Function Method 443


    7.16 Extrapolation Techniques in the InteriorPenalty Function Method 447


    7.16.1 Extrapolationof the Design VectorX 448


    7.16.2 Extrapolationof the Functionf 450


    7.17 Extended Interior Penalty Function Methods 451


    7.17.1 Linear Extended Penalty Function Method 451


    7.17.2 Quadratic Extended Penalty Function Method 452


    7.18 Penalty Function Method for Problems with Mixed Equalityand Inequality


    Constraints 453


    7.18.1 Interior Penalty Function Method 454


    7.18.2 Exterior Penalty Function Method 455


    7.19 Penalty Function Method for Parametric Constraints 456


    7.19.1 Parametric Constraint 456


    7.19.2 Handling Parametric Constraints 457


    7.20 Augmented Lagrange MultiplierMethod 459


    7.20.1 Equality-ConstrainedProblems 459


    7.20.2 Inequality-ConstrainedProblems 462


    7.20.3 Mixed Equality–Inequality-ConstrainedProblems 463


    Please note: To fully download this free PDF,EBook files you need know All free.
    Found by internet command,site not saved pdf file
You May Also Like

Related PPT Template in the same category.