Engineering Optimization: Theory and Practice, 5/Ed > 이산수학

TABLE OF CONTENTS

Preface

Acknowledgment

About the Companion Website

1. Introduction to Optimization

1.1 Introduction

1.2 Historical Development

1.3 Engineering Applications of Optimization

1.4 Statement of an Optimization Problem

1.4.1 Design Vector

1.4.2 Design Constraints

1.4.3 Constraint Surface

1.4.4 Objective Function

1.4.5 Objective Function Surfaces

1.5 Classification of Optimization Problems

1.5.1 Classification Based on the Existence of Constraints

1.5.2 Classification Based on the Nature of the Design Variables

1.5.3 Classification Based on the Physical Structure of the Problem

1.5.4 Classification Based on the Nature of the Equations Involved

1.5.5 Classification Based on the Permissible Values of the Design Variables

1.5.6 Classification Based on the Deterministic Nature of the Variables

1.5.7 Classification Based on the Separability of the Functions

1.5.8 Classification Based on the Number of Objective Functions

1.6 Classification Based on the Number of Objective Functions

1.7 Engineering Optimization Literature

References & Bibliography

Review Questions

Problems

2 Classical Optimization Techniques

2.1 Introduction

2.2 Single-Variable Optimization

2.3 Multivariable Optimization with No Constraints

2.3.1 Semidefinite Case

2.3.2 Saddle Point

2.4 Multivariable Optimization with Equality Constraints

2.4.1 Solution by Direct Substitution

2.4.2 Solution by the Method of Constrained Variation

2.4.3 Solution by the Method of Lagrange Multipliers

2.5 Multivariable Optimization with Inequality Constraints

2.5.1 Kuhn–Tucker Conditions

2.5.2 Constraint Qualification

2.6 Convex Programming Problem

References and Bibliography

Review Questions

Problems

3. Linear Programming I: Simplex Method

3.1 Introduction

3.2 Applications of Linear Programming

3.3 Standard Form of a Linear Programming Problem

3.4 Geometry of Linear Programming Problems

3.5 Definitions and Theorems

3.6 Solution of a System of Linear Simultaneous Equations

3.7 Pivotal Reduction of a General System of Equations

3.8 Motivation of the Simplex Method

3.9 Simplex Algorithm

3.10 Two Phases of the Simplex Method

References and Bibliography

Review Questions

Problems

4. Linear Programming II: Additional Topics and Extensions

4.1 Introduction

4.2 Revised Simplex Method

4.3 Duality in Linear Programming

4.3.1 Symmetric Primal–Dual Relations

4.3.2 General Primal–Dual Relations

4.3.3 Primal–Dual Relations When the Primal Is in Standard Form

4.3.4 Duality Theorems

4.3.5 Dual Simplex Method

4.4 Decomposition Principle

4.5 Sensitivity or Postoptimality Analysis

4.5.1 Changes in the Right-Hand-Side Constants bi

4.5.2 Changes in the Cost Coefficients cj

4.5.3 Addition of New Variables

4.5.4 Changes in the Constraint Coefficients aij

4.5.5 Addition of Constraints

4.6 Transportation Problem

4.7 Karmarkar’s Interior Method

4.7.1 Statement of the Problem

4.7.2 Conversion of an LP Problem into the Required Form

4.7.3 Algorithm

4.8 Quadratic Programming

Solutions Using Matlab

References and Bibliography

Review Questions

Problems

5. Nonlinear Programming I: One-Dimensional Minimization Methods

5.1 Introduction

5.2 Unimodal Function

5.3 Unrestricted Search

5.4 Exhaustive Search

5.5 Dichotomous Search

5.6 Interval Halving Method

5.7 Fibonacci Method

5.8 Golden Section Method

5.9 Comparison of Elimination Methods

5.10 Quadratic Interpolation Method

5.11 Cubic Interpolation Method

5.12 Direct Root Methods

5.12.1 Newton Method

5.12.2 Quasi-Newton Method

5.12.3 Secant Method

5.13 Practical Considerations

5.13.1 How to Make the Methods Efficient and More Reliable

5.13.2 Implementation in Multivariable Optimization Problems

5.13.3 Comparison of Methods

Solutions Using Matlab

References and Bibliography

Review Questions

Problems

6. Nonlinear Programming II: Unconstrained Optimization Techniques

6.1 Introduction

6.1.1 Classification of Unconstrained Minimization Methods

6.1.2 General Approach

6.1.3 Rate of Convergence

6.1.4 Scaling of Design Variables

6.2 Random Search Methods

6.2.1 Random Jumping Method

6.2.2 Random Walk Method

6.2.3 Random Walk Method with Direction Exploitation

6.2.4 Advantages of Random Search Methods

6.3 Grid Search Method

6.4 Univariate Method

6.5 Pattern Directions

6.6 Powell’s Method

6.6.1 Conjugate Directions

6.6.2 Algorithm

6.7 Simplex Method

6.7.1 Reflection

6.7.2 Expansion

6.7.3 Contraction

6.8 Gradient of a Function

6.8.1 Evaluation of the Gradient

6.8.2 Rate of Change of a Function along a Direction

6.9 Steepest Descent (Cauchy) Method

6.10 Conjugate Gradient (Fletcher–Reeves) Method

6.10.1 Development of the Fletcher–Reeves Method

6.10.2 Fletcher–Reeves Method

6.11 Newton’s Method

6.12 Marquardt Method

6.13 Quasi-Newton Methods

6.13.1 Rank 1 Updates

6.14 Davidon–Fletcher–Powell Method

6.15 Broyden–Fletcher–Goldfarb–Shanno Method

6.16 Test Functions

Solutions Using Matlab

References and Bibliography

Review Questions

Problems

7. Nonlinear Programming III: Constrained Optimization Techniques

7.1 Introduction

7.2 Characteristics of a Constrained Problem

7.3 Random Search Methods

7.4 Complex Method

7.5 Sequential Linear Programming

7.6 Basic Approach in the Methods of Feasible Directions

7.7 Zoutendijk’s Method of Feasible Directions

7.7.1 Direction-Finding Problem

7.7.2 Determination of Step Length

7.7.3 Termination Criteria

7.8 Rosen’s Gradient Projection Method

7.8.1 Determination of Step Length

7.9 Generalized Reduced Gradient Method

7.10 Sequential Quadratic Programming

7.10.1 Derivation

7.10.2 Solution Procedure

7.11 Transformation Techniques

7.12 Basic Approach of the Penalty Function Method

7.13 Interior Penalty Function Method

7.14 Convex Programming Problem

7.15 Exterior Penalty Function Method

7.16 Extrapolation Techniques in the Interior Penalty Function Method

7.16.1 Extrapolation of the Design Vector X

7.16.2 Extrapolation of the Function f

7.17 Extended Interior Penalty Function Methods

17.1 Linear Extended Penalty Function Method

7.17.2 Quadratic Extended Penalty Function Method

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

7.18.1 Interior Penalty Function Method

7.18.2 Exterior Penalty Function Method

7.19 Penalty Function Method for Parametric Constraints

7.19.1 Parametric Constraint

7.19.2 Handling Parametric Constraints

7.20 Augmented Lagrange Multiplier Method

7.20.1 Equality-Constrained Problems

7.20.2 Inequality-Constrained Problems

7.20.3 Mixed Equality–Inequality-Constrained Problems

7.21 Checking the Convergence of Constrained Optimization Problems

7.21.1 Perturbing the Design Vector

7.21.2 Testing the Kuhn–Tucker Conditions

7.22 Test Problems

7.22.1 Design of a Three-Bar Truss

7.22.2 Design of a Twenty-Five-Bar Space Truss

7.22.3 Welded Beam Design

7.22.4 Speed Reducer (Gear Train) Design

7.22.5 Heat Exchanger Design [7.42]

Solutions Using Matlab

References and Bibliography

Review Questions

Problems

8. Geometric Programming

8.1 Introduction

8.2 Posynomial

8.3 Unconstrained Minimization Problem

8.4 Solution of an Unconstrained Geometric Programming Program Using Differential Calculus

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

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

8.7 Constrained Minimization

8.8 Solution of a Constrained Geometric Programming Problem

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

8.10 Geometric Programming with Mixed Inequality Constraints

8.11 Complementary Geometric Programming

8.12 Applications of Geometric Programming

References and Bibliography

9. Dynamic Programming

9.1 Introduction

9.2 Multistage Decision Processes

9.2.1 Definition and Examples

9.2.2 Representation of a Multistage Decision Process

9.2.3 Conversion of a Nonserial System to a Serial System

9.2.4 Types of Multistage Decision Problems

9.3 Concept of Suboptimization and Principle of Optimality

9.4 Computational Procedure in Dynamic Programming

9.5 Example Illustrating the Calculus Method of Solution

9.6 Example Illustrating the Tabular Method of Solution

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

9.8 Linear Programming as a Case of Dynamic Programming

9.9 Continuous Dynamic Programming

9.10 Additional Applications

9.10.1 Design of Continuous Beams

9.10.2 Optimal Layout (Geometry) of a Truss

9.10.3 Optimal Design of a Gear Train

9.10.4 Design of a Minimum-Cost Drainage System

References and Bibliography

Review Questions

Problems

10. Integer Programming

10.1 Introduction

10.2 Graphical Representation

10.3 Gomory’s Cutting Plane Method

10.4 Balas’ Algorithm for Zero–One Programming Problems

10.5 Integer Polynomial Programming

10.5.1 Representation of an Integer Variable by an Equivalent System of Binary Variables

10.5.2 Conversion of a Zero–One Polynomial Programming Problem into a Zero–One LP Problem

10.6 Branch-and-Bound Method

10.7 Sequential Linear Discrete Programming

10.8 Generalized Penalty Function Method

Solutions Using Matlab

References and Bibliography

Review Questions

Problems

11. Stochastic Programming

11.2 Basic Concepts of Probability Theory

11.2.1 Definition of Probability

11.2.2 Random Variables and Probability Density Functions

11.2.3 Mean and Standard Deviation

11.2.4 Function of a Random Variable

11.2.5 Jointly Distributed Random Variables

11.2.6 Covariance and Correlation

11.2.7 Functions of Several Random Variables

11.2.8 Probability Distributions

11.2.9 Central Limit Theorem

11.3 Stochastic Linear Programming

11.4 Stochastic Nonlinear Programming

11.4.1 Objective Function

11.4.2 Constraints

11.5 Stochastic Geometric Programming

References and Bibliography

Review Questions

Problems

12. Optimal Control and Optimality Criteria Methods

12.1 Introduction

12.2 Calculus of Variations

12.2.1 Introduction

12.2.2 Problem of Calculus of Variations

12.2.3 Lagrange Multipliers and Constraints

12.3 Optimal Control Theory

12.3.1 Necessary Conditions for Optimal Control

12.3.2 Necessary Conditions for a General Problem

12.4 Optimality Criteria Methods

12.4.1 Optimality Criteria with a Single Displacement Constraint

12.4.2 Optimality Criteria with Multiple Displacement Constraints

12.4.3 Reciprocal Approximations

References and Bibliography

Review Questions

Problems

13. Modern Methods of Optimization

13.1 Introduction

13.2 Genetic Algorithms

13.2.1 Introduction

13.2.2 Representation of Design Variables

13.2.3 Representation of Objective Function and Constraints

13.2.4 Genetic Operators

13.2.5 Algorithm

13.2.6 Numerical Results

13.3 Simulated Annealing

13.3.2 Procedure

13.3.3 Algorithm

13.3.4 Features of the Method

13.3.5 Numerical Results

13.4 Particle Swarm Optimization

13.4.1 Introduction

13.4.2 Computational Implementation of PSO

13.4.3 Improvement to the Particle Swarm Optimization Method

13.4.4 Solution of the Constrained Optimization Problem

13.5 Ant Colony Optimization

13.5.1 Basic Concept

13.5.2 Ant Searching Behavior

13.5.3 Path Retracing and Pheromone Updating

13.5.4 Pheromone Trail Evaporation

13.5.5 Algorithm

13.6 Optimization of Fuzzy Systems

13.6.1 Fuzzy Set Theory

13.6.2 Optimization of Fuzzy Systems

13.6.3 Computational Procedure

13.7 Neural-Network-Based Optimization

References and Bibliography

Review Questions

Problems

14. Metaheuristic Optimization Methods

14.1 Definitions

14.2 Metaphors associated with metaheuristic optimization methods

14.3 Details of Representative Mataheuristic Algorithms

14.3.1 Crow search algorithm

14.3.2 Firefly Optimization Algorithm (FOA)

14.3.3 Harmony Search Algorithm

14.3.4 Teaching-Learning-Based Optimization (TLBO)

14.3.5 Honey Bee Swarm Optimization Algorithm

References

Review Questions

15. Practical Aspects of Optimization

15.1 Introduction

15.2 Reduction of Size of an Optimization Problem

15.2.1 Reduced Basis Technique

15.2.2 Design Variable Linking Technique

15.3 Fast Reanalysis Techniques

15.3.1 Incremental Response Approach

15.3.2 Basis Vector Approach

15.4 Derivatives of Static Displacements and Stresses

15.5 Derivatives of Eigenvalues and Eigenvectors

15.5.1 Derivatives of λi

15.5.2 Derivatives of Yi

15.6 Derivatives of Transient Response

15.7 Sensitivity of Optimum Solution to Problem Parameters

15.7.1 Sensitivity Equations Using Kuhn–Tucker Conditions

References

Review Questions

Problems

16. Multilevel and Multiobjective Optimization

16.1 Introduction

16.2 Multilevel Optimization

16.2.1 Basic Idea

16.2.1 Basic Idea

16.3 Parallel Processing

16.4 Multiobjective Optimization

16.4.1 Utility Function Method

16.4.2 Inverted Utility Function Method

16.4.3 Global Criterion Method

16.4.4 Bounded Objective Function Method

16.4.5 Lexicographic Method

16.4.6 Goal Programming Method

16.4.7 Goal Attainment Method

16.4.8 Game Theory Approach

Solutions Using Matlab

References and Bibliography

Review Questions

Problems

17. Solution of Optimization Problems Using MATLAB

17.1 Introduction

17.2 Solution of General Nonlinear Programming Problems

17.3 Solution of Linear Programming Problems

17.4 Solution of Lp Problems Using Interior Point Method

17.5 Solution of Quadratic Programming Problems

17.6 Solution of One-Dimensional Minimization Problems

17.7 Solution of Unconstrained Optimization Problems

17.8 Matlab Solution of Constrained Optimization Problems

17.9 Solution of Binary Programming Problems Using Matlab

17.10 Solution of Multiobjective Problems Using Matlab

References

Problems

Index