Linear Programming with MATLAB

✍ Scribed by Michael C. Ferris, Olvi L. Mangasarian, Stephen J. Wright

• Publisher: Society for Industrial and Applied Mathematics, Mathematical Programming Society
• Year: 2007
• Tongue: English
• Leaves: 279
• Category: Library

✦ Synopsis

This text has grown over many years from a set of class notes for an undergraduate linear
programming course offered at the University of Wisconsin-Madison. Though targeted to
Computer Science undergraduates, the course has attracted both undergraduates and beginning
graduate students from many other departments, including Industrial and Systems
Engineering, Statistics, and Mathematics. The course aims to provide a one-semester elementary
introduction to linear programming formulations, algorithms, computations, and
applications. Only basic knowledge of linear algebra and calculus is required.

✦ Table of Contents

Cover
Contents
Preface
1 Introduction
1.1 An Example: The Professor’s Dairy
1.1.1 The Setup
1.1.2 Formulating the Problem and a Graphical Solution
1.1.3 Changing the Problem
1.1.4 Discussion
1.2 Formulations
1.3 Applications
1.3.1 The Diet Problem
1.3.2 Linear Surface Fitting
1.3.3 Load Balancing Problem
1.3.4 Resource Allocation
1.3.5 Classification
1.3.6 Minimum-Cost Network Flow
1.4 Algorithms and Complexity
1.4.1 The Simplex Method
1.4.2 Interior-Point Methods
2 Linear Algebra: A Constructive Approach
2.1 Jordan Exchange
2.2 Linear Independence
2.3 Matrix Inversion
2.4 Exact Solution of m Equations in n Unknowns
2.5 Solving Linear Equations Efficiently
2.6 LU Decomposition
3 The Simplex Method
3.1 A Simple Example
3.2 Vertices
3.3 The Phase II Procedure
3.4 The Phase I Procedure
3.5 Finite Termination
3.5.1 The Nondegenerate Case
3.5.2 Cycling
3.5.3 The General Case
3.6 Linear Programs in Nonstandard Form
3.6.1 Transforming Constraints and Variables
3.6.2 Scheme I
3.6.3 Scheme II
3.6.4 Summary
4 Duality
4.1 Duality and Rank in Linear Systems
4.2 Duality in Linear Programming
4.3 Interpretation of Linear Programming Duality
4.4 Duality Theory
4.5 KKT Optimality Conditions
4.6 Dual Simplex Method
4.7 General Linear Programs
4.8 Big M Method
4.9 Applications of Duality
5 Solving Large Linear Programs
5.1 Foundations
5.1.1 Basic Feasible Solutions and Basis Matrices
5.1.2 Geometric Viewpoint
5.2 The Revised Simplex Method
5.2.1 Upper and Lower Bounds
5.2.2 Generating Basic Feasible Solutions
5.2.3 Basis Updates
5.2.4 Advanced Pivot Selection Mechanisms
5.3 Network Flow Problems
5.3.1 Minimum-Cost Network Flow
5.3.2 Shortest-Path Problem
5.3.3 Max-Flow Problem
5.3.4 Transportation Problem
5.3.5 Assignment Problem
5.3.6 Network Simplex Method
6 Sensitivity and Parametric Linear Programming
6.1 Sensitivity Analysis
6.2 Adding New Variables or Constraints
6.3 Parametric Optimization of the Objective Function
6.4 Parametric Optimization of the Right-Hand Side
7 Quadratic Programming and Complementarity Problems
7.1 Nonlinear Programs: Optimality Conditions
7.2 Quadratic Programming
7.2.1 Basic Existence Result
7.2.2 KKT Conditions
7.2.3 Duality
7.3 Linear Complementarity Problems
7.4 Lemke’s Method
7.5 Bimatrix Games
7.5.1 Computing Nash Equilibria
7.5.2 Zero-Sum Games As Dual Linear Programs
8 Interior-Point Methods
8.1 Motivation and Outline
8.2 Newton’s Method
8.3 Primal-Dual Methods
8.3.1 An Affine-Scaling Approach
8.3.2 Path-Following Methods
8.3.3 Solution of the Linear System at Each Interior-Point Iteration
8.3.4 Practical Primal-Dual Methods
8.4 Interior-Point vs. Simplex
8.5 Extension to Quadratic Programming
9 Approximation and Classification
9.1 Minimax Problems
9.2 Approximation
9.2.1 Chebyshev Approximation
9.2.2 L1 Approximation
9.2.3 Approximate Solutions to Systems with Inequality Constraints
9.2.4 Least-Squares Problems
9.3 Huber Estimation
9.4 Classification Problems
A Linear Algebra, Convexity, and Nonlinear Functions
A.1 Linear Algebra
A.2 Convex Sets
A.3 Smooth Functions
A.4 Convex Functions
A.5 Quadratic Functions
A.6 Norms and Order Notation
A.7 Taylor’s Theorem
B Summary of Available MATLAB Commands
B.1 Basic MATLAB Operations
B.2 MATLAB Functions Defined in This Book
Bibliography
Index