Table of Contents

Preface xvii


1 Introduction to Optimization 1


1.1 Introduction 1


1.2 Historical Development 3


1.3 Engineering Applications of Optimization 5


1.4 Statement of an Optimization Problem 6


1.5 Classification of Optimization Problems 14


1.6 Optimization Techniques 35


1.7 Engineering Optimization Literature 35


1.8 Solution of Optimization Problems Using MATLAB 36


2 Classical Optimization Techniques 63


2.1 Introduction 63


2.2 Single-Variable Optimization 63


2.3 Multivariable Optimization with No Constraints 68


2.4 Multivariable Optimization with Equality Constraints 75


2.5 Multivariable Optimization with Inequality Constraints 93


2.6 Convex Programming Problem 104


3 Linear Programming I: Simplex Method 119


3.1 Introduction 119


3.2 Applications of Linear Programming 120


3.3 Standard Form of a Linear Programming Problem 122


3.4 Geometry of Linear Programming Problems 124


3.5 Definitions and Theorems 127


3.6 Solution of a System of Linear Simultaneous Equations 133


3.7 Pivotal Reduction of a General System of Equations 135


3.8 Motivation of the Simplex Method 138


3.9 Simplex Algorithm 139


3.10 Two Phases of the Simplex Method 150


3.11 MATLAB Solution of LP Problems 156


4 Linear Programming II: Additional Topics and Extensions 177


4.1 Introduction 177


4.2 Revised Simplex Method 177


4.3 Duality in Linear Programming 192


4.4 Decomposition Principle 200


4.5 Sensitivity or Postoptimality Analysis 207


4.6 Transportation Problem 220


4.7 Karmarkar's Interior Method 222


4.8 Quadratic Programming 229


4.9 MATLAB Solutions 235


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.4 Exhaustive Search 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.13 Practical Considerations 293


5.14 MATLAB Solution of One-Dimensional Minimization Problems 294


6 Nonlinear Programming II: Unconstrained Optimization Techniques 301


6.1 Introduction 301


DIRECT SEARCH METHODS 309


6.2 Random Search Methods 309


6.3 Grid Search Method 314


6.4 Univariate Method 315


6.5 Pattern Directions 318


6.6 Powell's Method 319


6.7 Simplex Method 328


INDIRECT SEARCH (DESCENT) METHODS 335


6.8 Gradient of a Function 335


6.9 Steepest Descent (Cauchy) Method 339


6.10 Conjugate Gradient (Fletcher–Reeves) Method 341


6.11 Newton's Method 345


6.12 Marquardt Method 348


6.13 Quasi-Newton Methods 350


6.14 Davidon–Fletcher–Powell Method 354


6.15 Broyden–Fletcher–Goldfarb–Shanno Method 360


6.16 Test Functions 363


6.17 MATLAB Solution of Unconstrained Optimization Problems 365


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's Method of Feasible Directions 394


7.8 Rosen's Gradient Projection Method 404


7.9 Generalized Reduced Gradient Method 412


7.10 Sequential Quadratic Programming 422


INDIRECT METHODS 428


7.11 Transformation Techniques 428


7.12 Basic Approach of the Penalty 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 Interior Penalty Function Method 447


7.17 Extended Interior Penalty Function Methods 451


7.18 Penalty Function Method for Problems with Mixed Equality and Inequality Constraints 453


7.19 Penalty Function Method for Parametric Constraints 456


7.20 Augmented Lagrange Multiplier Method 459


7.21 Checking the Convergence of Constrained Optimization Problems 464


7.22 Test Problems 467


7.23 MATLAB Solution of Constrained Optimization Problems 474


8 Geometric Programming 492


8.1 Introduction 492


8.2 Posynomial 492


8.3 Unconstrained Minimization Problem 493


8.4 Solution of an Unconstrained Geometric Programming Program Using Differential Calculus 493


8.5 Solution of an Unconstrained Geometric Programming Problem Using Arithmetic–Geometric Inequality 500


8.6 Primal–Dual Relationship and Sufficiency Conditions in the Unconstrained Case 501


8.7 Constrained Minimization 508


8.8 Solution of a Constrained Geometric Programming Problem 509


8.9 Primal and Dual Programs in the Case of Less-Than Inequalities 510


8.10 Geometric Programming with Mixed Inequality Constraints 518


8.11 Complementary Geometric Programming 520


8.12 Applications of Geometric Programming 525


9 Dynamic Programming 544


9.1 Introduction 544


9.2 Multistage Decision Processes 545


9.3 Concept of Suboptimization and Principle of Optimality 549


9.4 Computational Procedure in Dynamic Programming 553


9.5 Example Illustrating the Calculus Method of Solution 555


9.6 Example Illustrating the Tabular Method of Solution 560


9.7 Conversion of a Final Value Problem into an Initial Value Problem 566


9.8 Linear Programming as a Case of Dynamic Programming 569


9.9 Continuous Dynamic Programming 573


9.10 Additional Applications 576


10 Integer Programming 588


10.1 Introduction 588


INTEGER LINEAR PROGRAMMING 589


10.2 Graphical Representation 589


10.3 Gomory's Cutting Plane Method 591


10.4 Balas' Algorithm for Zero–One Programming Problems 604


INTEGER NONLINEAR PROGRAMMING 606


10.5 Integer Polynomial Programming 606


10.6 Branch-and-Bound Method 609


10.7 Sequential Linear Discrete Programming 614


10.8 Generalized Penalty Function Method 619


10.9 Solution of Binary Programming Problems Using MATLAB 624


11 Stochastic Programming 632


11.1 Introduction 632


11.2 Basic Concepts of Probability Theory 632


11.3 Stochastic Linear Programming 647


11.4 Stochastic Nonlinear Programming 652


11.5 Stochastic Geometric Programming 659


12 Optimal Control and Optimality Criteria Methods 668


12.1 Introduction 668


12.2 Calculus of Variations 668


12.3 Optimal Control Theory 678


12.4 Optimality Criteria Methods 683


13 Modern Methods of Optimization 693


13.1 Introduction 693


13.2 Genetic Algorithms 694


13.3 Simulated Annealing 702


13.4 Particle Swarm Optimization 708


13.5 Ant Colony Optimization 714


13.6 Optimization of Fuzzy Systems 722


13.7 Neural-Network-Based Optimization 727


14 Practical Aspects of Optimization 737


14.1 Introduction 737


14.2 Reduction of Size of an Optimization Problem 737


14.3 Fast Reanalysis Techniques 740


14.4 Derivatives of Static Displacements and Stresses 745


14.5 Derivatives of Eigenvalues and Eigenvectors 747


14.6 Derivatives of Transient Response 749


14.7 Sensitivity of Optimum Solution to Problem Parameters 751


14.8 Multilevel Optimization 755


14.9 Parallel Processing 760


14.10 Multiobjective Optimization 761


14.11 Solution of Multiobjective Problems Using MATLAB 767


A Convex and Concave Functions 779


B Some Computational Aspects of Optimization 784


B.1 Choice of Method 784


B.2 Comparison of Unconstrained Methods 784


B.3 Comparison of Constrained Methods 785


B.4 Availability of Computer Programs 786


B.5 Scaling of Design Variables and Constraints 787


B.6 Computer Programs for Modern Methods of Optimization 788


C Introduction to MATLAB 791


C.1 Features and Special Characters 791


C.2 Defining Matrices in MATLAB 792


C.3 CREATING m-FILES 793


C.4 Optimization Toolbox 793


Answers to Selected Problems 795


Index 803

About the Author

Singiresu S. Rao, PhD, is a Professor and Chairman of the Department of Mechanical Engineering at the University of Miami. Dr. Rao has published more than 175 technical papers in internationally respected journals and more than 150 papers in conference proceedings in the areas of engineering optimization, reliability-based design, fuzzy systems, uncertainty models, structural and mechanical design, and vibration engineering. He has authored several books, including The Finite Element Method in Engineering, Mechanical Vibrations, Vibration of Continuous Systems, Reliability-Based Design, and Applied Numerical Methods for Engineers and Scientists.

Reviews

"He presents an updated textbook addressing the techniques and applications of engineering optimization for the efficient and economical design and production of products and systems. The material has been used extensively by the author to teach optimum design and engineering optimization courses at the advanced-undergraduate and graduate levels at a number of universities." (Book News, August 2009)