ÏßÐԺͷÇÏßÐԹ滮-µÚ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 ProgrammingChapter 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.ExercisesChapter 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.Artifi 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.ExercisesChapter 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.ExercisesChapter 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.ExercisesChapter 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 ProblemsChapter 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.ExercisesChapter 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.ExercisesChapter 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.ExercisesChapter 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 MinimizationChapter 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.ExercisesChapter 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.ExercisesChapter 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.ExercisesChapter 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.ExercisesChapter 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.ExercisesAppendix 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.FunctionsAppendix B.Convex Sets B.1.Basic Definitions B.2.Hyperplanes and Polytopes B.3.Separating and Supporting Hyperplanes B.4.Extreme PointsAppendix C.Gaussian EliminationBibliographyIndex