1 Introduction to Optimization 1 1.1 Introduction 1 1.2 Historical Development 3 1.2.1 Modern Methods of Optimization 4 1.3 Engineering Applications of 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 7 1.4.4 Objective Function 8 1.4.5 Objective Function Surfaces 9 1.5 Classification of Optimization Problems 14 1.5.1 Classification Based on the Existence of Constraints 14 1.5.2 Classification Based on the Nature of the Design Variables 14 1.5.3 Classification Based on the Physical Structure of the Problem 15 1.5.4 Classification Based on the Nature of the Equations Involved 18 1.5.5 Classification Based on the Permissible Values of the Design Variables 27 1.5.6 Classification Based on the Deterministic Nature of the Variables 28 1.5.7 Classification Based on the Separability of the Functions 29 1.5.8 Classification Based on the Number of Objective Functions 31 1.6 Optimization Techniques 33 1.7 Engineering Optimization Literature 34 1.8 Solutions Using MATLAB 34 References and Bibliography 34 Review Questions 40 Problems 41 2 Classical Optimization Techniques 57 2.1 Introduction 57 2.2 Single-Variable Optimization 57 2.3 Multivariable Optimization with no Constraints 62 2.3.1 Definition: rth Differential of f 62 2.3.2 Semidefinite Case 67 2.3.3 Saddle Point 67 2.4 Multivariable Optimization with Equality Constraints 69 2.4.1 Solution by Direct Substitution 69 2.4.2 Solution by the Method of Constrained Variation 71 2.4.3 Solution by the Method of Lagrange Multipliers 77 2.5 Multivariable Optimization with Inequality Constraints 85 2.5.1 Kuhn-Tucker Conditions 90 2.5.2 Constraint Qualification 90 2.6 Convex Programming Problem 96 References and Bibliography 96 Review Questions 97 Problems 98 3 Linear Programming I: Simplex Method 109 3.1 Introduction 109 3.2 Applications of Linear Programming 110 3.3 Standard form of a Linear Programming Problem 112 3.3.1 Scalar Form 112 3.3.2 Matrix Form 112 3.4 Geometry of Linear Programming Problems 114 3.5 Definitions and Theorems 117 3.5.1 Definitions 117 3.5.2 Theorems 120 3.6 Solution of a System of Linear Simultaneous Equations 122 3.7 Pivotal Reduction of a General System of Equations 123 3.8 Motivation of the Simplex Method 127 3.9 Simplex Algorithm 128 3.9.1 Identifying an Optimal Point 128 3.9.2 Improving a Nonoptimal Basic Feasible Solution 129 3.10 Two Phases of the Simplex Method 137 3.11 Solutions Using MATLAB 143 References and Bibliography 143 Review Questions 143 Problems 145 4 Linear Programming II: Additional Topics and Extensions 159 4.1 Introduction 159 4.2 Revised Simplex Method 159 4.3 Duality in Linear Programming 173 4.3.1 Symmetric Primal-Dual Relations 173 4.3.2 General Primal-Dual Relations 174 4.3.3 Primal-Dual Relations when the Primal Is in Standard Form 175 4.3.4 Duality Theorems 176 4.3.5 Dual Simplex Method 176 4.4 Decomposition Principle 180 4.5 Sensitivity or Postoptimality Analysis 187 4.5.1 Changes in the Right-Hand-Side Constants bi 188 4.5.2 Changes in the Cost Coefficients cj 192 4.5.3 Addition of New Variables 194 4.5.4 Changes in the Constraint Coefficients aij 195 4.5.5 Addition of Constraints 197 4.6 Transportation Problem 199 4.7 Karmarkar's Interior Method 202 4.7.1 Statement of the Problem 203 4.7.2 Conversion of an LP Problem into the Required Form 203 4.7.3 Algorithm 205 4.8 Quadratic Programming 208 4.9 Solutions Using Matlab 214 References and Bibliography 214 Review Questions 215 Problems 216 5 Nonlinear Programming I: One-Dimensional Minimization Methods 225 5.1 Introduction 225 5.2 Unimodal Function 230 Elimination Methods 231 5.3 Unrestricted Search 231 5.3.1 Search with Fixed Step Size 231 5.3.2 Search with Accelerated Step Size 232 5.4 Exhaustive Search 232 5.5 Dichotomous Search 234 5.6 Interval Halving Method 236 5.7 Fibonacci Method 238 5.8 Golden Section Method 243 5.9 Comparison of Elimination Methods 246 Interpolation Methods 247 5.10 Quadratic Interpolation Method 248 5.11 Cubic Interpolation Method 253 5.12 Direct Root Methods 259 5.12.1 Newton Method 259 5.12.2 Quasi-Newton Method 261 5.12.3 Secant Method 263 5.13 Practical Considerations 265 5.13.1 How to Make the Methods Efficient and More Reliable 265 5.13.2 Implementation in Multivariable Optimization Problems 266 5.13.3 Comparison of Methods 266 5.14 Solutions Using MATLAB 267 References and Bibliography 267 Review Questions 267 Problems 268 6 Nonlinear Programming II: Unconstrained Optimization Techniques 273 6.1 Introduction 273 6.1.1 Classification of Unconstrained Minimization Methods 276 6.1.2 General Approach 276 6.1.3 Rate of Convergence 276 6.1.4 Scaling of Design Variables 277 Direct Search Methods 280 6.2 Random Search Methods 280 6.2.1 Random Jumping Method 280 6.2.2 Random Walk Method 282 6.2.3 Random Walk Method with Direction Exploitation 283 6.2.4 Advantages of Random Search Methods 284 6.3 Grid Search Method 285 6.4 Univariate Method 285 6.5 Pattern Directions 288 6.6 Powell's Method 289 6.6.1 Conjugate Directions 289 6.6.2 Algorithm 293 6.7 Simplex Method 298 6.7.1 Reflection 298 6.7.2 Expansion 301 6.7.3 Contraction 301 Indirect Search (Descent) Methods 304 6.8 Gradient of a Function 304 6.8.1 Evaluation of the Gradient 306 6.8.2 Rate of Change of a Function Along a Direction 307 6.9 Steepest Descent (Cauchy) Method 308 6.10 Conjugate Gradient (Fletcher-Reeves) Method 310 6.10.1 Development of the Fletcher-Reeves Method 310 6.10.2 Fletcher-Reeves Method 311 6.11 Newton's Method 313 6.12 Marquardt Method 316 6.13 Quasi-Newton Methods 317 6.13.1 Computation of [Bi] 318 6.13.2 Rank 1 Updates 319 6.13.3 Rank 2 Updates 320 6.14 Davidon-Fletcher-Powell Method 321 6.15 Broyden-Fletcher-Goldfarb-Shanno Method 327 6.16 Test Functions 330 6.17 Solutions Using Matlab 332 References and Bibliography 333 Review Questions 334 Problems 336 7 Nonlinear Programming III: Constrained Optimization Techniques 347 7.1 Introduction 347 7.2 Characteristics of a Constrained Problem 347 Direct Methods 350 7.3 Random Search Methods 350 7.4 Complex Method 351 7.5 Sequential Linear Programming 353 7.6 Basic Approach in the Methods of Feasible Directions 360 7.7 Zoutendijk's Method of Feasible Directions 360 7.7.1 Direction-Finding Problem 362 7.7.2 Determination of Step Length 364 7.7.3 Termination Criteria 367 7.8 Rosen's Gradient Projection Method 369 7.8.1 Determination of Step Length 372 7.9 Generalized Reduced Gradient Method 377 7.10 Sequential Quadratic Programming 386 7.10.1 Derivation 386 7.10.2 Solution Procedure 389 Indirect Methods 392 7.11 Transformation Techniques 392 7.12 Basic Approach of the Penalty Function Method 394 7.13 Interior Penalty Function Method 396 7.14 Convex Programming Problem 405 7.15 Exterior Penalty Function Method 406 7.16 Extrapolation Techniques in the Interior Penalty Function Method 410 7.16.1 Extrapolation of the Design Vector X 410 7.16.2 Extrapolation of the Function f 412 7.17 Extended Interior Penalty Function Methods 414 7.17.1 Linear Extended Penalty Function Method 414 7.17.2 Quadratic Extended Penalty Function Method 415 7.18 Penalty Function Method for Problems with Mixed Equality and Inequality Constraints 416 7.18.1 Interior Penalty Function Method 416 7.18.2 Exterior Penalty Function Method 418 7.19 Penalty Function Method for Parametric Constraints 418 7.19.1 Parametric Constraint 418 7.19.2 Handling Parametric Constraints 420 7.20 Augmented Lagrange Multiplier Method 422 7.20.1 Equality-Constrained Problems 422 7.20.2 Inequality-Constrained Problems 423 7.20.3 Mixed Equality-Inequality-Constrained Problems 425 7.21 Checking the Convergence of Constrained Optimization Problems 426 7.21.1 Perturbing the Design Vector 427 7.21.2 Testing the Kuhn-Tucker Conditions 427 7.22 Test Problems 428 7.22.1 Design of a Three-Bar Truss 429 7.22.2 Design of a Twenty-Five-Bar Space Truss 430 7.22.3 Welded Beam Design 431 7.22.4 Speed Reducer (Gear Train) Design 433 7.22.5 Heat Exchanger Design [7.42] 435 7.23 Solutions Using MATLAB 435 References and Bibliography 435 Review Questions 437 Problems 439 8 Geometric Programming 449 8.1 Introduction 449 8.2 Posynomial 449 8.3 Unconstrained Minimization Problem 450 8.4 Solution of an Unconstrained Geometric Programming Program using Differential Calculus 450 8.4.1 Degree of Difficulty 453 8.4.2 Sufficiency Condition 453 8.4.3 Finding the Optimal Values of Design Variables 453 8.5 Solution of an Unconstrained Geometric Programming Problem Using Arithmetic-Geometric Inequality 457 8.6 Primal-dual Relationship and Sufficiency Conditions in the Unconstrained Case 458 8.6.1 Primal and Dual Problems 461 8.6.2 Computational Procedure 461 8.7 Constrained Minimization 464 8.8 Solution of a Constrained Geometric Programming Problem 465 8.8.1 Optimum Design Variables 466 8.9 Primal and Dual Programs in the Case of Less-than Inequalities 466 8.10 Geometric Programming with Mixed Inequality Constraints 473 8.11 Complementary Geometric Programming 475 8.11.1 Solution Procedure 477 8.11.2 Degree of Difficulty 478 8.12 Applications of Geometric Programming 480 References and Bibliography 491 Review Questions 493 Problems 493 9 Dynamic Programming 497 9.1 Introduction 497 9.2 Multistage Decision Processes 498 9.2.1 Definition and Examples 498 9.2.2 Representation of a Multistage Decision Process 499 9.2.3 Conversion of a Nonserial System to a Serial System 500 9.2.4 Types of Multistage Decision Problems 501 9.3 Concept of Suboptimization and Principle of Optimality 501 9.4 Computational Procedure in Dynamic Programming 505 9.5 Example Illustrating the Calculus Method of Solution 507 9.6 Example Illustrating the Tabular Method of Solution 512 9.6.1 Suboptimization of Stage 1 (Component 1) 514 9.6.2 Suboptimization of Stages 2 and 1 (Components 2 and 1) 514 9.6.3 Suboptimization of Stages 3, 2, and 1 (Components 3, 2, and 1) 515 9.7 Conversion of a Final Value Problem into an Initial Value Problem 517 9.8 Linear Programming as a Case of Dynamic Programming 519 9.9 Continuous Dynamic Programming 523 9.10 Additional Applications 526 9.10.1 Design of Continuous Beams 526 9.10.2 Optimal Layout (Geometry) of a Truss 527 9.10.3 Optimal Design of a Gear Train 528 9.10.4 Design of a Minimum-Cost Drainage System 529 References and Bibliography 530 Review Questions 531 Problems 532 10 Integer Programming 537 10.1 Introduction 537 Integer Linear Programming 538 10.2 Graphical Representation 538 10.3 Gomory's Cutting Plane Method 540 10.3.1 Concept of a Cutting Plane 540 10.3.2 Gomory's Method for All-Integer Programming Problems 541 10.3.3 Gomory's Method for Mixed-Integer Programming Problems 547 10.4 Balas' Algorithm for Zero-One Programming Problems 551 Integer Nonlinear Programming 553 10.5 Integer Polynomial Programming 553 10.5.1 Representation of an Integer Variable by an Equivalent System of Binary Variables 553 10.5.2 Conversion of a Zero-One Polynomial Programming Problem into a Zero-One LP Problem 555 10.6 Branch-and-Bound Method 556 10.7 Sequential Linear Discrete Programming 561 10.8 Generalized Penalty Function Method 564 10.9 Solutions Using MATLAB 569 References and Bibliography 569 Review Questions 570 Problems 571 11 Stochastic Programming 575 11.1 Introduction 575 11.2 Basic Concepts of Probability Theory 575 11.2.1 Definition of Probability 575 11.2.2 Random Variables and Probability Density Functions 576 11.2.3 Mean and Standard Deviation 578 11.2.4 Function of a Random Variable 580 11.2.5 Jointly Distributed Random Variables 581 11.2.6 Covariance and Correlation 583 11.2.7 Functions of Several Random Variables 583 11.2.8 Probability Distributions 585 11.2.9 Central Limit Theorem 589 11.3 Stochastic Linear Programming 589 11.4 Stochastic Nonlinear Programming 594 11.4.1 Objective Function 594 11.4.2 Constraints 595 11.5 Stochastic Geometric Programming 600 References and Bibliography 602 Review Questions 603 Problems 604 12 Optimal Control and Optimality Criteria Methods 609 12.1 Introduction 609 12.2 Calculus of Variations 609 12.2.1 Introduction 609 12.2.2 Problem of Calculus of Variations 610 12.2.3 Lagrange Multipliers and Constraints 615 12.2.4 Generalization 618 12.3 Optimal Control Theory 619 12.3.1 Necessary Conditions for Optimal Control 619 12.3.2 Necessary Conditions for a General Problem 621 12.4 Optimality Criteria Methods 622 12.4.1 Optimality Criteria with a Single Displacement Constraint 623 12.4.2 Optimality Criteria with Multiple Displacement Constraints 624 12.4.3 Reciprocal Approximations 625 References and Bibliography 628 Review Questions 628 Problems 629 13 Modern Methods of Optimization 633 13.1 Introduction 633 13.2 Genetic Algorithms 633 13.2.1 Introduction 633 13.2.2 Representation of Design Variables 634 13.2.3 Representation of Objective Function and Constraints 635 13.2.4 Genetic Operators 636 13.2.5 Algorithm 640 13.2.6 Numerical Results 641 13.3 Simulated Annealing 641 13.3.1 Introduction 641 13.3.2 Procedure 642 13.3.3 Algorithm 643 13.3.4 Features of the Method 644 13.3.5 Numerical Results 644 13.4 Particle Swarm Optimization 647 13.4.1 Introduction 647 13.4.2 Computational Implementation of PSO 648 13.4.3 Improvement to the Particle Swarm Optimization Method 649 13.4.4 Solution of the Constrained Optimization Problem 649 13.5 Ant Colony Optimization 652 13.5.1 Basic Concept 652 13.5.2 Ant Searching Behavior 653 13.5.3 Path Retracing and Pheromone Updating 654 13.5.4 Pheromone Trail Evaporation 654 13.5.5 Algorithm 655 13.6 Optimization of Fuzzy Systems 660 13.6.1 Fuzzy Set Theory 660 13.6.2 Optimization of Fuzzy Systems 662 13.6.3 Computational Procedure 663 13.6.4 Numerical Results 664 13.7 Neural-Network-Based Optimization 665 References and Bibliography 667 Review Questions 669 Problems 671 14 Metaheuristic Optimization Methods 673 14.1 Definitions 673 14.2 Metaphors Associated with Metaheuristic Optimization Methods 673 14.3 Details of Representative Metaheuristic Algorithms 680 14.3.1 Crow Search Algorithm 680 14.3.2 Firefly Optimization Algorithm (FA) 681 14.3.3 Harmony Search Algorithm 684 14.3.4 Teaching-Learning-Based Optimization (TLBO) 687 14.3.5 Honey Bee Swarm Optimization Algorithm 689 References and Bibliography 692 Review Questions 694 15 Practical Aspects of Optimization 697 15.1 Introduction 697 15.2 Reduction of Size of an Optimization Problem 697 15.2.1 Reduced Basis Technique 697 15.2.2 Design Variable Linking Technique 698 15.3 Fast Reanalysis Techniques 700 15.3.1 Incremental Response Approach 700 15.3.2 Basis Vector Approach 704 15.4 Derivatives of Static Displacements and Stresses 705 15.5 Derivatives of Eigenvalues and Eigenvectors 707 15.5.1 Derivatives of ;;i 707 15.5.2 Derivatives of Yi 708 15.6 Derivatives of Transient Response 709 15.7 Sensitivity of Optimum Solution to Problem Parameters 712 15.7.1 Sensitivity Equations Using Kuhn-Tucker Conditions 712 15.7.2 Sensitivity Equations Using the Concept of Feasible Direction 714 References and Bibliography 715 Review Questions 716 Problems 716 16 Multilevel and Multiobjective Optimization 721 16.1 Introduction 721 16.2 Multilevel Optimization 721 16.2.1 Basic Idea 721 16.2.2 Method 722 16.3 Parallel Processing 726 16.4 Multiobjective Optimization 729 16.4.1 Utility Function Method 730 16.4.2 Inverted Utility Function Method 730 16.4.3 Global Criterion Method 730 16.4.4 Bounded Objective Function Method 730 16.4.5 Lexicographic Method 731 16.4.6 Goal Programming Method 732 16.4.7 Goal Attainment Method 732 16.4.8 Game Theory Approach 733 16.5 Solutions Using MATLAB 735 References and Bibliography 735 Review Questions 736 Problems 737 17 Solution of Optimization Problems Using MATLAB 739 17.1 Introduction 739 17.2 Solution of General Nonlinear Programming Problems 740 17.3 Solution of Linear Programming Problems 742 17.4 Solution of LP Problems Using Interior Point Method 743 17.5 Solution of Quadratic Programming Problems 745 17.6 Solution of One-Dimensional Minimization Problems 746 17.7 Solution of Unconstrained Optimization Problems 746 17.8 Solution of Constrained Optimization Problems 747 17.9 Solution of Binary Programming Problems 750 17.10 Solution of Multiobjective Problems 751 References and Bibliography 755 Problems 755 A Convex and Concave Functions 761 B Some Computational Aspects of Optimization 767 B.1 Choice of Method 767 B.2 Comparison of Unconstrained Methods 767 B.3 Comparison of Constrained Methods 768 B.4 Availability of Computer Programs 769 B.5 Scaling of Design Variables and Constraints 770 B.6 Computer Programs for Modern Methods of Optimization 771 References and Bibliography 772 C Introduction to MATLAB (R) 773 C.1 Features and Special Characters 773 C.2 Defining Matrices in MATLAB 774 C.3 Creating m-Files 775 C.4 Optimization Toolbox 775 Answers to Selected Problems 777 Index 787