Mathematics of Convex and Linear Optimization

1 Introduction to Optimization Modeling 1 1.1 Who Uses Optimization? 1 1.2 Sending Aid to a Disaster 4 The Modeling Process 11 1.3 Optimization Terminology 14 1.4 Classes of Mathematical Programs 17 Linear Programs 18 Integer Programs 21 Nonlinear Programs 24 Problems 25 2 Linear Programming Models 29 2.1 Resource Allocation 29 Production Process Models 34 2.2 Purchasing and Blending 35 Online Advertising Markets 38 Blending Problems 40 2.3 Workforce Scheduling 44 2.4 Multiperiod Problems 46 Multiperiod Financial Models 50 2.5 Modeling Constraints 52 2.6 Network Flow 55 Transportation Problems 55 Minimum Cost Network Flow 61 Shortest Path Problems 65 Problems 68 3 Linear Programming Formulations 75 3.1 Changing Form 75 Slack Variables 76 3.2 Linearization of Piece-wise Linear Functions 79 Linearization without Adding Constraints 83 Goal Programming 85 3.3 Dynamic Programming 86 Problems 93 4 Integer Programming Models 101 4.1 Quantitative Variables and Fixed Costs 102 Fixed Costs 103 4.2 Set Covering 105 4.3 Logical Constraints and Piecewise Linear Functions 110 Job Shop Scheduling 112 Linearization of Piecewise Linear Objectives 115 4.4 Additional Applications 117 Supermarket Markdowns 117 Warehouse Location and Transshipment 120 Locating Disaster Recovery Centers 122 4.5 Traveling Salesperson and Cutting Stock Problems 125 Cutting Stock Problem 129 Problems 131 5 Iterative Search Algorithms 141 5.1 Iterative Search and Constructive Algorithms 143 Constructive Algorithms 145 Exact and Heuristic Algorithms 148 Traveling Salesperson Heuristics 150 5.2 Improving Directions and Optimality 153 Feasible Directions and Step Size 156 Optimality Conditions 158 5.3 Computational Complexity and Correctness 163 Computational Complexity 166 Problems 169 6 Convexity 175 6.1 Convex Sets 177 6.2 Convex and Concave Functions 184 Combining Convex Functions 187 Problems 190 7 Geometry and Algebra of LPs 193 7.1 Extreme Points and Basic Feasible Solutions 194 Degeneracy 198 7.2 Optimality of Extreme Points 199 7.3 Linear Programs in Canonical Form 204 Basic Solutions in Canonical Form 206 7.4 Optimality Conditions 211 7.5 Optimality for General Polyhedra 214 Representation of Polyhedra 216 Problems 218 8 Duality Theory 223 8.1 Dual of a Linear Program 224 8.2 Duality Theorems 231 8.3 Complementary Slackness 238 8.4 Lagrangian Duality 241 8.5 Farkas' Lemma and Optimality 245 Problems 250 9 Simplex Method 255 9.1 Simplex Method From a Known Feasible Solution 257 Finding an Improving Direction 258 Determining the Step Size 259 Updating the Basis 261 Simplex Method 262 A Comment on Names 269 9.2 Degeneracy and Correctness 269 9.3 Finding an Initial Feasible Solution 274 Artificial Variables in the Basis 275 Two-Phase Simplex Method 275 9.4 Computational Strategies and Speed 284 Number of Iterations Required 285 Revised Simplex Method 287 Simplex Tableaus 290 Other Implementation Issues 295 Problems 296 10 Sensitivity Analysis 301 10.1 Graphical Sensitivity Analysis 302 Changes in the Right-hand Side 304 Changes in the Objective Function 308 10.2 Shadow Prices and Reduced Costs 308 Changes in the Right-hand Side 309 Sign of Shadow Prices 311 Changes in the Objective Function 312 Sensitivity Analysis Examples 315 Degeneracy 322 Parametric Programming 324 10.3 Economic Interpretation of the Dual 325 Problems 329 11 Algorithmic Applications of Duality 333 11.1 Dual Simplex Method 335 11.2 Network Simplex Method 348 Node-arc Incidence Matrix 351 Tree Solutions 352 Network Simplex 355 Transportation Problem 360 11.3 Primal-dual Interior Point Method 366 Newton's Method 369 Step Size 371 Choosing the Complementary Slackness Parameter 372 Barrier Function Interpretation 378 Problems 383 12 Integer Programming Theory 389 12.1 Linear Programming Relaxations 390 12.2 Strong Formulations 392 Aggregate Constraints 397 Bounding Integer Variables 399 12.3 Unimodular Matrices 400 Network Flow Problems 402 Unimodularity 405 Problems 406 13 Integer Programming Algorithms 411 13.1 Branch and Bound Methods 412 Branching and Trees 414 Choosing a Subproblem 415 Mixed Integer Programs 423 Integer Lagrangian Relaxations 423 13.2 Cutting Plane Methods 426 Gomory Cutting Plane Method 428 Generating Valid Inequalities by Rounding 432 Valid Inequalities for Binary Variables 436 Problems 440 14 Convex Programming: Optimality Conditions 445 14.1 KKT Optimality Conditions 446 Equality Constraints 447 Inequality Constraints 449 Convexity 452 KKT Conditions with Nonnegativity Constraints 455 Examples 457 14.2 Lagrangian Duality 461 Geometry of Primal and Dual Functions 463 Sensitivity Analysis 467 Problems 470 15 Convex Programming: Algorithms 477 15.1 Convex Optimization Models 481 15.2 Separable Programs 487 15.3 Unconstrained Optimization 489 Gradient Search 490 Newton's Method 491 Quasi-Newton Methods 494 15.4 Quadratic Programming 496 15.5 Primal-dual Interior Point Method 498 Barrier Problem 501 The Newton Step 502 Step Size and Slackness Parameter 504 Primal-dual Interior Point Algorithm 506 Problems 511 A Linear Algebra and Calculus Review 515 A.1 Sets and Other Notation 515 A.2 Matrix and Vector Notation 516 A.3 Matrix Operations 519 A.4 Matrix Inverses 521 A.5 Systems of Linear Equations 523 A.6 Linear Independence and Rank 526 A.7 Quadratic Forms and Eigenvalues 528 A.8 Derivatives and Convexity 531