LINEAR PROGRAMMING WITH MATLAB

Michael C. Ferris
Olvi L. Mangasarian
Stephen J. Wright
University of Wisconsin–Madison
Madison, Wisconsin

Contents
Preface xi
1 Introduction 1
1.1 An Example: The Professor’s Dairy . . . . . . . . . . . . . . . . . . . 2
1.1.1 The Setup . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.1.2 Formulating the Problem and a Graphical Solution . . . . 2
1.1.3 Changing the Problem . . . . . . . . . . . . . . . . . . . 4
1.1.4 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2 Formulations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.3 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.3.1 The Diet Problem . . . . . . . . . . . . . . . . . . . . . 8
1.3.2 Linear Surface Fitting . . . . . . . . . . . . . . . . . . . 9
1.3.3 Load Balancing Problem . . . . . . . . . . . . . . . . . . 10
1.3.4 Resource Allocation . . . . . . . . . . . . . . . . . . . . 10
1.3.5 Classification . . . . . . . . . . . . . . . . . . . . . . . . 11
1.3.6 Minimum-Cost Network Flow . . . . . . . . . . . . . . . 12
1.4 Algorithms and Complexity . . . . . . . . . . . . . . . . . . . . . . . 14
1.4.1 The Simplex Method . . . . . . . . . . . . . . . . . . . . 14
1.4.2 Interior-Point Methods . . . . . . . . . . . . . . . . . . . 15
2 Linear Algebra: A Constructive Approach 17
2.1 Jordan Exchange . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.2 Linear Independence . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.3 Matrix Inversion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.4 Exact Solution of m Equations in n Unknowns . . . . . . . . . . . . . 32
2.5 Solving Linear Equations Efficiently . . . . . . . . . . . . . . . . . . 39
2.6 LU Decomposition . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3 The Simplex Method 45
3.1 A Simple Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3.2 Vertices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
3.3 The Phase II Procedure . . . . . . . . . . . . . . . . . . . . . . . . . 53
3.4 The Phase I Procedure . . . . . . . . . . . . . . . . . . . . . . . . . . 60
3.5 Finite Termination . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
vii
viii Contents
3.5.1 The Nondegenerate Case . . . . . . . . . . . . . . . . . 65
3.5.2 Cycling . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
3.5.3 The General Case . . . . . . . . . . . . . . . . . . . . . 67
3.6 Linear Programs in Nonstandard Form . . . . . . . . . . . . . . . . . 72
3.6.1 Transforming Constraints and Variables . . . . . . . . . . 72
3.6.2 Scheme I . . . . . . . . . . . . . . . . . . . . . . . . . . 76
3.6.3 Scheme II . . . . . . . . . . . . . . . . . . . . . . . . . 80
3.6.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . 86
4 Duality 89
4.1 Duality and Rank in Linear Systems . . . . . . . . . . . . . . . . . . 89
4.2 Duality in Linear Programming . . . . . . . . . . . . . . . . . . . . . 94
4.3 Interpretation of Linear Programming Duality . . . . . . . . . . . . . 96
4.4 Duality Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
4.5 KKT Optimality Conditions . . . . . . . . . . . . . . . . . . . . . . . 100
4.6 Dual Simplex Method . . . . . . . . . . . . . . . . . . . . . . . . . . 102
4.7 General Linear Programs . . . . . . . . . . . . . . . . . . . . . . . . 107
4.8 Big M Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
4.9 Applications of Duality . . . . . . . . . . . . . . . . . . . . . . . . . 112
5 Solving Large Linear Programs 117
5.1 Foundations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
5.1.1 Basic Feasible Solutions and Basis Matrices . . . . . . . 118
5.1.2 Geometric Viewpoint . . . . . . . . . . . . . . . . . . . 121
5.2 The Revised Simplex Method . . . . . . . . . . . . . . . . . . . . . . 123
5.2.1 Upper and Lower Bounds . . . . . . . . . . . . . . . . . 129
5.2.2 Generating Basic Feasible Solutions . . . . . . . . . . . 134
5.2.3 Basis Updates . . . . . . . . . . . . . . . . . . . . . . . 139
5.2.4 Advanced Pivot Selection Mechanisms . . . . . . . . . . 142
5.3 Network Flow Problems . . . . . . . . . . . . . . . . . . . . . . . . . 143
5.3.1 Minimum-Cost Network Flow . . . . . . . . . . . . . . . 144
5.3.2 Shortest-Path Problem . . . . . . . . . . . . . . . . . . . 145
5.3.3 Max-Flow Problem . . . . . . . . . . . . . . . . . . . . 146
5.3.4 Transportation Problem . . . . . . . . . . . . . . . . . . 147
5.3.5 Assignment Problem . . . . . . . . . . . . . . . . . . . . 149
5.3.6 Network Simplex Method . . . . . . . . . . . . . . . . . 149
6 Sensitivity and Parametric Linear Programming 151
6.1 Sensitivity Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
6.2 Adding New Variables or Constraints . . . . . . . . . . . . . . . . . . 155
6.3 Parametric Optimization of the Objective Function . . . . . . . . . . . 158
6.4 Parametric Optimization of the Right-Hand Side . . . . . . . . . . . . 164
7 Quadratic Programming and Complementarity Problems 169
7.1 Nonlinear Programs: Optimality Conditions . . . . . . . . . . . . . . 169
7.2 Quadratic Programming . . . . . . . . . . . . . . . . . . . . . . . . . 172
Contents ix
7.2.1 Basic Existence Result . . . . . . . . . . . . . . . . . . . 172
7.2.2 KKT Conditions . . . . . . . . . . . . . . . . . . . . . . 173
7.2.3 Duality . . . . . . . . . . . . . . . . . . . . . . . . . . . 176
7.3 Linear Complementarity Problems . . . . . . . . . . . . . . . . . . . 177
7.4 Lemke’s Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178
7.5 Bimatrix Games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185
7.5.1 Computing Nash Equilibria . . . . . . . . . . . . . . . . 186
7.5.2 Zero-Sum Games As Dual Linear Programs . . . . . . . 192
8 Interior-Point Methods 195
8.1 Motivation and Outline . . . . . . . . . . . . . . . . . . . . . . . . . 195
8.2 Newton’s Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197
8.3 Primal-Dual Methods . . . . . . . . . . . . . . . . . . . . . . . . . . 201
8.3.1 An Affine-Scaling Approach . . . . . . . . . . . . . . . . 202
8.3.2 Path-Following Methods . . . . . . . . . . . . . . . . . . 204
8.3.3 Solution of the Linear System at Each Interior-Point
Iteration . . . . . . . . . . . . . . . . . . . . . . . . . . 208
8.3.4 Practical Primal-Dual Methods . . . . . . . . . . . . . . 209
8.4 Interior-Point vs. Simplex . . . . . . . . . . . . . . . . . . . . . . . . 212
8.5 Extension to Quadratic Programming . . . . . . . . . . . . . . . . . . 212
9 Approximation and Classification 217
9.1 Minimax Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217
9.2 Approximation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218
9.2.1 Chebyshev Approximation . . . . . . . . . . . . . . . . . 219
9.2.2 L1 Approximation . . . . . . . . . . . . . . . . . . . . . 221
9.2.3 Approximate Solutions to Systems with Inequality
Constraints . . . . . . . . . . . . . . . . . . . . . . . . . 223
9.2.4 Least-Squares Problems . . . . . . . . . . . . . . . . . . 224
9.3 Huber Estimation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227
9.4 Classification Problems . . . . . . . . . . . . . . . . . . . . . . . . . 230
A Linear Algebra, Convexity, and Nonlinear Functions 237
A.1 Linear Algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237
A.2 Convex Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239
A.3 Smooth Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242
A.4 Convex Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242
A.5 Quadratic Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . 244
A.6 Norms and Order Notation . . . . . . . . . . . . . . . . . . . . . . . 247
A.7 Taylor’s Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 249
B Summary of Available MATLAB Commands 251
B.1 Basic MATLAB Operations . . . . . . . . . . . . . . . . . . . . . . . 251
B.2 MATLAB Functions Defined in This Book . . . . . . . . . . . . . . . 252
x Contents
Bibliography 257
Index 261