Optimization : foundations and applications / Ronald E. Miller.

Format:

Book

Author/Creator:

Miller, Ronald E.

Language:

English

Subjects (All):

Mathematical optimization.

Physical Description:

xvvii, 653 pages : illustrations ; 26 cm

Place of Publication:

New York : Wiley, 2000.

Summary:

An Instructor's Manual presenting detailed solutions to all the problems in the book is available upon request from the Wiley editorial department.

Contents:

Part I Foundations: Linear Methods 1

1 Matrix Algebra 3

1.1 Matrices: Definition and General Representation 4

1.2 The Algebra of Matrices 4

1.2.1 Matrix Operations: Addition and Subtraction 4

1.2.2 Matrix Definitions: Equality and the Null Matrix 5

1.2.3 Matrix Operations: Multiplication 5

1.2.4 Matrix Definitions: The Identity Matrix 7

1.2.5 Matrix Operations: Transposition 8

1.2.6 Matrix Operations: Partitioning 9

1.2.7 Additional Definitions and Operations 9

1.3 Linear Equation Systems: A Preview 11

1.3.1 Matrix Operations: Division 14

1.3.2 The Geometry of Simple Equation Systems: Solution Possibilities 26

1.4 The Geometry of Vectors 29

1.4.1 Linear Combinations of Vectors 29

1.4.2 The Geometry of Multiplication by a Scalar 31

1.4.3 The Geometry of Addition (and Subtraction) 32

1.4.4 Additional Vector Geometry 32

1.5 Linear Dependence and Independence 35

1.6 Quadratic Forms 39

1.6.1 Basic Structure of Quadratic Forms 40

1.6.2 Rewritten Structure of Quadratic Forms 41

1.6.3 Principal Minors and Permutation Matrices 42

1.6.4 The Sign of a Quadratic Form 48

2 Systems of Linear Equations 53

2.1 The 2 [times] 2 Case Again 54

2.2 The 3 [times] 3 Case 58

2.2.1 Numerical Illustrations 59

2.2.2 Summary of 2 [times] 2 and 3 [times] 3 Solution Possibilities 62

2.3 The n [times] n Case 62

2.3.1 Consistent Systems [[rho](A) = [rho](A|B)] 62

2.3.2 Inconsistent Systems [[rho](A) [not equal rho](A|B)] 64

2.4 More Matrix Algebra: Inverses for Nonsquare Matrices 65

2.4.1 The m > n Case 65

2.4.2 The m < n Case 66

2.4.3 Nonsquare Inverses and Systems of Linear Equations 66

2.5 Fewer Equations than Unknowns (m < n) 67

2.5.1 Consistent Systems [[rho](A) = [rho](A|B)] 67

2.5.2 Inconsistent Systems [[rho](A) [not equal rho](A|B)] 71

2.5.3 Summary: Fewer Equations than Unknowns 71

2.6 More Equations than Unknowns (m > n) 72

2.6.1 Consistent Systems [[rho](A) = [rho](A|B)] 72

2.6.2 Inconsistent Systems [[rho](A) [not equal rho](A|B)] 74

2.6.3 Summary: More Equations than Unknowns 75

2.7 Numerical Methods for Solving Systems of Linear Equations 75

2.7.1 Elementary Matrix Operations and Gaussian Methods 76

2.7.2 Iterative Methods 79

2.7.3 Factorization of the Matrix A 81

2.7.4 Numerical Illustration 84

Part II Foundations: Nonlinear Methods 97

3 Unconstrained Maximization and Minimization 99

3.1 Limits and Derivatives for Functions of One Variable 100

3.1.1 Limits 100

3.1.2 The Derivative (Algebra) 102

3.1.3 The Derivative (Geometry) 105

3.2 Maximum and Minimum Conditions for Functions of One Variable 106

3.2.1 The (First) Derivative

a Question of Slope 106

3.2.2 The Second Derivative

a Question of Shape 109

3.2.3 Maxima and Minima Using First and Second Derivatives 110

3.2.4 The Differential 112

3.2.5 Maxima and Minima with Differentials 113

3.3 Taylor's Series, Concavity, and Convexity of f(x) 114

3.3.1 Taylor's Series for f(x) 114

3.3.2 Concavity and Convexity of f(x) 116

3.3.3 Local, Global and Unique Maxima and Minima 121

3.3.4 Additional Kinds of Convexity and Concavity 121

3.3.5 Numerical Examples 122

3.4 Maxima and Minima for Functions of Two Independent Variables 124

3.4.1 Partial Derivatives, Gradient Vectors, and Hessian Matrices 125

3.4.2 Maxima and Minima for f(x[subscript 1], x[subscript 2]) 128

3.4.3 The Total Differential for Functions of Two Variables 129

3.5 Taylor's Series, Concavity, and Convexity of f(X) 134

3.5.1 Taylor's Series for f(X) 134

3.5.2 Concavity and Convexity of f(X) 135

3.5.3 Convex Sets 137

3.5.4 Numerical Illustrations for the f(x[subscript 1], x[subscript 2]) Case 141

3.5.5 Quasiconcave and Quasiconvex Functions f(x[subscript 1], x[subscript 2]) 146

3.6 Maxima and Minima for Functions of n Independent Variables 146

3.6.1 First-Order Conditions 147

3.6.2 Second-Order Conditions 148

Appendix 3.1 Quasiconcave and Quasiconvex Functions 150

3A.1.1 Quasiconcavity and Quasiconvexity of f(x) 151

3A.1.2 Quasiconcavity and Quasiconvexity of f(X) 158

Appendix 3.2 Maclaurin's and Taylor's Series 165

3A.2.1 Maclaurin's Series 165

3A.2.2 Taylor's Series 166

3A.2.2 Taylor's Theorem 167

4 Constrained Maximization and Minimization 171

4.1 Quadratic Forms with Side Conditions 172

4.2 Maxima and Minima for Functions of Two Dependent Variables 174

4.2.1 First-Order Conditions: Differentials 174

4.2.2 First-Order Conditions: Lagrange Multipliers 178

4.2.3 Second-Order Conditions 179

4.2.5 Geometry of the First-Order Conditions 183

4.2.6 Two Examples with Gradients that Are Null Vectors 187

4.2.7 A Note on the Form of the Lagrangian Function 190

4.3 Extension to More Dependent Variables 191

4.3.1 First-Order Conditions 191

4.3.2 Second-Order Conditions 192

4.4 Extension to More Constraints 193

4.4.1 First-Order Conditions 193

4.4.2 Second-Order Conditions 195

4.5 Maxima and Minima with Inequality Constraints 197

4.5.1 Standard Forms for Inequality-Constrained Problems 198

4.5.2 More on Inequalities and Convex Sets 199

4.5.3 One Inequality Constraint 200

4.5.4 More than One Inequality Constraint 207

4.5.5 A Systematic Approach: The Kuhn-Tucker Method 210

4.5.6 Further Complications 221

Part III Applications: Iterative Methods for Nonlinear Problems 227

5 Solving Nonlinear Equations 229

5.1 Solutions to f(x) = 0 233

5.1.1 Nonderivative Methods 233

5.1.2 Derivative Methods 243

5.2 Solutions to F(X) = 0 251

5.2.1 Nonderivative Methods 253

5.2.2 Derivative Methods 266

Appendix 5.1 Finite-Difference Approximations to Derivatives, Gradients, and Hessian Matrices 276

5A.1.1 Functions of One Variable 276

5A.1.2 Functions of Several Variables 278

5A.1.3 Systems of Equations 278

5A.1.4 Hessian Matrices 279

Appendix 5.2 The Sherman-Morrison-Woodbury Formula 281

6 Solving Unconstrained Maximization and Minimization Problems 291

6.1 Minimization of f(x) 292

6.1.1 Simultaneous Methods 293

6.1.2 Sequential Methods 299

6.1.3 Parabolic Interpolation 312

6.1.4 Combined Techniques 313

6.1.5 Line Search with Derivatives 314

6.2 Minimization of f(X): Nonderivative Methods 315

6.2.1 Test Functions 315

6.2.2 Simplex Methods 316

6.2.3 Sequential Univariate Search 327

6.2.4 Conjugate Direction Methods 329

6.2.5 Results for Additional Test Functions 341

6.3 Minimization of f(X): Derivative Methods 346

6.3.1 Classical Gradient Methods 347

6.3.2 Restricted Step Methods 349

6.3.3 Conjugate Gradient Methods 358

6.3.4 Quasi-Newton (Variable Metric) Methods 360

6.3.5 Results for Additional Test Functions 367

Appendix 6.1 The Sherman-Morrison-Woodbury Formula Revisited 371

6A.1.2 Symmetric Rank 1 Changes 372

6A.1.3 An Alternative SMW Expression 373

6A.1.4 Symmetric Rank 2 Changes 374

6A.1.5 Another Alternative SMW Expression 375

6A.1.6 Symmetric Rank n Changes (n > 2) and the Accompanying SMW Expression 375

Part IV Applications: Constrained Optimization in Linear Models 381

7 Linear Programming: Fundamentals 383

7.1 Fundamental Structure, Algebra, and Geometry 387

7.1.1 Illustrative Example 387

7.1.2 The Minimization Problem: Algebra 389

7.1.3 The Maximization Problem: Geometry 390

7.2 Convex Set Theory Again 394

7.3 The Simplex Method 400

7.3.1 The Simplex Criterion 401

7.3.2 Simplex Arithmetic 404

7.4 Duality 412

7.4.1 Mathematical Relationships and Interpretation 412

7.4.2 Dual Values in the Simplex Tables 417

7.4.3 The Optimal Solution to the Dual 419

7.5 Sensitivity Analysis 419

7.5.1 Changes in the Right-Hand Side of a Constraint 419

7.5.2 Changes in an Objective Function Coefficient 423

8 Linear Programming: Extensions 429

8.1 Multiple Optima and Degeneracy 430

8.1.1 Primal Multiple Optima 430

8.1.2 Primal Degenerate Optimum 432

8.2 Artificial Variables 434

8.3 Equations as Constraints 438

8.4 The Transportation Problem 439

8.4.1 Fundamental Structure 439

8.4.2 Numerical Illustration 443

8.5 The Assignment Problem 447

8.5.1 Fundamental Structure 447

8.5.2 Numerical Illustration 448

8.6 Integer Programming 449

8.6.1 The Geometry of Integer Programs 450

8.6.2 Complete Enumeration 451

8.6.3 Gomory's Cutting-Plane Method 453

8.6.4 Branch-and-Bound Methods 461

8.7 Hierarchical Optimization and Goal Programming 467

8.7.1 Hierarchical Optimization: Structure 468

8.7.2 Hierarchical Optimization: Numerical Illustration 470

8.7.3 An Alternative Hierarchical Optimization Approach 473

8.7.4 Numerical Illustration of This Alternative Approach 475

8.7.5 Goal Programming: Structure 477

8.7.6 Goal Programming: Numerical Illustration 480

9 Linear Programming: Interior Point Methods 491

9.1 Introduction to Interior Point Methods 494

9.2 Affine Scaling Interior Point Methods 497

9.2.1 Direction of Movement 499

9.2.2 Step Size 503

9.2.3 Scaling 505

9.2.4 Starting and Stopping 509

9.3 Path-Following Interior Point Methods 510

9.4 Additional Variations and Implementation Issues 517

9.4.1 Regular Simplices; Circles and Ellipses 517

9.4.2 Alternative Scalings 521

9.4.3 Computational Issues 521

9.4.4 Cholesky Factorizations 523

9.5 Relative Performance: Simplex versus Interior Point Methods on Real-World Problems 527

Part V Applications: Constrained Optimization in Nonlinear Models 533

10 Nonlinear Programming: Fundamentals 535

10.1 Structure of the Nonlinear Programming Problem 536

10.1.1 Algebra 536

10.1.2 Geometry 537

10.2 The Kuhn-Tucker Approach to Nonlinear Programming Problems 539

10.2.1 Kuhn-Tucker Conditions for Programming Problems that Include X [greater than or equal] 0 540

10.2.2 Computational Implications 544

10.2.3 Numerical Illustrations 545

10.2.4 Constraint Gradient Geometry Once Again 550

10.2.5 The Linear Programming Case and Dual Variables 553

10.2.6 Quasiconcavity, Quasiconvexity and Sufficiency 557

10.3 The Kuhn-Tucker Constraint Qualification 564

10.3.1 Unconstrained Optimum Inside or on the Boundaries of the Feasible Region 564

10.3.2 Unconstrained Optimum Outside the Feasible Region 565

10.3.3 Numerical Illustrations: Convex Feasible Regions 565

10.3.4 Numerical Illustration: Nonconvex Feasible Regions with Cusps at Optimal Corners 569

10.3.5 Practical Considerations 571

10.4 Saddle Point Problems 575

10.4.1 Saddle Points Defined 571

10.4.2 Saddle Points and Linear Programming Problems 577

10.4.3 Saddle Points and Nonlinear Programming Problems 578

11 Nonlinear Programming: Duality and Computational Methods 583

11.1 Gradientlike Computational Methods for Nonlinear Programs 584

11.1.1 Zoutendijk's Method of Feasible Directions 585

11.1.2 Rosen's Gradient Projection Method 588

11.1.3 Alternative Interior Point Methods for Nonlinear Programs 591

11.2 Duality in Nonlinear Programming 591

11.3 Additional Computational Methods for Nonlinear Programs 595

11.3.1 Separable Programming 595

11.3.2 Cutting-Plane Methods 602

11.3.3 Sequential Unconstrained Techniques 609

11.4 Quadratic Programming 617

11.4.1 Structure 617

11.4.2 Computational Methods 620

11.4.3 Duality in Quadratic Programming Problems 621

11.4.4 Numerical Examples 622.

Notes:

"A Wiley-Interscience publication."

Includes bibliographical references and index.

ISBN:

0471351695

OCLC:

41017413