Top
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:
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
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.
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
The New copy of this book will include any supplemental materials advertised. Please check the title of the book to determine if it should include any access cards, study guides, lab manuals, CDs, etc.
The Used, Rental and eBook copies of this book are not guaranteed to include any supplemental materials. Typically, only the book itself is included. This is true even if the title states it includes any access cards, study guides, lab manuals, CDs, etc.
Need Help? Copyright © 1999-2026
