Engineering Optimization

Singiresu S. Rao is a Professor in the Mechanical and Aerospace Engineering Department at the University of Miami. His main areas of research include multi objective optimization and uncertainty models in engineering analysis, design and optimization.

• Preface xviiAcknowledgment xxiAbout the Author xxiii1 Introduction to Optimization 11.1 Introduction 11.2 Historical Development 31.2.1 Modern Methods of Optimization 41.3 Engineering Applications of Optimization 51.4 Statement of an Optimization Problem 61.4.1 Design Vector 61.4.2 Design Constraints 71.4.3 Constraint Surface 71.4.4 Objective Function 81.4.5 Objective Function Surfaces 91.5 Classification of Optimization Problems 141.5.1 Classification Based on the Existence of Constraints 141.5.2 Classification Based on the Nature of the Design Variables 141.5.3 Classification Based on the Physical Structure of the Problem 151.5.4 Classification Based on the Nature of the Equations Involved 181.5.5 Classification Based on the Permissible Values of the Design Variables 271.5.6 Classification Based on the Deterministic Nature of the Variables 281.5.7 Classification Based on the Separability of the Functions 291.5.8 Classification Based on the Number of Objective Functions 311.6 Optimization Techniques 331.7 Engineering Optimization Literature 341.8 Solutions Using MATLAB 34References and Bibliography 34Review Questions 40Problems 412 Classical Optimization Techniques 572.1 Introduction 572.2 Single-Variable Optimization 572.3 Multivariable Optimization with no Constraints 622.3.1 Definition: rth Differential of f 622.3.2 Semidefinite Case 672.3.3 Saddle Point 672.4 Multivariable Optimization with Equality Constraints 692.4.1 Solution by Direct Substitution 692.4.2 Solution by the Method of Constrained Variation 712.4.3 Solution by the Method of Lagrange Multipliers 772.5 Multivariable Optimization with Inequality Constraints 852.5.1 Kuhn–Tucker Conditions 902.5.2 Constraint Qualification 902.6 Convex Programming Problem 96References and Bibliography 96Review Questions 97Problems 983 Linear Programming I: Simplex Method 1093.1 Introduction 1093.2 Applications of Linear Programming 1103.3 Standard form of a Linear Programming Problem 1123.3.1 Scalar Form 1123.3.2 Matrix Form 1123.4 Geometry of Linear Programming Problems 1143.5 Definitions and Theorems 1173.5.1 Definitions 1173.5.2 Theorems 1203.6 Solution of a System of Linear Simultaneous Equations 1223.7 Pivotal Reduction of a General System of Equations 1233.8 Motivation of the Simplex Method 1273.9 Simplex Algorithm 1283.9.1 Identifying an Optimal Point 1283.9.2 Improving a Nonoptimal Basic Feasible Solution 1293.10 Two Phases of the Simplex Method 1373.11 Solutions Using MATLAB 143References and Bibliography 143Review Questions 143Problems 1454 Linear Programming II: Additional Topics and Extensions 1594.1 Introduction 1594.2 Revised Simplex Method 1594.3 Duality in Linear Programming 1734.3.1 Symmetric Primal–Dual Relations 1734.3.2 General Primal–Dual Relations 1744.3.3 Primal–Dual Relations when the Primal Is in Standard Form 1754.3.4 Duality Theorems 1764.3.5 Dual Simplex Method 1764.4 Decomposition Principle 1804.5 Sensitivity or Postoptimality Analysis 1874.5.1 Changes in the Right-Hand-Side Constants bi 1884.5.2 Changes in the Cost Coefficients cj 1924.5.3 Addition of New Variables 1944.5.4 Changes in the Constraint Coefficients aij 1954.5.5 Addition of Constraints 1974.6 Transportation Problem 1994.7 Karmarkar’s Interior Method 2024.7.1 Statement of the Problem 2034.7.2 Conversion of an LP Problem into the Required Form 2034.7.3 Algorithm 2054.8 Quadratic Programming 2084.9 Solutions Using Matlab 214References and Bibliography 214Review Questions 215Problems 2165 Nonlinear Programming I: One-Dimensional Minimization Methods 2255.1 Introduction 2255.2 Unimodal Function 230Elimination Methods 2315.3 Unrestricted Search 2315.3.1 Search with Fixed Step Size 2315.3.2 Search with Accelerated Step Size 2325.4 Exhaustive Search 2325.5 Dichotomous Search 2345.6 Interval Halving Method 2365.7 Fibonacci Method 2385.8 Golden Section Method 2435.9 Comparison of Elimination Methods 246Interpolation Methods 2475.10 Quadratic Interpolation Method 2485.11 Cubic Interpolation Method 2535.12 Direct Root Methods 2595.12.1 Newton Method 2595.12.2 Quasi-Newton Method 2615.12.3 Secant Method 2635.13 Practical Considerations 2655.13.1 How to Make the Methods Efficient and More Reliable 2655.13.2 Implementation in Multivariable Optimization Problems 2665.13.3 Comparison of Methods 2665.14 Solutions Using MATLAB 267References and Bibliography 267Review Questions 267Problems 2686 Nonlinear Programming II: Unconstrained Optimization Techniques 2736.1 Introduction 2736.1.1 Classification of Unconstrained Minimization Methods 2766.1.2 General Approach 2766.1.3 Rate of Convergence 2766.1.4 Scaling of Design Variables 277Direct Search Methods 2806.2 Random Search Methods 2806.2.1 Random Jumping Method 2806.2.2 Random Walk Method 2826.2.3 Random Walk Method with Direction Exploitation 2836.2.4 Advantages of Random Search Methods 2846.3 Grid Search Method 2856.4 Univariate Method 2856.5 Pattern Directions 2886.6 Powell’s Method 2896.6.1 Conjugate Directions 2896.6.2 Algorithm 2936.7 Simplex Method 2986.7.1 Reflection 2986.7.2 Expansion 3016.7.3 Contraction 301Indirect Search (Descent) Methods 3046.8 Gradient of a Function 3046.8.1 Evaluation of the Gradient 3066.8.2 Rate of Change of a Function Along a Direction 3076.9 Steepest Descent (Cauchy) Method 3086.10 Conjugate Gradient (Fletcher–Reeves) Method 3106.10.1 Development of the Fletcher–Reeves Method 3106.10.2 Fletcher–Reeves Method 3116.11 Newton’s Method 3136.12 Marquardt Method 3166.13 Quasi-Newton Methods 3176.13.1 Computation of [Bi] 3186.13.2 Rank 1 Updates 3196.13.3 Rank 2 Updates 3206.14 Davidon–Fletcher–Powell Method 3216.15 Broyden–Fletcher–Goldfarb–Shanno Method 3276.16 Test Functions 3306.17 Solutions Using Matlab 332References and Bibliography 333Review Questions 334Problems 3367 Nonlinear Programming III: Constrained Optimization Techniques 3477.1 Introduction 3477.2 Characteristics of a Constrained Problem 347Direct Methods 3507.3 Random Search Methods 3507.4 Complex Method 3517.5 Sequential Linear Programming 3537.6 Basic Approach in the Methods of Feasible Directions 3607.7 Zoutendijk’s Method of Feasible Directions 3607.7.1 Direction-Finding Problem 3627.7.2 Determination of Step Length 3647.7.3 Termination Criteria 3677.8 Rosen’s Gradient Projection Method 3697.8.1 Determination of Step Length 3727.9 Generalized Reduced Gradient Method 3777.10 Sequential Quadratic Programming 3867.10.1 Derivation 3867.10.2 Solution Procedure 389Indirect Methods 3927.11 Transformation Techniques 3927.12 Basic Approach of the Penalty Function Method 3947.13 Interior Penalty Function Method 3967.14 Convex Programming Problem 4057.15 Exterior Penalty Function Method 4067.16 Extrapolation Techniques in the Interior Penalty Function Method 4107.16.1 Extrapolation of the Design Vector X 4107.16.2 Extrapolation of the Function f 4127.17 Extended Interior Penalty Function Methods 4147.17.1 Linear Extended Penalty Function Method 4147.17.2 Quadratic Extended Penalty Function Method 4157.18 Penalty Function Method for Problems with Mixed Equality and Inequality Constraints 4167.18.1 Interior Penalty Function Method 4167.18.2 Exterior Penalty Function Method 4187.19 Penalty Function Method for Parametric Constraints 4187.19.1 Parametric Constraint 4187.19.2 Handling Parametric Constraints 4207.20 Augmented Lagrange Multiplier Method 4227.20.1 Equality-Constrained Problems 4227.20.2 Inequality-Constrained Problems 4237.20.3 Mixed Equality–Inequality-Constrained Problems 4257.21 Checking the Convergence of Constrained Optimization Problems 4267.21.1 Perturbing the Design Vector 4277.21.2 Testing the Kuhn–Tucker Conditions 4277.22 Test Problems 4287.22.1 Design of a Three-Bar Truss 4297.22.2 Design of a Twenty-Five-Bar Space Truss 4307.22.3 Welded Beam Design 4317.22.4 Speed Reducer (Gear Train) Design 4337.22.5 Heat Exchanger Design [7.42] 4357.23 Solutions Using MATLAB 435References and Bibliography 435Review Questions 437Problems 4398 Geometric Programming 4498.1 Introduction 4498.2 Posynomial 4498.3 Unconstrained Minimization Problem 4508.4 Solution of an Unconstrained Geometric Programming Program using Differential Calculus 4508.4.1 Degree of Difficulty 4538.4.2 Sufficiency Condition 4538.4.3 Finding the Optimal Values of Design Variables 4538.5 Solution of an Unconstrained Geometric Programming Problem Using Arithmetic–Geometric Inequality 4578.6 Primal–dual Relationship and Sufficiency Conditions in the Unconstrained Case 4588.6.1 Primal and Dual Problems 4618.6.2 Computational Procedure 4618.7 Constrained Minimization 4648.8 Solution of a Constrained Geometric Programming Problem 4658.8.1 Optimum Design Variables 4668.9 Primal and Dual Programs in the Case of Less-than Inequalities 4668.10 Geometric Programming with Mixed Inequality Constraints 4738.11 Complementary Geometric Programming 4758.11.1 Solution Procedure 4778.11.2 Degree of Difficulty 4788.12 Applications of Geometric Programming 480References and Bibliography 491Review Questions 493Problems 4939 Dynamic Programming 4979.1 Introduction 4979.2 Multistage Decision Processes 4989.2.1 Definition and Examples 4989.2.2 Representation of a Multistage Decision Process 4999.2.3 Conversion of a Nonserial System to a Serial System 5009.2.4 Types of Multistage Decision Problems 5019.3 Concept of Suboptimization and Principle of Optimality 5019.4 Computational Procedure in Dynamic Programming 5059.5 Example Illustrating the Calculus Method of Solution 5079.6 Example Illustrating the Tabular Method of Solution 5129.6.1 Suboptimization of Stage 1 (Component 1) 5149.6.2 Suboptimization of Stages 2 and 1 (Components 2 and 1) 5149.6.3 Suboptimization of Stages 3, 2, and 1 (Components 3, 2, and 1) 5159.7 Conversion of a Final Value Problem into an Initial Value Problem 5179.8 Linear Programming as a Case of Dynamic Programming 5199.9 Continuous Dynamic Programming 5239.10 Additional Applications 5269.10.1 Design of Continuous Beams 5269.10.2 Optimal Layout (Geometry) of a Truss 5279.10.3 Optimal Design of a Gear Train 5289.10.4 Design of a Minimum-Cost Drainage System 529References and Bibliography 530Review Questions 531Problems 53210 Integer Programming 53710.1 Introduction 537Integer Linear Programming 53810.2 Graphical Representation 53810.3 Gomory’s Cutting Plane Method 54010.3.1 Concept of a Cutting Plane 54010.3.2 Gomory’s Method for All-Integer Programming Problems 54110.3.3 Gomory’s Method for Mixed-Integer Programming Problems 54710.4 Balas’ Algorithm for Zero–One Programming Problems 551Integer Nonlinear Programming 55310.5 Integer Polynomial Programming 55310.5.1 Representation of an Integer Variable by an Equivalent System of Binary Variables 55310.5.2 Conversion of a Zero–One Polynomial Programming Problem into a Zero–One LP Problem 55510.6 Branch-and-Bound Method 55610.7 Sequential Linear Discrete Programming 56110.8 Generalized Penalty Function Method 56410.9 Solutions Using MATLAB 569References and Bibliography 569Review Questions 570Problems 57111 Stochastic Programming 57511.1 Introduction 57511.2 Basic Concepts of Probability Theory 57511.2.1 Definition of Probability 57511.2.2 Random Variables and Probability Density Functions 57611.2.3 Mean and Standard Deviation 57811.2.4 Function of a Random Variable 58011.2.5 Jointly Distributed Random Variables 58111.2.6 Covariance and Correlation 58311.2.7 Functions of Several Random Variables 58311.2.8 Probability Distributions 58511.2.9 Central Limit Theorem 58911.3 Stochastic Linear Programming 58911.4 Stochastic Nonlinear Programming 59411.4.1 Objective Function 59411.4.2 Constraints 59511.5 Stochastic Geometric Programming 600References and Bibliography 602Review Questions 603Problems 60412 Optimal Control and Optimality Criteria Methods 60912.1 Introduction 60912.2 Calculus of Variations 60912.2.1 Introduction 60912.2.2 Problem of Calculus of Variations 61012.2.3 Lagrange Multipliers and Constraints 61512.2.4 Generalization 61812.3 Optimal Control Theory 61912.3.1 Necessary Conditions for Optimal Control 61912.3.2 Necessary Conditions for a General Problem 62112.4 Optimality Criteria Methods 62212.4.1 Optimality Criteria with a Single Displacement Constraint 62312.4.2 Optimality Criteria with Multiple Displacement Constraints 62412.4.3 Reciprocal Approximations 625References and Bibliography 628Review Questions 628Problems 62913 Modern Methods of Optimization 63313.1 Introduction 63313.2 Genetic Algorithms 63313.2.1 Introduction 63313.2.2 Representation of Design Variables 63413.2.3 Representation of Objective Function and Constraints 63513.2.4 Genetic Operators 63613.2.5 Algorithm 64013.2.6 Numerical Results 64113.3 Simulated Annealing 64113.3.1 Introduction 64113.3.2 Procedure 64213.3.3 Algorithm 64313.3.4 Features of the Method 64413.3.5 Numerical Results 64413.4 Particle Swarm Optimization 64713.4.1 Introduction 64713.4.2 Computational Implementation of PSO 64813.4.3 Improvement to the Particle Swarm Optimization Method 64913.4.4 Solution of the Constrained Optimization Problem 64913.5 Ant Colony Optimization 65213.5.1 Basic Concept 65213.5.2 Ant Searching Behavior 65313.5.3 Path Retracing and Pheromone Updating 65413.5.4 Pheromone Trail Evaporation 65413.5.5 Algorithm 65513.6 Optimization of Fuzzy Systems 66013.6.1 Fuzzy Set Theory 66013.6.2 Optimization of Fuzzy Systems 66213.6.3 Computational Procedure 66313.6.4 Numerical Results 66413.7 Neural-Network-Based Optimization 665References and Bibliography 667Review Questions 669Problems 67114 Metaheuristic Optimization Methods 67314.1 Definitions 67314.2 Metaphors Associated with Metaheuristic Optimization Methods 67314.3 Details of Representative Metaheuristic Algorithms 68014.3.1 Crow Search Algorithm 68014.3.2 Firefly Optimization Algorithm (FA) 68114.3.3 Harmony Search Algorithm 68414.3.4 Teaching-Learning-Based Optimization (TLBO) 68714.3.5 Honey Bee Swarm Optimization Algorithm 689References and Bibliography 692Review Questions 69415 Practical Aspects of Optimization 69715.1 Introduction 69715.2 Reduction of Size of an Optimization Problem 69715.2.1 Reduced Basis Technique 69715.2.2 Design Variable Linking Technique 69815.3 Fast Reanalysis Techniques 70015.3.1 Incremental Response Approach 70015.3.2 Basis Vector Approach 70415.4 Derivatives of Static Displacements and Stresses 70515.5 Derivatives of Eigenvalues and Eigenvectors 70715.5.1 Derivatives of ;;i 70715.5.2 Derivatives of Yi 70815.6 Derivatives of Transient Response 70915.7 Sensitivity of Optimum Solution to Problem Parameters 71215.7.1 Sensitivity Equations Using Kuhn–Tucker Conditions 71215.7.2 Sensitivity Equations Using the Concept of Feasible Direction 714References and Bibliography 715Review Questions 716Problems 71616 Multilevel and Multiobjective Optimization 72116.1 Introduction 72116.2 Multilevel Optimization 72116.2.1 Basic Idea 72116.2.2 Method 72216.3 Parallel Processing 72616.4 Multiobjective Optimization 72916.4.1 Utility Function Method 73016.4.2 Inverted Utility Function Method 73016.4.3 Global Criterion Method 73016.4.4 Bounded Objective Function Method 73016.4.5 Lexicographic Method 73116.4.6 Goal Programming Method 73216.4.7 Goal Attainment Method 73216.4.8 Game Theory Approach 73316.5 Solutions Using MATLAB 735References and Bibliography 735Review Questions 736Problems 73717 Solution of Optimization Problems Using MATLAB 73917.1 Introduction 73917.2 Solution of General Nonlinear Programming Problems 74017.3 Solution of Linear Programming Problems 74217.4 Solution of LP Problems Using Interior Point Method 74317.5 Solution of Quadratic Programming Problems 74517.6 Solution of One-Dimensional Minimization Problems 74617.7 Solution of Unconstrained Optimization Problems 74617.8 Solution of Constrained Optimization Problems 74717.9 Solution of Binary Programming Problems 75017.10 Solution of Multiobjective Problems 751References and Bibliography 755Problems 755A Convex and Concave Functions 761B Some Computational Aspects of Optimization 767B.1 Choice of Method 767B.2 Comparison of Unconstrained Methods 767B.3 Comparison of Constrained Methods 768B.4 Availability of Computer Programs 769B.5 Scaling of Design Variables and Constraints 770B.6 Computer Programs for Modern Methods of Optimization 771References and Bibliography 772C Introduction to MATLAB® 773C.1 Features and Special Characters 773C.2 Defining Matrices in MATLAB 774C.3 Creating m-Files 775C.4 Optimization Toolbox 775Answers to Selected Problems 777Index 787