Engineering optimization: theory and practice

Front Matter......Page 1
Preface......Page 3
Acknowledgments......Page 6
Table of Contents......Page 0
Table of Contents......Page 7
1.1 Introduction......Page 22
1.2 Historical Development......Page 24
1.3 Engineering Applications of Optimization......Page 25
1.4 Statement of an Optimization Problem......Page 26
1.4.1 Design Vector......Page 27
1.4.2 Design Constraints......Page 28
1.4.3 Constraint Surface......Page 29
1.4.4 Objective Function......Page 30
1.4.5 Objective Function Surfaces......Page 31
1.5.2 Classification Based on the Nature of the Design Variables......Page 36
1.5.3 Classification Based on the Physical Structure of the Problem......Page 38
1.5.4 Classification Based on the Nature of the Equations Involved......Page 41
1.5.5 Classification Based on the Permissible Values of the Design Variables......Page 52
1.5.6 Classification Based on the Deterministic Nature of the Variables......Page 53
1.5.7 Classification Based on the Separability of the Functions......Page 55
1.5.8 Classification Based on the Number of Objective Functions......Page 57
1.6 Optimization Techniques......Page 60
1.7 Engineering Optimization Literature......Page 61
References and Bibliography......Page 62
Review Questions......Page 66
Problems......Page 68
2.2 Single-Variable Optimization......Page 87
2.3 Multivariable Optimization with No Constraints......Page 93
2.3.2 Saddle Point......Page 99
2.4.1 Solution by Direct Substitution......Page 102
2.4.2 Solution by the Method of Constrained Variation......Page 104
2.4.3. Solution by the Method of Lagrange Multipliers......Page 113
2.5 Multivariable Optimization with Inequality Constraints......Page 122
2.5.2 Constraint Qualification......Page 127
References and Bibliography......Page 134
Review Questions......Page 135
Problems......Page 136
3.1 Introduction......Page 151
3.2 Applications of Linear Programming......Page 152
3.3 Standard Form of a Linear Programming Problem......Page 154
3.4 Geometry of Linear Programming Problems......Page 157
3.5 Definitions and Theorems......Page 161
3.6 Solution of a System of Linear Simultaneous Equations......Page 168
3.7 Pivotal Reduction of a General System of Equations......Page 170
3.8 Motivation of the Simplex Method......Page 174
3.9 Simplex Algorithm......Page 175
3.9.2 Improving a Nonoptimal Basic Feasible Solution......Page 176
3.10 Two Phases of the Simplex Method......Page 186
Review Questions......Page 194
Problems......Page 196
4.1 Introduction......Page 215
4.2 Revised Simplex Method......Page 216
4.3 Duality in Linear Programming......Page 232
4.3.2 General Primal-Dual Relations......Page 233
4.3.3 Primal-Dual Relations When the Primal Is in Standard Form......Page 234
4.3.5 Dual Simplex Method......Page 236
4.4 Decomposition Principle......Page 241
4.5 Sensitivity or Postoptimality Analysis......Page 251
4.5.1 Changes in the Right-Hand-Side Constants bi......Page 252
4.5.2 Changes in the Cost Coefficients cj......Page 258
4.5.3 Addition of New Variables......Page 260
4.5.4 Changes in the Constraint Coefficients aij......Page 261
4.5.5 Addition of Constraints......Page 264
4.6 Transportation Problem......Page 266
4.7 Karmarkar's Method......Page 269
4.7.2 Conversion of an LP Problem into the Required Form......Page 271
4.7.3 Algorithm......Page 274
4.8 Quadratic Programming......Page 277
References and Bibliography......Page 284
Review Questions......Page 285
Problems......Page 286
5.1 Introduction......Page 295
5.2 Unimodal Function......Page 301
5.3.1 Search with Fixed Step Size......Page 302
5.3.2 Search with Accelerated Step Size......Page 303
5.4 Exhaustive Search......Page 304
5.5 Dichotomous Search......Page 306
5.6 Interval Halving Method......Page 309
5.7 Fibonacci Method......Page 312
5.8 Golden Section Method......Page 319
5.9 Comparison of Elimination Methods......Page 321
Interpolation Methods......Page 322
5.10 Quadratic Interpolation Method......Page 324
5.11 Cubic Interpolation Method......Page 331
5.12.1 Newton Method......Page 339
5.12.2 Quasi-Newton Method......Page 342
5.12.3 Secant Method......Page 344
5.13.1 How to Make the Methods Efficient and More Reliable......Page 347
5.13.3 Comparison of Methods......Page 348
Review Questions......Page 349
Problems......Page 350
6.1 Introduction......Page 356
6.1.1 Classification of Unconstrained Minimization Methods......Page 359
6.1.3 Rate of Convergence......Page 360
6.1.4 Scaling of Design Variables......Page 362
6.2.1 Random Jumping Method......Page 366
6.2.2 Random Walk Method......Page 368
6.2.3 Random Walk Method with Direction Exploitation......Page 370
6.3 Grid Search Method......Page 371
6.4 Univariate Method......Page 373
6.5 Pattern Directions......Page 376
6.6 Hooke and Jeeves' Method......Page 377
6.7 Powell's Method......Page 380
6.7.1 Conjugate Directions......Page 381
6.7.2 Algorithm......Page 385
6.9 Simplex Method......Page 391
6.9.1 Reflection......Page 392
6.9.2 Expansion......Page 395
6.9.3 Contraction......Page 396
6.10 Gradient of a Function......Page 400
6.10.1 Evaluation of the Gradient......Page 403
6.10.2 Rate of Change of a Function Along a Direction......Page 404
6.11 Steepest Descent (Cauchy) Method......Page 405
6.12 Conjugate Gradient (Fletcher-Reeves) Method......Page 407
6.12.1 Development of the Fletcher-Reeves Method......Page 408
6.12.2 Fletcher-Reeves Method......Page 410
6.13 Newton's Method......Page 413
6.14 Marquardt Method......Page 416
6.15 Quasi-Newton Methods......Page 418
6.15.1 Rank 1 Updates......Page 419
6.15.2 Rank 2 Updates......Page 421
6.16 Davidon-Fletcher-Powell Method......Page 423
6.17 Broydon-Fletcher-Goldfarb-Shanno Method......Page 429
6.18 Test Functions......Page 432
References and Bibliography......Page 435
Review Questions......Page 437
Problems......Page 439
7.2 Characteristics of a Constrained Problem......Page 452
7.3 Random Search Methods......Page 456
7.4 Complex Method......Page 457
7.5 Sequential Linear Programming......Page 460
7.6 Basic Approach in the Methods of Feasible Directions......Page 467
7.7 Zoutendijk's Method of Feasible Directions......Page 468
7.7.1 Direction-Finding Problem......Page 470
7.7.2 Determination of Step Length......Page 473
7.7.3 Termination Criteria......Page 476
7.8 Rosen's Gradient Projection Method......Page 479
7.8.1 Determination of Step Length......Page 483
7.9 Generalized Reduced Gradient Method......Page 489
7.10.1 Derivation......Page 501
7.10.2 Solution Procedure......Page 504
7.11 Transformation Techniques......Page 509
7.12 Basic Approach of the Penalty Function Method......Page 511
7.13 Interior Penalty Function Method......Page 514
7.14 Convex Programming Problem......Page 526
7.15 Exterior Penalty Function Method......Page 527
7.16 Extrapolation Technique in the Interior Penalty Function Method......Page 532
7.16.1 Extrapolation of the Design Vector X......Page 533
7.16.2 Extrapolation of the Function f......Page 535
7.17.1 Linear Extended Penalty Function Method......Page 537
7.17.2 Quadratic Extended Penalty Function Method......Page 538
7.18.1 Interior Penalty Function Method......Page 540
7.19.1 Parametric Constraint......Page 542
7.19.2 Handling Parametric Constraints......Page 544
7.20.1 Equality-Constrained Problems......Page 546
7.20.2 Inequality-Constrained Problems......Page 548
7.20.3 Mixed Equality-Inequality Constrained Problems......Page 550
7.21.1 Perturbing the Design Vector......Page 552
7.21.2 Testing the Kuhn-Tucker Conditions......Page 553
7.22 Test Problems......Page 554
7.22.1 Design of a Three-Bar Truss......Page 555
7.22.2 Design of a Twenty-Five-Bar Space Truss......Page 556
7.22.3 Welded Beam Design......Page 559
7.22.4 Speed Reducer (Gear Train) Design......Page 561
7.22.5 Heat Exchanger Design......Page 562
References and Bibliography......Page 563
Review Questions......Page 565
Problems......Page 568
8.2 Posynomial......Page 581
8.3 Unconstrained Minimization Problem......Page 582
8.4 Solution of an Unconstrained Geometric Programming Problem Using Differential Calculus......Page 583
8.5 Solution of an Unconstrained Geometric Programming Problem Using Arithmetic-Geometric Inequality......Page 591
8.6 Primal-Dual Relationship and Sufficiency Conditions in the Unconstrained Case......Page 592
8.7 Constrained Minimization......Page 600
8.8 Solution of a Constrained Geometric Programming Problem......Page 601
8.9 Primal and Dual Programs in the Case of Less-Than Inequalities......Page 602
8.10 Geometric Programming with Mixed Inequality Constraints......Page 610
8.11 Complementary Geometric Programming......Page 613
8.12 Applications of Geometric Programming......Page 619
References and Bibliography......Page 634
Review Questions......Page 636
Problems......Page 637
9.1 Introduction......Page 641
9.2.1 Definition and Examples......Page 642
9.2.2 Representation of a Multistage Decision Process......Page 643
9.2.3 Conversion of a Nonserial System to a Serial System......Page 645
9.2.4 Types of Multistage Decision Problems......Page 646
9.3 Concept of Suboptimization and the Principle of Optimality......Page 647
9.4 Computational Procedure in Dynamic Programming......Page 651
9.5 Example Illustrating the Calculus Method of Solution......Page 655
9.6 Example Illustrating the Tabular Method of Solution......Page 660
9.7 Conversion of a Final Value Problem into an Initial Value Problem......Page 666
9.8 Linear Programming as a Case of Dynamic Programming......Page 669
9.9 Continuous Dynamic Programming......Page 674
9.10.1 Design of Continuous Beams......Page 678
9.10.2 Optimal Layout (Geometry) of a Truss......Page 679
9.10.3 Optimal Design of a Gear Train......Page 680
9.10.4 Design of a Minimum-Cost Drainage System......Page 681
References and Bibliography......Page 683
Review Questions......Page 684
Problems......Page 685
10.1 Introduction......Page 692
10.2 Graphical Representation......Page 693
10.3.1 Concept of a Cutting Plane......Page 695
10.3.2 Gomory's Method for All-Integer Programming Problems......Page 697
10.3.3 Gomory's Method for Mixed-Integer Programming Problems......Page 704
10.4 Balas' Algorithm for Zero-One Programming Problems......Page 710
10.5 Integer Polynomial Programming......Page 712
10.5.1 Representation of an Integer Variable by an Equivalent System of Binary Variables......Page 713
10.5.2 Conversion of a Zero-One Polynomial Programming Problem into a Zero-One LP Problem......Page 714
10.6 Branch-and-Bound Method......Page 715
10.7 Sequential Linear Discrete Programming......Page 722
10.8 Generalized Penalty Function Method......Page 726
References and Bibliography......Page 732
Review Questions......Page 733
Problems......Page 734
11.1 Introduction......Page 740
11.2.1 Definition of Probability......Page 741
11.2.2 Random Variables and Probability Density Functions......Page 742
11.2.3 Mean and Standard Deviation......Page 744
11.2.4 Function of a Random Variable......Page 747
11.2.5 Jointly Distributed Random Variables......Page 748
11.2.6 Covariance and Correlation......Page 749
11.2.7 Functions of Several Random Variables......Page 750
11.2.8 Probability Distributions......Page 752
11.3 Stochastic Linear Programming......Page 757
11.4.1 Objective Function......Page 763
11.4.2 Constraints......Page 764
11.5 Stochastic Geometric Programming......Page 771
11.6.1 Optimality Criterion......Page 773
11.6.2 Multistage Optimization......Page 774
11.6.3 Stochastic Nature of the Optimum Decisions......Page 778
References and Bibliography......Page 783
Review Questions......Page 784
Problems......Page 786
12.1 Introduction......Page 793
12.2 Separable Programming......Page 794
12.2.1 Transformation of a Nonlinear Function to Separable Form......Page 795
12.2.2 Piecewise Linear Approximation of a Nonlinear Function......Page 797
12.2.3 Formulation of a Separable Nonlinear Programming Problem......Page 799
12.3 Multiobjective Optimization......Page 804
12.3.1 Utility Function Method......Page 805
12.3.4 Bounded Objective Function Method......Page 806
12.3.6 Goal Programming Method......Page 807
12.4.1 Introduction......Page 808
12.4.2 Problem of Calculus of Variations......Page 809
12.4.3 Lagrange Multipliers and Constraints......Page 816
12.5 Optimal Control Theory......Page 820
12.5.1 Necessary Conditions for Optimal Control......Page 821
12.5.2 Necessary Conditions for a General Problem......Page 824
12.6 Optimality Criteria Methods......Page 826
12.6.1 Optimality Criteria with a Single Displacement Constraint......Page 827
12.6.2 Optimality Criteria with Multiple Displacement Constraints......Page 828
12.6.3 Reciprocal Approximations......Page 829
12.7.1 Introduction......Page 832
12.7.2 Representation of Design Variables......Page 834
12.7.3 Representation of Objective Function and Constraints......Page 835
12.7.4 Genetic Operators......Page 836
12.8 Simulated Annealing......Page 837
12.9 Neural-Network-Based Optimization......Page 840
12.10.1 Fuzzy Set Theory......Page 844
12.10.2 Optimization of Fuzzy Systems......Page 847
12.10.3 Computational Procedure......Page 849
References and Bibliography......Page 850
Review Questions......Page 853
Problems......Page 855
13.2.1 Reduced Basis Technique......Page 862
13.2.2 Design Variable Linking Technique......Page 863
13.3.1 Incremental Response Approach......Page 865
13.3.2 Basis Vector Approach......Page 871
13.4 Derivatives of Static Displacements and Stresses......Page 873
13.5.1 Derivatives of lambda i......Page 874
13.5.2 Derivatives of Yi......Page 875
13.6 Derivatives of Transient Response......Page 877
13.7.1 Sensitivity Equations Using Kuhn-Tucker Conditions......Page 880
13.7.2 Sensitivity Equations Using the Concept of Feasible Direction......Page 883
13.8.1 Basic Idea......Page 884
13.8.2 Method......Page 885
13.9 Parallel Processing......Page 890
References and Bibliography......Page 893
Review Questions......Page 894
Problems......Page 895
Appendix A: Convex and Concave Functions......Page 902
Appendix B: Some Computational Aspects of Optimization......Page 908
Answers to Selected Problems......Page 914
A......Page 921
C......Page 922
D......Page 926
F......Page 928
G......Page 930
I......Page 932
J......Page 933
L......Page 934
M......Page 935
N......Page 936
O......Page 937
P......Page 938
Q......Page 940
R......Page 941
S......Page 942
T......Page 945
V......Page 947
Z......Page 948