线性和非线性规划 第3版

Chapter 1.Introduction 
1.1.Optimization 
1.2.Types of Problems 
1.3.Size of Problems 
1.4.Iterative Algorithms and Convergence 
PART Ⅰ Linear Programming 
Chapter 2.Basic Properties of Linear Programs 
2.1.Introduction 
2.2.Examples of Linear Programming Problems 
2.3.Basic Solutions 
2.4.The Fundamental Theorem of Linear Programming 
2.5.Relations to Convexity 
2.6.Exercises 
Chapter 3.The Simplex Method 
3.1.Pivots 
3.2.Adjacent Extreme Points 
3.3.Determining a Minimum Feasible Solution 
3.4.Computational Procedure—Simplex Method 
3.5.Artificial Variables 
3.6.Matrix Form of the Simplex Method 
3.7.The Revised Simplex Method 
3.8.The Simplex Method and LU Decomposition 
3.9.Decomposition 
3.10.Summary 
3.11.Exercises 
Chapter 4.Duality 
4.1.Dual Linear Programs 
4.2.The Duality Theorem 
4.3.Relations to the Simplex Procedure 
4.4.Sensitivity and Complementary Slackness 
4.5.The Dual Simplex Method 
4.6.The—Primal—Dual Algorithm 
4.7.Reduction of Linear Inequalities 
4.8.Exercises 
Chapter 5.Interior—Point Methods 
5.1.Elements of Complexity Theory 
5.2.The Simplex Method is not Polynomial—Time 
5.3.The Ellipsoid Method 
5.4.The Analytic Center 
5.5.The Central Path 
5.6.Solution Strategies 
5.7.Termination and Initialization 
5.8.Summary 
5.9.Exercises 
Chapter 6.Transportation and Network Flow Problems 
6.1.The Transportation Problem 
6.2.Finding a Basic Feasible Solution 
6.3.Basis Triangularity 
6.4.Simplex Method for Transportation Problems 
6.5.The Assignment Problem 
6.6.Basic Network Concepts 
6.7.Minimum Cost Flow 
6.8.Maximal Flow 
6.9.Summary 
6.10.Exercises 
PART Ⅱ Unconstrained Problems 
Chapter 7.Basic Properties of Solutions and Algorithms 
7.1.First—Order Necessary Conditions 
7.2.Examples of Unconstrained Problems 
7.3.Second—Order Conditions 
7.4.Convex and Concave Functions 
7.5.Minimization and Maximization of Convex Functions 
7.6.Zero—Order Conditions 
7.7.Global Convergence of Descent Algorithms 
7.8.Speed of Convergence 
7.9.Summary 
7.10.Exercises 
Chapter 8.Basic Descent Methods 
8.1.Fibonacci and Golden Section Search 
8.2.Line Search by Curve Fitting 
8.3.Global Convergence of Curve Fitting 
8.4.Closedness of Line Search Algorithms 
8.5.Inaccurate Line Search 
8.6.The Method of Steepest Descent 
8.7.Applications of the Theory 
8.8.Newton's Method 
8.9.Coordinate Descent Methods 
8.10.Spacer Steps 
8.11.Summary 
8.12.Exercises 
Chapter 9.Conjugate Direction Methods 
9.1.Conjugate Directions 
9.2.Descent Properties of the Conjugate Direction Method 
9.3.The Conjugate Gradient Method 
9.4.The C—G Method as an Optimal Process 
9.5.The Partial Conjugate Gradient Method 
9.6.Extension to Nonquadratic Problems 
9.7.Parallel Tangents 
9.8.Exercises 
Chapter 10.Quasi—Newton Methods 
10.1.Modified Newton Method 
10.2.Construction of the Inverse 
10.3.Davidon—Fletcher—Powell Method 
10.4.The Broyden Family 
10.5.Convergence Properties 
10.6.Scaling 
10.7.Memoryless Quasi—Newton Methods 
10.8.Combination of Steepest Descent and Newton's Method 
10.9.Summary 
10.10.Exercises 
PART Ⅲ Constrained Minimization 
Chapter 11.Constrained Minimization Conditions 
1.1.Constraints 
1.2.Tangent Plane 
1.3.First—Order Necessary Conditions（Equality Constraints） 
1.4.Examples 
1.5.Second—Order Conditions 
1.6.Eigenvalues in Tangent Subspace 
1.7.Sensitivity 
1.8.Inequality Constraints 
1.9.Zero—Order Conditions and Lagrange Multipliers 
1.10.Summary 
1.11.Exercises 
Chapter 12.Primal Methods 
12.1.Advantage of Primal Methods 
12.2.Feasible Direction Methods 
12.3.Active Set Methods 
12.4.The Gradient Projection Method 
12.5.Convergence Rate of the Gradient Projection Method 
12.6.The Reduced Gradient Method 
12.7.Convergence Rate of the Reduced Gradient Method 
12.8.Variations 
12.9.Summary 
12.10.Exercises 
Chapter 13.Penalty and Barrier Methods 
13.1.Penalty Methods 
13.2.Barrier Methods 
13.3.Properties of Penalty and Barrier Functions 
13.4.Newton's Method and Penalty Functions 
13.5.Conjugate Gradients and Penalty Methods 
13.6.Normalization of Penalty Functions 
13.7.Penalty Functions and Gradient Projection 
13.8.Exact Penalty Functions 
13.9.Summary 
13.10.Exercises 
Chapter 14.Dual and Cutting Plane Methods 
14.1.Global Duality 
14.2.Local Duality 
14.3.Dual Canonical Convergence Rate 
14.4.Separable Problems 
14.5.Augmented Lagrangians 
14.6.The Dual Viewpoint 
14.7.Cutting Plane Methods 
14.8.Kelley's Convex Cutting Plane Algorithm 
14.9.Modifications 
14.10.Exercises 
Chapter 15.Primal—Dual Methods 
15.1.The Standard Problem 
15.2.Strategies 
15.3.A Simple Merit Function 
15.4.Basic Primal—Dual Methods 
15.5.Modified Newton Methods 
15.6.Descent Properties 
15.7.Rate of Convergence 
15.8.Interior Point Methods 
15.9.Semidefinite Programming 
15.10.Summary 
15.11.Exercises 
Appendix A.Mathematical Review 
A.1.Sets 
A.2.Matrix Notation 
A.3.Spaces 
A.4.Eigenvalues and Quadratic Forms 
A.5.Topological Concepts 
A.6.Functions 
Appendix B.Convex Sets 
B.1.Basic Definitions 
B.2.Hyperplanes and Polytopes 
B.3.Separating and Supporting Hyperplanes 
B.4.Extreme Points 
Appendix C.Gaussian Elimination 
Bibliography 
Index