Applied Optimization with MATLAB Programming Book

Preface xiii

1 Introduction 1

1.1 Optimization Fundamentals 3

1.1.1 Elements of Problem Formulation 4

1.1.2 Mathematical Modeling 11

1.1.3 Nature of Solution 18

1.1.4 Characteristics of the Search Procedure 23

1.2 Introduction to Matlab 27

1.2.1 Why Matlab? 28

1.2.2 Matlab Installation Issues 29

1.2.3 Using Matlab the First Time 31

1.2.4 An Interactive Session 33

1.2.5 Using the Editor 36

1.2.6 Creating a Code Snippet 41

1.2.7 Creating a Program 46

1.2.8 Application Bibliography 49

Problems 51

2 Graphical Optimization 67

2.1 Problem Definition 68

2.1.1 Example 2.1 68

2.1.2 Format for the Graphical Display 70

2.2 Graphical Solution 70

2.2.1 Matlab High-Level Graphics Functions 71

2.2.2 Matlab Plot Editor 73

2.2.3 Example 2.1-Graphical Solution 74

2.3 Additional Examples 80

2.3.1 Example 2.2-Different Ways of Displaying Information 80

2.3.2 Example 2.3-Flagpole Design 86

2.3.3 Example 2.4-Fin Design for Heat Transfer Application 97

2.3.4 Example 2.5-Shipping Container with Three Design Variables 106

2.4 Additional Matlab Graphics 118

2.4.1 Handle Graphics 118

2.4.2 Interactive Contour Plots 120

References 126

Problems 126

3 Linear Programming 130

3.1 Problem Definition 131

3.1.1 Standard Format 132

3.1.2 Modeling Issues 136

3.2 Graphical Solution 145

3.2.1 Example 3.1 147

3.2.2 Characteristics of the Solution 150

3.2.3 Different Solution Types 153

3.3 Numerical Solution-The Simplex Method 154

3.3.1 Features of the Simplex Method 154

3.3.2 Application of Simplex Method 156

3.3.3 Solution Using Matlab Code 159

3.3.4 Solution Using Matlab's Optimization Toolbox 161

3.4 Additional Examples162

3.4.1 Example 3.2-Transportation Problem 162

3.4.2 Example 3.3-Equality Constraints and Unrestricted Variables 169

3.4.3 Example 3.4-A Four-Variable Problem 175

3.5 Additional Topics in Linear Programming 182

3.5.1 Primal and Dual Problem 182

3.5.2 Example 3.5 183

3.5.3 Sensitivity Analysis 195

References 198

Problems 198

4 Nonlinear Programming 203

4.1 Problem Definition 204

4.1.1 Problem Formulation-Example 4.1 205

4.1.2 Additional Optimization Problems 207

4.2 Mathematical Concepts 209

4.2.1 Symbolic Computation Using Matlab 209

4.2.2 Basic Mathematical Concepts 213

4.2.3 Taylor's Theorem/Series 221

4.3 Analytical Conditions 224

4.3.1 Unconstrained Problem 225

4.3.2 Equality-Constrained Problem 2 230

4.3.3 Equality-Constrained Problem 3 236

4.3.4 Inequality-Constrained Optimization 239

4.3.5 A General Optimization Problem 246

4.4 Examples 249

4.4.1 Example 4.2-Curve Fitting 249

4.4.2 Example 4.3-Flagpole Problem 251

4.4.3 Additional Topics 256

References 258

Problems 259

5 Numerical Techniques - The One-Dimensional Problem 261

5.1 Problem Definition 262

5.1.1 Constrained One-Dimensional Problem 262

5.1.2 Necessary and Sufficient Conditions 263

5.1.3 Solution to the Examples 263

5.2 Numerical Techniques 265

5.2.1 Features of the Numerical Techniques 265

5.2.2 Newton-Raphson Technique 266

5.2.3 Bisection Technique 269

5.2.4 Polynomial Approximation 271

5.2.5 Golden Section Method 276

5.3 Importance of the One-Dimensional Problem 279

5.4 Additional Examples 281

5.4.1 Example 5.3-Golden Section Method for Many Variables 281

5.4.2 Example 5.4-Two-Point Boundary Value Problem 283

5.4.3 Example 5.5-Root Finding with Golden Section 286

References 288

Problems 288

6 Numerical Techniques for Unconstrained Optimization 290

6.1 Problem Definition 291

6.1.1 Example 6.1 291

6.1.2 Graphical Solution 291

6.1.3 Necessary and Sufficient Conditions 292

6.1.4 Elements of a Numerical Technique 293

6.2 Numerical Technique-Nongradient Methods 294

6.2.1 Scan and Zoom 294

6.2.2 Random Walk 296

6.2.3 Pattern Search 299

6.2.4 Powell's Method 302

6.3 Numerical Technique-Gradient-Based Methods 306

6.3.1 Steepest Descent Method 306

6.3.2 Conjugate Gradient (Fletcher-Reeves) Method 310

6.3.3 Davidon-Fletcher-Powell Method 313

6.3.4 Broydon-Fletcher-Goldfarb-Shanno (BFGS) Method 317

6.4 Numerical Technique-Second Order 320

6.4.1 Modified Newton's Method 321

6.5 Additional Examples 323

6.5.1 Example 6.2-Rosenbrock Problem 323

6.5.2 Example 6.3-Three-Dimensional Flow near a Rotating Disk 326

6.5.3 Example 6.4-An Electrical Engineering Problem 329

6.6 Summary 332

References 333

Problems 333

7 Numerical Techniques for Constrained Optimization 337

7.1 Problem Definition 338

7.1.1 Problem Formulation-Example 7.1 339

7.1.2 Necessary Conditions 340

7.1.3 Elements of a Numerical Technique 342

7.2 Indirect Methods for Constrained Optimization 343

7.2.1 Exterior Penalty Function (EPF) Method 344

7.2.2 Augmented Lagrange Multiplier Method 349

7.3 Direct Methods for Constrained Optimization 354

7.3.1 Constrained Scan and Zoom 354

7.3.2 Expansion of Functions 359

7.3.3 Sequential Linear Programming (SLP) 363

7.3.4 Sequential Quadratic Programming (SQP) 369

7.3.5 Generalized Reduced Gradient (GRG) Method 377

7.3.6 Sequential Gradient Restoration Algorithm (SGRA) 383

7.4 Additional Examples 389

7.4.1 Example 7.2-Flagpole Problem 390

7.4.2 Example 7.3-I-Beam Design 394

7.4.3 Example 7.4-Box Design 398

References 400

Problems 401

8 Discrete Optimization 403

8.1 Concepts in Discrete Programming 405

8.1.1 Problem Relaxation 406

8.1.2 Discrete Optimal Solution 407

8.2 Discrete Optimization Techniques 409

8.2.1 Exhaustive Enumeration 411

8.2.2 Branch and Bound 414

8.2.3 Dynamic Programming 422

8.3 Additional Examples 427

8.3.1 Example 8.4-I-Beam Design-Single Variable? 427

8.3.2 Zero-One Integer Programming 430

References 435

Problems 435

9 Global Optimization 437

9.1 Problem Definition 438

9.1.1 Global Minimum 439

9.1.2 Nature of the Solution 441

9.1.3 Elements of a Numerical Technique 443

9.2 Numerical Techniques and Additional Examples 445

9.2.1 Simulated Annealing (SA) 445

9.2.2 Genetic Algorithm 457

References 467

Problems 468

10 Optimization Toolbox from Matlab 469

10.1 The Optimization Toolbox 470

10.1.1 Programs 473

10.1.2 Using Programs 476

10.1.3 Setting Optimization Parameters 479

10.2 Examples 481

10.2.1 Linear Programming 481

10.2.2 Quadratic Programming 482

10.2.3 Unconstrained Optimization 484

10.2.4 Constrained Optimization 485

References 488

11 Hybrid Mathematics - An Application 489

11.1 Central Idea 490

11.1.1 Bezier Function-2D 490

11.1.2 Bezier Function-3D 493

11.1.3 Data Decoupling 495

11.1.4 Derivatives 495

11.2 Data-Handling Examples 496

11.2.1 Data Fitting with Bezier Functions 496

11.2.2 Optimum Bezier Solution 497

11.2.3 Example 11.1-Smooth Data at Equidistant Intervals 498

11.2.4 Example 11.2-Data Fitting Using Bezier Surface 500

11.3 Solutions to Differential Systems 503

11.3.1 Flow over a Rotating Disk 504

11.3.2 Two-Dimensional Flow Entering a Channel 509

11.4 Summary 517

References 518

Index 521