Optimization : foundations and applications /

A thorough and highly accessible resource for analysts in a broad range of social sciences. Optimization: Foundations and Applications presents a series of approaches to the challenges faced by analysts who must find the best way to accomplish particular objectives, usually with the added complicati...

Full description

Bibliographic Details
Main Author:	Miller, Ronald E.
Format:	eBook
Language:	English
Published:	New York : Wiley, 2000.
Subjects:	Mathematical optimization. Electronic books.
Online Access:	Connect to the full text of this electronic book

Table of Contents:

Front Matter
Foundations: Linear Methods. Foundations: Linear Methods
Matrix Algebra
Systems of Linear Equations
Foundations: Nonlinear Methods. Foundations: Nonlinear Methods
Unconstrained Maximization and Minimization
Constrained Maximization and Minimization
Applications: Iterative Methods for Nonlinear Problems. Applications: Iterative Methods for Nonlinear Problems
Solving Nonlinear Equations
Solving Unconstrained Maximization and Minimization Problems
Applications: Constrained Optimization in Linear Models. Applications: Constrained Optimization in Linear Models
Linear Programming: Fundamentals
Linear Programming: Extensions
Linear Programming: Interior Point Methods
Applications: Constrained Optimization in Nonlinear Models. Applications: Constrained Optimization in Nonlinear Models
Nonlinear Programming: Fundamentals
Nonlinear Programming: Duality and Computational Methods
Answers to Selected Problems
Index.
Part I Foundations: Linear Methods 1
1 Matrix Algebra 3
1.1 Matrices: Definition and General Representation 4
1.2 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 Geometry of Simple Equation Systems: Solution Possibilities 26
1.4 Geometry of Vectors 29
1.4.1 Linear Combinations of Vectors 29
1.4.2 Geometry of Multiplication by a Scalar 31
1.4.3 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 Sign of a Quadratic Form 48
2 Systems of Linear Equations 53
2.1 2 [times] 2 Case Again 54
2.2 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 N [times] n Case 62
2.3.1 Consistent Systems [[rho](A) = [rho](A)] 62
2.3.2 Inconsistent Systems [[rho](A) [not equal rho](A)] 64
2.4 More Matrix Algebra: Inverses for Nonsquare Matrices 65
2.4.1 M> n Case 65
2.4.2 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)] 67
2.5.2 Inconsistent Systems [[rho](A) [not equal rho](A)] 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)] 72
2.6.2 Inconsistent Systems [[rho](A) [not equal rho](A)] 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 Derivative (Algebra) 102
3.1.3 Derivative (Geometry) 105
3.2 Maximum and Minimum Conditions for Functions of One Variable 106
3.2.1 (First) Derivative--a Question of Slope 106
3.2.2 Second Derivative--a Question of Shape 109
3.2.3 Maxima and Minima Using First and Second Derivatives 110
3.2.4 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 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 FunctionsH 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 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 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 Minimization Problem: Algebra 389
7.1.3 Maximization Problem: Geometry 390
7.2 Convex Set Theory Again 394
7.3 Simplex Method 400
7.3.1 Simplex Criterion 401
7.3.2 Simplex Arithmetic 404
7.4 Duality 412
7.4.1N Mathematical Relationships and Interpretation 412
7.4.2 Dual Values in the Simplex Tables 417
7.4.3 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 Transportation Problem 439
8.4.1 Fundamental Structure 439
8.4.2 Numerical Illustration 443
8.5 Assignment Problem 447
8.5.1 Fundamental Structure 447
8.5.2 Numerical Illustration 448
8.6 Integer Programming 449
8.6.1 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.