| |
| |
| |
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 | |