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

11.1．Constraints

11.2．Tangent Plane

11.3．First-Order Necessary Conditions(Equality Constraints)

11.4．Examples

11.5．Second-Order Conditions

11.6．Eigenvalues in Tangent Subspace

11.7．Sensitivity

11.8．Inequality Constraints

11.9．Zero-Order Conditions and Lagrange Multipliers

11.10．Summary

11.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．Mathemtical 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