Optimization

vii

Contents

Preface ......................................................................................................................xi

Author .....................................................................................................................xv

1. Introduction .....................................................................................................1

1.1 Historical Review ..................................................................................1

1.2 Optimization Problem ..........................................................................3

1.3 Modeling of the Optimization Problem ............................................5

1.4 Solution with the Graphical Method ................................................ 11

1.5 Convexity .............................................................................................13

1.6 Gradient Vector, Directional Derivative, and Hessian Matrix ..... 16

1.7 Linear and Quadratic Approximations ...........................................23

1.8 Organization of the Book ...................................................................25

Chapter Highlights ........................................................................................27

Formulae Chart ..............................................................................................28

Problems ..........................................................................................................29

2. 1-D Optimization Algorithms ...................................................................35

2.1 Introduction .........................................................................................35

2.2 Test Problem .........................................................................................37

2.3 Solution Techniques ............................................................................38

2.3.1 Bisection Method ...................................................................38

2.3.2 Newton–Raphson Method ...................................................40

2.3.3 Secant Method ........................................................................42

2.3.4 Cubic Polynomial Fit .............................................................44

2.3.5 Golden Section Method ........................................................46

2.3.6 Other Methods .......................................................................47

2.4 Comparison of Solution Methods .....................................................49

Chapter Highlights ........................................................................................51

Formulae Chart ..............................................................................................52

Problems ..........................................................................................................52

3. Unconstrained Optimization .....................................................................55

3.1 Introduction .........................................................................................55

3.2 Unidirectional Search .........................................................................57

3.3 Test Problem .........................................................................................59

3.4 Solution Techniques ............................................................................60

3.4.1 Steepest Descent Method ......................................................62

3.4.2 Newton’s Method ...................................................................63

3.4.3 Modied Newton’s Method .................................................66

3.4.4 Levenberg–Marquardt Method ...........................................66

viii Contents

3.4.5 Fletcher–Reeves Conjugate Gradient Method ...................68

3.4.6 DFP Method ............................................................................70

3.4.7 BFGS Method ..........................................................................72

3.4.8 Powell Method ....................................................................... 74

3.4.9 Nelder–Mead Algorithm ......................................................75

3.5 Additional Test Functions ..................................................................78

3.5.1 Rosenbrock Function .............................................................78

3.5.2 Quadratic Function ................................................................79

3.5.3 Nonlinear Function ...............................................................81

3.5.4 Wood’s Function.....................................................................82

3.6 Application to Robotics ......................................................................83

Chapter Highlights ........................................................................................85

Formulae Chart ..............................................................................................86

Problems ..........................................................................................................87

4. Linear Programming ....................................................................................93

4.1 Introduction .........................................................................................93

4.2 Solution with the Graphical Method ................................................95

4.3 Standard Form of an LPP ...................................................................98

4.4 Basic Solution ..................................................................................... 103

4.5 Simplex Method ................................................................................105

4.5.1 Multiple Solutions ................................................................ 112

4.5.2 Degeneracy ........................................................................... 114

4.5.3 Two-Phase Method .............................................................. 116

4.5.4 Dual Simplex Method ......................................................... 121

4.6 Interior-Point Method .......................................................................125

4.7 Portfolio Optimization .....................................................................127

Chapter Highlights ...................................................................................... 131

Formulae Chart ............................................................................................133

Problems ........................................................................................................133

5. Guided Random Search Methods ........................................................... 139

5.1 Introduction ....................................................................................... 139

5.2 Genetic Algorithms ........................................................................... 140

5.2.1 Initialize Population ............................................................ 142

5.2.2 Fitness Evaluation ................................................................ 143

5.2.3 Reproduction ........................................................................ 143

5.2.4 Crossover and Mutation ..................................................... 147

5.2.5 Multimodal Test Functions ................................................ 148

5.3 Simulated Annealing ........................................................................154

5.4 Particle Swarm Optimization ..........................................................157

5.5 Other Methods .................................................................................. 160

5.5.1 Ant Colony Optimization ................................................... 160

5.5.2 Tabu Search ...........................................................................163

Chapter Highlights ...................................................................................... 164

ixContents

Formulae Chart ............................................................................................ 165

Problems ........................................................................................................ 166

6. Constrained Optimization ....................................................................... 169

6.1 Introduction ....................................................................................... 169

6.2 Optimality Conditions ..................................................................... 171

6.3 Solution Techniques .......................................................................... 175

6.3.1 Penalty Function Method ................................................... 176

6.4 Augmented Lagrange Multiplier Method ..................................... 182

6.5 Sequential Quadratic Programming ..............................................184

6.6 Method of Feasible Directions ........................................................190

6.6.1 Zoutendijk’s Method ........................................................... 191

6.6.2 Rosen’s Gradient Projection Method ................................. 192

6.7 Application to Structural Design ....................................................195

Chapter Highlights ...................................................................................... 196

Formulae Chart ............................................................................................ 197

Problems ........................................................................................................199

7. Multiobjective Optimization ...................................................................203

7.1 Introduction .......................................................................................203

7.2 Weighted Sum Approach .................................................................205

7.3 ε-Constraints Method ....................................................................... 210

7.4 Goal Programming ........................................................................... 212

7.5 Utility Function Method .................................................................. 214

7.6 Application ......................................................................................... 215

Chapter Highlights ......................................................................................220

Formulae Chart ............................................................................................220

Problems ........................................................................................................221

8. Geometric Programming ..........................................................................223

8.1 Introduction .......................................................................................223

8.2 Unconstrained Problem ...................................................................224

8.3 Dual Problem .....................................................................................229

8.4 Constrained Optimization ..............................................................231

8.5 Application .........................................................................................235

Chapter Highlights ......................................................................................238

Formulae Chart ............................................................................................238

Problems ........................................................................................................240

9. Multidisciplinary Design Optimization ...............................................243

9.1 Introduction .......................................................................................243

9.2 MDO Architecture ............................................................................245

9.2.1 Multidisciplinary Design Feasible ....................................247

9.2.2 Individual Discipline Feasible ...........................................248

9.2.3 Simultaneous Analysis and Design .................................. 249

x Contents

9.2.4 Collaborative Optimization ................................................251

9.2.5 Concurrent Subspace Optimization ..................................252

9.2.6 Bilevel Integrated System Synthesis ..................................252

9.3 MDO Framework ..............................................................................253

9.4 Response Surface Methodology ......................................................254

Chapter Highlights ......................................................................................257

Formulae Chart ............................................................................................258

Problems ........................................................................................................259

10. Integer Programming ................................................................................263

10.1 Introduction .......................................................................................263

10.2 Integer Linear Programming ..........................................................264

10.2.1 Gomory’s Cutting Plane Method .......................................265

10.2.2 Zero-One Problems .............................................................272

10.3 Integer Nonlinear Programming ....................................................277

10.3.1 Branch-and-Bound Method ................................................278

10.3.2 Evolutionary Method ..........................................................284

Chapter Highlights ......................................................................................286

Formulae Chart ............................................................................................286

Problems ........................................................................................................287

11. Dynamic Programming .............................................................................289

11.1 Introduction .......................................................................................289

11.2 Deterministic Dynamic Programming..........................................289

11.3 Probabilistic Dynamic Programming ............................................294

Chapter Highlights ......................................................................................296

Formula Chart .............................................................................................. 297

Problems ........................................................................................................297

Bibliography ........................................................................................................299

Appendix A: Introduction to MATLAB

®

......................................................309

Appendix B: MATLAB

®

Code ......................................................................... 321

Appendix C: Solutions to Chapter Problems ...............................................401

Index .....................................................................................................................437