Optimization

George L. Nemhauser0444872841, 9780444872845

Hardbound. Collected together in this book are ten expository articles on the most important topics in optimization, written by leading experts in the field. The book provides a primary reference for those performing research in some area of optimization or for those who have an elementary basic knowledge of optimization techniques but wish to learn the most up-to-date and efficient algorithms for particular classes of problems. The first sections of each chapter are expository and therefore accessible to master’s level graduate students. However, the chapters also contain advanced material on current topics of interest to researchers. For instance, there are chapters which describe the polynomial-time linear programming algorithms of Khachian and Karmarkar and the techniques used to solve combinatorial and integer programming problems, an order of magnitude larger than was possible just a few years ago. The work contains a coherent view of the important

---

Table of contents :
Cover……Page 1
Date-line……Page 2
Preface……Page 3
Contents……Page 9
1. Preliminaries……Page 13
2. Newton’s method……Page 20
3. Derivative approximations……Page 25
4. Globally convergent methods……Page 47
5. Non-Taylor series methods……Page 65
6. Some current research directions……Page 70
References……Page 78
1. Introduction……Page 85
2. Geometric interpretation……Page 90
3. The simplex method……Page 97
4. Duality and sensitivity analysis……Page 107
5. Exploiting structure……Page 120
6. Column generation and the decomposition principle……Page 132
7. The complexity of linear programming……Page 142
8. The elipsoid method……Page 145
9. Karmarkar’s projective scaling algorithm……Page 153
References……Page 177
1. Equality constraints……Page 183
2. Equality-constrained quadratic programming……Page 188
3. Overview of methods……Page 192
4. The quadratic penality function……Page 193
5. The $l_1$ penalty function……Page 197
6. Sequential quadratic programming methods……Page 198
7. Sequential linearly constrained methods……Page 205
8. Augmented Lagrangian methods……Page 207
9. Inequality constraints……Page 208
10. Inequality-constrained quadratic programming……Page 212
11. Penalty-function methods for inequalities……Page 213
12. Sequential quadratic programming methods……Page 214
14. Augmented Lagrangian methods……Page 216
15. Barrier-function methods……Page 217
References……Page 220
1. Introduction……Page 223
2. Basic properties of network flows……Page 248
3. Shortest paths……Page 261
4. Maximum flows……Page 277
5. Minimum cost flows……Page 299
6. Reference notes……Page 344
References……Page 372
1. Min-max relations, NP and co-NP……Page 383
2. Weighted min-max relations and polyhedra……Page 389
3. Basic theory of polyhedra and linear systems……Page 395
4. Linear systems and combinatorial optimization……Page 406
5. Separation and partial descriptions……Page 416
6. Polarity, blocking and antiblocking……Page 421
7. Strengthening min-max theorems I: Essential inequalities……Page 425
8. Strengthening min-max theorems II: Dual integrality……Page 431
9. Dimension……Page 439
10. Adjacency……Page 440
11. Extended formulations and projection……Page 444
Appendix: P. NP and co-NP……Page 449
References……Page 452
1. Introduction……Page 459
2. Integer programming models……Page 461
3. Choices in model formulation……Page 468
4. Properties of integral polyhedra and computational complexity……Page 471
5. Relaxation and valid inequalities……Page 475
6. Duality……Page 488
7. Cutting plane algorithms……Page 497
8. Branch-and-bound……Page 510
9. Heuristics……Page 518
10. Notes……Page 529
References……Page 533
1. Introduction……Page 541
2. Examples of nonsmooth problems……Page 544
3. Failure of smooth methods……Page 549
4. Special methods for special problems……Page 551
5. Subgradient methods……Page 555
6. Bundle methods……Page 564
7. Directions for future developments……Page 573
8. Commented bibliography……Page 578
Bibliography……Page 581
1. Introduction: The model……Page 585
2. Expectation functionals……Page 589
3. Anticipative models and adaptive models……Page 600
4. Recourse problems……Page 605
5. Optimality conditions……Page 608
6. Approximations……Page 612
7. Solution procedures……Page 623
8. Stability and incomplete information……Page 632
9. References……Page 635
1. Introduction……Page 643
2. Partition and search……Page 647
3. Approximation and search……Page 650
4. Global decrease……Page 657
5. Improvement of local minima……Page 659
6. Enumeration of local minima……Page 661
7. Concluding remarks……Page 669
References……Page 671
1. Introduction……Page 675
2. Preference structures and classes of nondominatcd solutions……Page 676
3. Goal setting and compromise solutions……Page 681
4. Value functions……Page 690
5. Nondominated solutions and cone domination structures……Page 697
6. Linear cases and MC$^2$ simplex method……Page 705
References……Page 709
Subject Index……Page 713