Desire to improve drives many human activities. Optimization can be seen as a means for identifying better solutions by utilizing a scientific and mathematical approach. In addition to its widespread applications, optimization is an amazing subject with very strong connections to many other subjects and deep interactions with many aspects of computation and theory. The main goal of this textbook is to provide an attractive, modem, and accessible route to learning the fundamental ideas in optimization for a large group of students with varying backgrounds and abilities. The only background required for the textbook is a first-year linear algebra course (some readers may even be ready immediately after finishing high school). However, a course based on this book can serve as a header course for all optimization courses. As a result, an important goal is to ensure that the students who successfully complete the course are able to proceed to more advanced optimization courses.
Another goal of ours was to create a textbook that could be used by a large group of instructors, possibly under many different circumstances. To a degree, we tested this over a fbur-year period. Including the three of us, 12 instructors used the drafts of the book for two different courses. Students in various programs (majors), including accounting, business, software engineering, statistics, actuarial science, operations research, applied mathematics, pure mathematics, computational mathematics, computer science, combinatorics and optimization, have taken these courses. We believe that the book will be suitable for a wide range of students (mathematics, mathematical sciences including computer science, engineering including software engineering, and economics). To accomplish our goals, we operated with the following rules:
1.Always motivate the subject/algorithm/theorem (leading by modem, relatable examples which expose important aspects of the subject/algorithm/theorem).
2.Keep the text as concise and as focused as possible (this meant, that some of the more advanced or tangential topics are either treated in advanced sections or in starred exercises).
3.Make sure that some of the pieces are modular so that an instructor or a reader can choose to skip certain parts of the text smoothly. (Please see the potential usages of the book below.)

Preface page ix

1 Introduction 1

      1.1 A first example 2

      1.1.1 The formulation 3

      1.1.2 Correctness 4

      1.2 Linear programs 5

      1.2.1 Multiperiod models 7

      1.3 Integer programs 14

      1.3.1 Assignment problem 15

      1.3.2 Knapsack problem 17

      1.4 Optimization problems on graphs 26

      1.4.1Shortest path problem 27

      1.4.2 Minimum cost perfect matching 28

      1.5 Integer programs continued 30

      1.5.1 Minimum cost perfect matching 30

      1.5.2 Shortest path problem 32

      1.6 Nonlinear programs 37

      1.6.1 Pricing a tech gadget 37

      1.6.2 Finding a closest point feasible in an LP 39

      1.6.3 Finding a "central" feasible solution of an LP 39

      1.7 Overview of the book 42

      1.8 Further reading and notes 43

2 Solving linear programs 44

      2.1 Possible outcomes 44

      2.1.1 Infeasible linear programs 45

      2.1.2 Unbounded linear programs 47

      2.1.3 Linear programs with optimal solutions 48

      2.2 Standard equality form 50

      2.3 A simplex iteration 55

      2.4 Bases and canonical forms 57

      2.4.1 Bases 57

      2.4.2 Canonical forms 58

      2.5 The simplex algorithm 64

      2.5.1 An example with an optimal solution 64

      2.5.2 An unbounded example 67

      2.5.3 Formalizing the procedxire 68

      2.6 Finding feasible solutions 75

      2.6.1 General scheme 75

      2.6.2 The two phase simplex algorithm-an example 78

      2.6.3 Consequences 80

      2.7 Simplex via tableaus* 82

      2.7.1 Pivoting 82

      2.7.2 Tableaus 84

      2.8 Geometry 85

      2.8.1Feasible region of LPs and polyhedra 86

      2.8.2 Convexity 88

      2.8.3 Extreme points 89

      2.8.4 Geometric interpretation of the simplex algorithm 92

      2.9 Further reading and notes 97

3 Duality through examples 99

      3.1 The shortest path problem 99

      3.1.1 An intuitive lower bound 100

      3.1.2 A general argument - weak duality 103

      3.1.3 Revisiting the intuitive lower bound 106

      3.1.4 An algorithm 111

      3.1.5 Correctness of the algorithm 114

      3.2 Minimum cost perfect matching in bipartite graphs 116

      3.2.1An intuitive lower bound 117

      3.2.2 A general argument-weak duality 119

      3.2.3 Revisiting the intuitive lower bound 122

      3.2.4 An algorithm 125

      3.2.5 Correctness of the algorithm 129

      3.2.6 Finding perfect matchings in bipartite graphs* 133

      3.3 Further reading and notes 140

4 Duality theory 142

      4.1 Weak duality 142

      4.2 Strong duality 150

      4.3 A geometric characterization of optimality 153

      4.3.1 Complementary slackness 154

      4.3.2 Geometry 158

      4.4 Farkas, lemma* 163

      4.5 Further reading and notes 165

5 Applications of duality* 166

      5.1 Approximation algorithm for set-cover 166

      5.1.1A primal-dual algorithm 167

      5.1.2 Greed is good ... at least sometimes 170

      5.1.3 Discussion 172

      5.2 Economic interpretation 173

      5.3 The maximum-flow-minimum-cut theorem 176

      5.3.1 Totally unimodular matrices 178

      5.3.2 Applications to 5r-flows 179

6 Solving integer programs 183

      6.1 Integer programs versus linear programs 183

      6.2 Cutting planes 188

      6.2.1Cutting planes and the simplex algorithm 190

      6.3 Branch and bound 196

      6.4 Traveling salesman problem and a separation algorithm* 201

      6.5 Further reading and notes 204

7 Nonlinear optimization 206

      7.1 Some examples 206

      7.2 Some nonlinear programs are very hard 208

      7.2.1 NLP versus 0,1 integer programming 208

      7.2.2 Hard small-dimensional instances 209

      7.3 Convexity 210

      7.3.1 Convex functions and epigraphs 210

      7.3.2 Level sets and feasible region 213

      7.4 Relaxing convex NLPs 215

      7.4.1Subgradients 216

      7.4.2 Supporting halfspaces 216

      7.5 Optimality conditions for the differentiable case 218

      7.5.1 Sufficient conditions for optimality 218

      7.5.2 Differentiability and gradients 220

      7.5.3 A Karush-Kuhn-Tucker theorem 221

      7.6 Optimality conditions based on Lagrangians 223

      7.7 Nonconvex optimization problems 227

      7.7.1 The Karush-Kuhn-Tucker theorem fbr nonconvex problems* 227

      7.7.2 Convex relaxation approach to nonconvex problems* 230

      7.8 Interior-point method fbr linear programs* 234

      7.8.1 A polynomial-time interior-point algorithm* 239

      7.9 Further reading and notes 242

Appendix A Computational complexity 244

      A.1 What is a fast (resp. slow) algorithm? 244

      A.1.1 The big "O" notation 245

      A.1.2 Input size and running time 245

      A.1.3 Polynomial and exponential algorithms 247

      A.2 Examples of fast and slow algorithms 249

      A.2.1 Linear programming 249

      A.2.2 Other algorithms in this book 251

      A.3 The classes NP, co-NP and P 252

      A.3.1 Decision problems 252

      A.3.2 The class* 253

      A.3.3 The class co-NP 255

      A.3.4 The class P 256

      A.4 Hard problems 258

      A.4.1 Reducibility 258

      A.4.2 NP-complete problems 260

      A.4.3 Complexity as guide 261

      A.4.4 Easy versus hard problems 261

References 263

Index 267

中科院文献情报中心