Nonlinear Programming

Table of Contents:

1. Unconstrained Optimization

   1. Optimality Conditions
      1. Variational Ideas
      2. Main Optimality Conditions
   2. Gradient Methods -- Convergence
      1. Descent Directions and Stepsize Rules
      2. Convergence Results
   3. Gradient Methods -- Rate of Convergence
      1. The Local Analysis Approach
      2. The Role of the Condition Number
      3. Convergence Rate Results
   4. Newton's Method and Variations
   5. Least Squares Problems
      1. The Gauss-Newton Method
      2. Incremental Gradient Methods*
      3. Incremental Forms of the Gauss-Newton Method*
   6. Conjugate Direction Methods
   7. Quasi-Newton Methods
   8. Nonderivative Methods
      1. Coordinate Descent
      2. Direct Search Methods
   9. Discrete-Time Optimal Control*
   10. Some Practical Guidelines
   11. Notes and Sources
   
   

2. Optimization Over a Convex Set

   1. Optimality Conditions
   2. Feasible Directions and the Conditional Gradient Method
      1. Descent Directions and Stepsize Rules
      2. The Conditional Gradient Method
   3. Gradient Projection Methods
      1. Feasible Directions and Stepsize Rules Based on Projection
      2. Convergence Analysis*
   4. Two-Metric Projection Methods
   5. Manifold Suboptimization -- Quadratic Programming
   6. Affine Scaling for Linear Programming
   7. Block Coordinate Descent Methods*
   8. Notes and Sources
   
   

3. Lagrange Multiplier Theory

   1. Necessary Conditions for Equality Constraints
      1. The Penalty Approach
      2. The Elimination Approach
      3. The Lagrangian Function
   2. Sufficient Conditions and Sensitivity Analysis
      1. The Augmented Lagrangian Approach
      2. The Feasible Direction Approach
      3. Sensitivity*
   3. Inequality Constraints
      1. Karush-Kuhn-Tucker Optimality Conditions
      2. Conversion to the Equality Case*
      3. Second Order Sufficiency Conditions and Sensitivity*
      4. Fritz John Optimality Conditions*
      5. Refinements*
   4. Linear Constraints and Duality*
      1. Convex Cost Functions and Linear Constraints
      2. Duality Theory: A Simple Form for Linear Constraints
   5. Notes and Sources
   
   

4. Lagrange Multiplier Algorithms

   1. Barrier and Interior Point Methods
      1. Linear Programming and the Logarithmic Barrier*
   2. Penalty and Augmented Lagrangian Methods
      1. The Quadratic Penalty Function Method
      2. Multiplier Methods -- Main Ideas
      3. Convergence Analysis of Multiplier Methods*
      4. Duality and Second Order Multiplier Methods*
      5. The Exponential Method of Multipliers*
   3. Exact Penalties -- Sequential Quadratic Programming*
      1. Nondifferentiable Exact Penalty Functions
      2. Differentiable Exact Penalty Functions
   4. Lagrangian and Primal-Dual Interior Point Methods*
      1. First-Order Methods
      2. Newton-Like Methods for Equality Constraints
      3. Global Convergence
      4. Primal-Dual Interior Point Methods
      5. Comparison of Various Methods
   5. Notes and Sources
   
   

5. Duality and Convex Programming

   1. The Dual Problem
      1. Lagrange Multipliers
      2. The Weak Duality Theorem
      3. Characterization of Primal and Dual Optimal Solutions
      4. The Case of an Infeasible or Unbounded Primal Problem
      5. Treatment of Equality Constraints
      6. Separable problems and Their Geometry
      7. Additional Issues About Duality
   2. Convex Cost -- Linear Constraints*
      1. Proofs of Duality Theorems
   3. Convex Cost -- Convex Constraints
   4. Conjugate Functions and Fenchel Duality*
      1. Monotropic Programming Duality
      2. Network Optimization
      3. Games and the Minimax Theorem
      4. The Primal Function
      5. A Dual View of Penalty Methods
      6. The Proximal and Entropy Minimization
   5. Discrete Optimization and Duality
      1. Examples of Discrete Optimization Problems
      2. Branch-and-Bound
      3. Lagrangian Relaxation
   6. Notes and Sources
   
   

6. Dual Methods

   1. Dual Derivatives and Subgradients*
   2. Dual Dual Ascent Methods for Differentiable Dual Problems*
      1. Coordinate Ascent for Quadratic Programming
      2. Dualization and Primal Strict Convexity
      3. Partitioning and Dual Strict Concavity
   3. Nondifferentiable Optimization Methods*
      1. Subgradient Methods
      2. Approximate and Incremental Subgradient Methods
      3. Cutting Plane Methods
      4. Ascent and Approximate Ascent Methods
   4. Decomposition Methods*
      1. Lagrangian Relaxation of the Coupling Constraints
      2. Decomposition by Right-Hand Side Allocation
   5. Notes and Sources
   
   

7. Appendix A: Mathematical Background

8. Appendix B: Convex Analysis

9. Appendix C: Line Search Methods

10. Appendix D: Implementation of Newton's Method

11. References

12. Index

Note: Some of the sections in the book may be omitted at first reading without loss of continuity (see the preface). These sections have been marked by a star (*). The rule followed here is that the material discussed in a starred section is not used in a non-starred section.