Preface xvii
Acknowledgment xxi
About the Author xxiii
About the Companion Website xxv
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® 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
