Linear and convex optimization : a mathematical approach / Michael Veatch, Gordon College.
By: Veatch, Michael H [author.]
Language: English Publisher: Hoboken, NJ : Wiley, 2021Copyright date: ©2021Description: 1 online resourceContent type: text Media type: computer Carrier type: online resourceISBN: 9781119664048; 9781119664055; 1119664055; 9781119664024; 1119664020; 9781119664079; 1119664071Subject(s): Mathematical optimization | Nonlinear programming | Convex functionsGenre/Form: Electronic books.DDC classification: 519.6 LOC classification: QA402.5Online resources: Full text available at Wiley Online Library Click here to view| Item type | Current location | Home library | Call number | Status | Date due | Barcode | Item holds |
|---|---|---|---|---|---|---|---|
EBOOK
|
COLLEGE LIBRARY | COLLEGE LIBRARY | 519.6 V486 2021 (Browse shelf) | Available | CL-51265 |
Includes index.
Includes bibliographical references (pages 355-359) and index.
Table of Contents
Preface xi
About the Companion Website xvii
1 Introduction to Optimization Modeling 1
1.1 Who Uses Optimization? 1
1.2 Sending Aid to a Disaster 3
1.3 Optimization Terminology 9
1.4 Classes of Mathematical Programs 11
Problems 16
2 Linear Programming Models 19
2.1 Resource Allocation 19
2.2 Purchasing and Blending 23
2.3 Workforce Scheduling 29
2.4 Multiperiod Problems 30
2.5 Modeling Constraints 34
2.6 Network Flow 36
Problems 44
3 Linear Programming Formulations 55
3.1 Changing Form 55
3.2 Linearization of Piecewise Linear Functions 57
3.3 Dynamic Programming 62
Problems 66
4 Integer Programming Models 71
4.1 Quantitative Variables and Fixed Costs 72
4.2 Set Covering 74
4.3 Logical Constraints and Piecewise Linear Functions 77
4.4 Additional Applications 81
4.5 Traveling Salesperson and Cutting Stock Problems 86
Problems 90
5 Iterative Search Algorithms 99
5.1 Iterative Search and Constructive Algorithms 100
5.2 Improving Directions and Optimality 106
5.3 Computational Complexity and Correctness 112
Problems 116
6 Convexity 121
6.1 Convex Sets 122
6.2 Convex and Concave Functions 127
Problems 131
7 Geometry and Algebra of LPs 133
7.1 Extreme Points and Basic Feasible Solutions 134
7.2 Optimality of Extreme Points 137
7.3 Linear Programs in Canonical Form 140
7.4 Optimality Conditions 145
7.5 Optimality for General Polyhedra 146
Problems 149
8 Duality Theory 153
8.1 Dual of a Linear Program 153
8.2 Duality Theorems 158
8.3 Complementary Slackness 162
8.4 Lagrangian Duality 164
8.5 Farkas’ Lemma and Optimality 167
Problems 170
9 Simplex Method 173
9.1 Simplex Method From a Known Feasible Solution 174
9.2 Degeneracy and Correctness 183
9.3 Finding an Initial Feasible Solution 186
9.4 Computational Strategies and Speed 192
Problems 200
10 Sensitivity Analysis 203
10.1 Graphical Sensitivity Analysis 204
10.2 Shadow Prices and Reduced Costs 208
10.3 Economic Interpretation of the Dual 219
Problems 221
11 Algorithmic Applications of Duality 225
11.1 Dual Simplex Method 226
11.2 Network Simplex Method 234
11.3 Primal-Dual Interior Point Method 246
Problems 256
12 Integer Programming Theory 261
12.1 Linear Programming Relaxations 262
12.2 Strong Formulations 263
12.3 Unimodular Matrices 269
Problems 272
13 Integer Programming Algorithms 275
13.1 Branch and Bound Methods 275
13.2 Cutting Plane Methods 284
Problems 293
14 Convex Programming: Optimality Conditions 297
14.1 KKT Optimality Conditions 297
14.2 Lagrangian Duality 306
Problems 312
15 Convex Programming: Algorithms 317
15.1 Convex Optimization Models 320
15.2 Separable Programs 323
15.3 Unconstrained Optimization 325
15.4 Quadratic Programming 329
15.5 Primal-dual Interior Point Method 331
Problems 339
A Linear Algebra and Calculus Review 343
A.1 Sets and Other Notation 343
A.2 Matrix and Vector Notation 343
A.3 Matrix Operations 345
A.4 Matrix Inverses 347
A.5 Systems of Linear Equations 348
A.6 Linear Independence and Rank 350
A.7 Quadratic Forms and Eigenvalues 351
A.8 Derivatives and Convexity 352
Bibliography 355
Index 361
"This book introduces and explains the mathematics behind convex and linear optimization, focusing on developing insights in problem complexity, modelling and algorithms. Although many introductory books pay little attention to nonlinear optimization, convex problems deserve attention because of their many applications and the fast algorithms that have been developed to solve them. The main algorithms used in linear, integer, and convex optimization are presented in a mathematical style. The emphasis is on what makes a class of problems practically solvable and developing insight into algorithms geometrically. Principles of algorithm design are explained, making it accessible to those with no background in algorithms. The important issue of speed of algorithms is discussed and addressed theoretically where appropriate. A breadth of recent applications are presented to demonstrate the many areas in which optimization is successfully used. The process of formulating optimization problems is included throughout, both to develop the ability to formulate large problems and to appreciate that some formulations are more tractable"-- Provided by publisher.
About the Author
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.
There are no comments for this item.