Linear and Convex Optimization - A Mathematical Approach

Informationen zum Autor 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. Klappentext Discover the practical impacts of current methods of optimization with this approachable, one-stop resourceLinear 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 managementIdeal 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 Zusammenfassung Discover the practical impacts of current methods of optimization with this approachable, one-stop resourceLinear 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 f...

List 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 Operation

Product details

• Authors: M Veatch, Michael Veatch, Michael H Veatch, Michael H. Veatch
• Publisher: Wiley, John and Sons Ltd
• Languages: English
• Product format: Hardback
• Released: 31.12.2020
• EAN: 9781119664048
• ISBN: 978-1-119-66404-8
• No. of pages: 384
• Subjects: Natural sciences, medicine, IT, technology > Mathematics > Arithmetic, algebra; Social sciences, law, business > Business > Management; Betriebswirtschaft, Mathematik, Optimierung, Optimization, Lineare Algebra, Mathematics, Business & management, Linear Algebra, Wirtschaft u. Management, Betriebswirtschaft u. Operationsforschung, Management Science/Operational Research