| |
| |
| |
| Introduction | |
| |
| |
| |
| Optimization | |
| |
| |
| |
| Types of Problems | |
| |
| |
| |
| Size of Problems | |
| |
| |
| |
| Iterative Algorithms and Convergence | |
| |
| |
| |
| Linear Programming | |
| |
| |
| |
| Basic Properties of Linear Programs | |
| |
| |
| |
| Introduction | |
| |
| |
| |
| Examples of Linear Programming Problems | |
| |
| |
| |
| Basic Solutions | |
| |
| |
| |
| The Fundamental Theorem of Linear Programming | |
| |
| |
| |
| Relations to Convexity | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| The Simplex Method | |
| |
| |
| |
| Pivots | |
| |
| |
| |
| Adjacent Extreme Points | |
| |
| |
| |
| Determining a Minimum Feasible Solution | |
| |
| |
| |
| Computational Procedure-Simplex Method | |
| |
| |
| |
| Artificial Variables | |
| |
| |
| |
| Matrix Form of the Simplex Method | |
| |
| |
| |
| The Revised Simplex Method | |
| |
| |
| |
| The Simplex Method and LU Decomposition | |
| |
| |
| |
| Decomposition | |
| |
| |
| |
| Summary | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Duality | |
| |
| |
| |
| Dual Linear Programs | |
| |
| |
| |
| The Duality Theorem | |
| |
| |
| |
| Relations to the Simplex Procedure | |
| |
| |
| |
| Sensitivity and Complementary Slackness | |
| |
| |
| |
| The Dual Simplex Method | |
| |
| |
| |
| The Primal-Dual Algorithm | |
| |
| |
| |
| Reduction of Linear Inequalities | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Interior-Point Methods | |
| |
| |
| |
| Elements of Complexity Theory | |
| |
| |
| |
| The Simplex Method is not Polynomial-Time | |
| |
| |
| |
| The Ellipsoid Method | |
| |
| |
| |
| The Analytic Center | |
| |
| |
| |
| The Central Path | |
| |
| |
| |
| Solution Strategies | |
| |
| |
| |
| Termination and Initialization | |
| |
| |
| |
| Summary | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Transportation and Network Flow Problems | |
| |
| |
| |
| The Transportation Problem | |
| |
| |
| |
| Finding a Basic Feasible Solution | |
| |
| |
| |
| Basis Triangularity | |
| |
| |
| |
| Simplex Method for Transportation Problems | |
| |
| |
| |
| The Assignment Problem | |
| |
| |
| |
| Basic Network Concepts | |
| |
| |
| |
| Minimum Cost Flow | |
| |
| |
| |
| Maximal Flow | |
| |
| |
| |
| Summary | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Unconstrained Problems | |
| |
| |
| |
| Basic Properties of Solutions and Algorithms | |
| |
| |
| |
| First-Order Necessary Conditions | |
| |
| |
| |
| Examples of Unconstrained Problems | |
| |
| |
| |
| Second-Order Conditions | |
| |
| |
| |
| Convex and Concave Functions | |
| |
| |
| |
| Minimization and Maximization of Convex Functions | |
| |
| |
| |
| Zero-Order Conditions | |
| |
| |
| |
| Global Convergence of Descent Algorithms | |
| |
| |
| |
| Speed of Convergence | |
| |
| |
| |
| Summary | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Basic Descent Methods | |
| |
| |
| |
| Fibonacci and Golden Section Search | |
| |
| |
| |
| Line Search by Curve Fitting | |
| |
| |
| |
| Global Convergence of Curve Fitting | |
| |
| |
| |
| Closedness of Line Search Algorithms | |
| |
| |
| |
| Inaccurate Line Search | |
| |
| |
| |
| The Method of Steepest Descent | |
| |
| |
| |
| Applications of the Theory | |
| |
| |
| |
| Newton's Method | |
| |
| |
| |
| Coordinate Descent Methods | |
| |
| |
| |
| Spacer Steps | |
| |
| |
| |
| Summary | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Conjugate Direction Methods | |
| |
| |
| |
| Conjugate Directions | |
| |
| |
| |
| Descent Properties of the Conjugate Direction Method | |
| |
| |
| |
| The Conjugate Gradient Method | |
| |
| |
| |
| The C-G Method as an Optimal Process | |
| |
| |
| |
| The Partial Conjugate Gradient Method | |
| |
| |
| |
| Extension to Nonquadratic Problems | |
| |
| |
| |
| Parallel Tangents | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Quasi-Newton Methods | |
| |
| |
| |
| Modified Newton Method | |
| |
| |
| |
| Construction of the Inverse | |
| |
| |
| |
| Davidon-Fletcher-Powell Method | |
| |
| |
| |
| The Broyden Family | |
| |
| |
| |
| Convergence Properties | |
| |
| |
| |
| Scaling | |
| |
| |
| |
| Memoryless Quasi-Newton Methods | |
| |
| |
| |
| Combination of Steepest Descent and Newton's Method | |
| |
| |
| |
| Summary | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Constrained Minimization | |
| |
| |
| |
| Constrained Minimization Conditions | |
| |
| |
| |
| Constraints | |
| |
| |
| |
| Tangent Plane | |
| |
| |
| |
| First-Order Necessary Conditions (Equality Constraints) | |
| |
| |
| |
| Examples | |
| |
| |
| |
| Second-Order Conditions | |
| |
| |
| |
| Eigenvalues in Tangent Subspace | |
| |
| |
| |
| Sensitivity | |
| |
| |
| |
| Inequality Constraints | |
| |
| |
| |
| Zero-Order Conditions and Lagrange Multipliers | |
| |
| |
| |
| Summary | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Primal Methods | |
| |
| |
| |
| Advantage of Primal Methods | |
| |
| |
| |
| Feasible Direction Methods | |
| |
| |
| |
| Active Set Methods | |
| |
| |
| |
| The Gradient Projection Method | |
| |
| |
| |
| Convergence Rate of the Gradient Projection Method | |
| |
| |
| |
| The Reduced Gradient Method | |
| |
| |
| |
| Convergence Rate of the Reduced Gradient Method | |
| |
| |
| |
| Variations | |
| |
| |
| |
| Summary | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Penalty and Barrier Methods | |
| |
| |
| |
| Penalty Methods | |
| |
| |
| |
| Barrier Methods | |
| |
| |
| |
| Properties of Penalty and Barrier Functions | |
| |
| |
| |
| Newton's Method and Penalty Functions | |
| |
| |
| |
| Conjugate Gradients and Penalty Methods | |
| |
| |
| |
| Normalization of Penalty Functions | |
| |
| |
| |
| Penalty Functions and Gradient Projection | |
| |
| |
| |
| Exact Penalty Functions | |
| |
| |
| |
| Summary | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Dual and Cutting Plane Methods | |
| |
| |
| |
| Global Duality | |
| |
| |
| |
| Local Duality | |
| |
| |
| |
| Dual Canonical Convergence Rate | |
| |
| |
| |
| Separable Problems | |
| |
| |
| |
| Augmented Lagrangians | |
| |
| |
| |
| The Dual Viewpoint | |
| |
| |
| |
| Cutting Plane Methods | |
| |
| |
| |
| Kelley's Convex Cutting Plane Algorithm | |
| |
| |
| |
| Modifications | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Primal-Dual Methods | |
| |
| |
| |
| The Standard Problem | |
| |
| |
| |
| Strategies | |
| |
| |
| |
| A Simple Merit Function | |
| |
| |
| |
| Basic Primal-Dual Methods | |
| |
| |
| |
| Modified Newton Methods | |
| |
| |
| |
| Descent Properties | |
| |
| |
| |
| Rate of Convergence | |
| |
| |
| |
| Interior Point Methods | |
| |
| |
| |
| Semidefinite Programming | |
| |
| |
| |
| Summary | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Mathematical Review | |
| |
| |
| |
| Sets | |
| |
| |
| |
| Matrix Notation | |
| |
| |
| |
| Spaces | |
| |
| |
| |
| Eigenvalues and Quadratic Forms | |
| |
| |
| |
| Topological Concepts | |
| |
| |
| |
| Functions | |
| |
| |
| |
| Convex Sets | |
| |
| |
| |
| Basic Definitions | |
| |
| |
| |
| Hyperplanes and Polytopes | |
| |
| |
| |
| Separating and Supporting Hyperplanes | |
| |
| |
| |
| Extreme Points | |
| |
| |
| |
| Gaussian Elimination | |
| |
| |
| Bibliography | |
| |
| |
| Index | |