1. Introduction -- 1.1. History Of Linear Programming -- 1.2. The Linear Programming Problem -- 1.3. Examples Of Linear Programming Problems -- 1.4. Mastering Linear Programming -- 2. Geometry Of Linear Programming -- 2.1. Basic Terminologies Of Linear Programming -- 2.2. Hyperplanes, Halfspaces, And Polyhedral Sets -- 2.3. Affine Sets, Convex Sets, And Cones -- 2.4. Extreme Points And Basic Feasible Solutions -- 2.5. Nondegeneracy And Adjacency -- 2.6. Resolution Theorem For Convex Polyhedrons -- 2.7. Fundamental Theorem Of Linear Programming -- 2.8. Concluding Remarks: Motivations Of Different Approaches -- 3. The Revised Simplex Method -- 3.1. Elements Of An Iterative Scheme -- 3.2. Basics Of The Simplex Method -- 3.3. Algebra Of The Simplex Method -- 3.4. Starting The Simplex Method -- 3.5. Degeneracy And Cycling -- 3.6. Preventing Cycling -- 3.7. The Revised Simplex Method -- 4. Duality Theory And Sensitivity Analysis -- 4.1. Dual Linear Program -- 4.2. Duality Theory --^ 4.3. Complementary Slackness And Optimality Conditions -- 4.4. An Economic Interpretation Of The Dual Problem -- 4.5. The Dual Simplex Method -- 4.6. The Primal Dual Method -- 4.7. Sensitivity Analysis -- 5. Complexity Analysis And The Ellipsoid Method -- 5.1. Concepts Of Computational Complexity -- 5.2. Complexity Of The Simplex Method -- 5.3. Basic Ideas Of The Ellipsoid Method -- 5.4. Ellipsoid Method For Linear Programming -- 5.5. Performance Of The Ellipsoid Method For Lp -- 5.6. Modifications Of The Basic Algorithm -- 6. Karmarkar's Projective Scaling Algorithm -- 6.1. Basic Ideas Of Karmarkar's Algorithm -- 6.2. Karmarkar's Standard Form -- 6.3. Karmarkar's Projective Scaling Algorithm -- 6.4. Polynomial-time Solvability -- 6.5. Converting To Karmarkar's Standard Form -- 6.6. Handling Problems With Unknown Optimal Objective Values -- 6.7. Unconstrained Convex Dual Approach -- 7. Affine Scaling Algorithms -- 7.1. Primal Affine Scaling Algorithm --^ 7.2. Dual Affine Scaling Algorithm -- 7.3. The Primal-dual Algorithm -- 8. Insights Into The Interior-point Methods -- 8.1. Moving Along Different Algebraic Paths -- 8.2. Missing Information -- 8.3. Extensions Of Algebraic Paths -- 8.4. Geometric Interpretation Of The Moving Directions -- 8.5. General Theory -- 9. Affine Scaling For Convex Quadratic Programming -- 9.1. Convex Quadratic Program With Linear Constraints -- 9.2. Affine Scaling For Quadratic Programs -- 9.3. Primal-dual Algorithm For Quadratic Programming -- 9.4. Convex Programming With Linear Constraints -- 10. Implementation Of Interior-point Algorithms -- 10.1. The Computational Bottleneck -- 10.2. The Cholesky Factorization Method -- 10.3. The Conjugate Gradient Method -- 10.4. The Lq Factorization Method. Shu-cherng Fang, Sarat Puthenpura. At Head Of Title: At&t Includes Bibliographical References (p. 280-293) And Index.
