Linear and Convex Optimization A Mathematical Approach

by Veatch, Michael H.

• ISBN13: 9781119664048
• ISBN10: 1119664047
• Edition: 1st
• Format: Hardcover
• Copyright: 2021-01-13
• Publisher: Wiley

Summary

Discover the practical impacts of current methods of optimization with this approachable, one-stop resource

Linear and Convex Optimization: A Mathematical Approach delivers a concise and unified treatment of optimization with a focus on developing insights in problem structure, modeling, and algorithms. Convex optimization problems are covered in detail because of their many applications and the fast algorithms that have been developed to solve them. 

Experienced researcher and undergraduate teacher Mike Veatch presents the main algorithms used in linear, integer, and convex optimization in a mathematical style with an emphasis on what makes a class of problems practically solvable and developing insight into algorithms geometrically. Principles of algorithm design and the speed of algorithms are discussed in detail, requiring no background in algorithms.

The book offers a breadth of recent applications to demonstrate the many areas in which optimization is successfully and frequently used, while the process of formulating optimization problems is addressed throughout. 

Linear and Convex Optimization contains a wide variety of features, including:

• Coverage of current methods in optimization in a style and level that remains appealing and accessible for mathematically trained undergraduates
• Enhanced insights into a few algorithms, instead of presenting many algorithms in cursory fashion
• An emphasis on the formulation of large, data-driven optimization problems
• Inclusion of linear, integer, and convex optimization, covering many practically solvable problems using algorithms that share many of the same concepts
• Presentation of a broad range of applications to fields like online marketing, disaster response, humanitarian development, public sector planning, health delivery, manufacturing, and supply chain management

Ideal for upper level undergraduate mathematics majors with an interest in practical applications of mathematics, this book will also appeal to business, economics, computer science, and operations research majors with at least two years of mathematics training.

Software to accompany the text can be found here: https://www.gordon.edu/michaelveatch/optimization

Author Biography

Michael H. Veatch, PhD, is Professor of Mathematics at Gordon College, in Wenham, Massachusetts, United States. He obtained his PhD in Operations Research from the Massachusetts Institute of Technology in Cambridge, MA and has been working in operations research for 40 years.

Table of Contents

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