vanderbei_linear-programming_ed-4.pdfThis book is

文件名称: vanderbei_linear-programming_ed-4.pdf

所属分类: 专业指导

开发工具:

文件大小: 8mb

下载次数: 0

上传时间: 2019-07-15

提供者: jeffc*****

下载 (8mb)

不能下载？报告错误

详细说明：This book is about constrained optimization. It begins with a thorough treatment of linear programming and proceeds to convex analysis, network flows, integer programming, quadratic programming, and convex optimization. Along the way, dynamic programming and the linear complementarity problem are toRobert j. vanderbei Linear Programming Foundations and extensions Fourth edition ② Springer Robert j vanderbei Department of Operations Research and Financial Engineering Princeton University Princeton, New Jersey, USA ISSN0884-8289 ISBN978-1-4614-76290 ISBN978-1-4614-7630-6( eBook) DOI10.1007/978-1-4614-7630-6 Springer New York Heidelberg dordrecht London Library of Congress Control Number: 2013939593 o Springer Science+ Business Media New York 2014 This work is subject to copyright. All rights are reserved by the publisher, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation broadcasting, reproduction on microfilms or in any other physical way, and transmission or information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology now known or hereafter developed. Exempted from this legal reservation are brief excerpts in connection with reviews or scholarly analysis or material supplied specifically for the purpose of being entered and executed on a computer system, for exclusive use by the purchaser of the work. Duplication o this publication or parts thereof is permitted only under the provisions of the Copyright Law of the Publisher's location, in its current version, and permission for use must always be obtained from Springer Permissions for use may be obtained through rights link at the copyright clearance Center. violations are liable to prosecution under the respective Copyright Law The use of general descriptive names, registered names, trademarks, service marks, etc. in this publica tion does not imply, even in the absence of a specific statement, that such names are exempt from the relevant protective laws and regulations and therefore free for general use While the advice and information in this book are believed to be true and accurate at the date of pub lication, neither the authors nor the editors nor the publisher can accept any legal responsibility for any errors or omissions that may be made. The publisher makes no warranty, express or implied, with respect to the material contained herein Printed on acid-free paper SpringerispartofSpringerScience+businessMedia(www.springer.com) To Krisadee Marisa and diana Preface This book is about constrained optimization. It begins with a thorough treat ment of linear programming and proceeds to convex analysis, network flows, integer programming, quadratic programming, and convex optimization. Along the way, dynamic programming and the linear complementarity problem are touched on as well The book aims to be a first introduction to the subject. Specific examples and concrete algorithms precede more abstract topics. Nevertheless, topics covered are developed in some depth, a large number of numerical examples are worked out in detail, and many recent topics are included, most notably interior-point methods The exercises at the end of each chapter both illustrate the theory and, in some cases extend it Prerequisites. The book is divided into four parts. The first two parts assume a background only in linear algebra. For the last two parts some knowledge of multivariate calculus is necessary. In particular, the student should know how to use Lagrange multipliers to solve simple calculus problems in 2 and 3 dimensions Associated software. It is good to be able to solve small problems by hand but the problems one encounters in practice are large, requiring a computer for their solution. Therefore, to fully appreciate the subject, one needs to solve large(prac tical) problems on a computer. An important feature of this book is that it comes with software implementing the major algorithms described herein. At the time of writing, software for the following five algorithms is available The two-phase simplex method as shown in Figure 6.1 The self-dual simplex method as shown in Figure 7.1 The path-following method as shown in Figure 18.1 The homogeneous self-dual method as shown in Figure 22.1 The long-step homogeneous self-dual method as described in Exerci 22.4. The programs that implement these algorithms are written in C and can be easily compiled on most hardware platforms. Students/instructors are encouraged to install and compile these programs on their local hardware. Great pains have been taken to make the source code for these programs readable(see Appendix a) In particular, the names of the variables in the programs are consistent with the notation of this book PREFACE There are two ways to run these programs The first is to prepare the input in a standard computer-file format, called MPS format, and to run the program usin such a file as input. The advantage of this input format is that there is an archiv of problems stored in this format, called the netlib suite, that one can download and use immediately(a link to the netliB suite can be found at the web site men tioned below). But, this format is somewhat archaic and, in particular, it is not easy to create these files by hand Therefore the programs can also be run from within a problem modeling system called AMPL. AMPL allows one to describe mathemat ical programming problems using an easy to read, yet concise, algebraic notation To run the programs within AMPL, one simply tells amPl the name of the solver- program before asking that a problem be solved. The text that describes AMPL, Fourer et al.(1993 )makes an excellent companion to this book. It includes a dis cussion of many practical linear programming problems. It also has lots of exercises to hone the modeling skills of the student Several interesting computer projects can be suggested Here are a few sugges tions regarding the simplex codes Incorporate the partial pricing strategy(see Section 8.7) into the two- phase simplex method and compare it with full pricing Incorporate the steepest-edge pivot rule(see Section 8. 8)into the two phase simplex method and compare it with the largest-coefficient rule e modify the code for either variant of the simplex method so that it can treat bounds and ranges implicitly(see Chapter 9), and compare the per- formance with the explicit treatment of the supplied codes Implement awarm-start' capability so that the sensitivity analyses dis cussed in Chapter 7 can be done e Extend the simplex codes to be able to handle integer programming prol lems using the branch-and-bound method described in Chapter 23 As for the interior-point codes, one could try some of the following projects: Modify the code for the path-following algorithm so that it implements the affine-scaling method(see Chapter 21), and then compare the two methods Modify the code for the path-following method so that it can treat bounds and ranges implicitly(see Section 20.3), and compare the performance against the explicit treatment in the given code Modify the code for the path-following method to implement the higher order method described in Exercise 18.5. Compare Extend the path-following code to solve quadratic programming problems using the algorithm shown in Figure 24.3 Further extend the code so that it can solve convex optimization problems using the algorithm shown in Figure 25.2 And, perhaps the most interesting project of all Compare the simplex codes against the interior-point code and decide for yourself which algorithm is better on specific families of problems PREFACE The software implementing the various algorithms was developed using consistent data structures and so making fair comparisons should be straightforward. The soft ware can be downloaded from the following web site http://www.princeton.edu/rvdb/lpbook/ If, in the future, further codes relating to this text are developed (for example, a self-dual network simplex code), they will be made available through this web site Features. Here are some other features that distinguish this book from others The development of the simplex method leads to Dantzig's parametric self-dual method, a randomized variant of this method is shown to be immune to the travails of degeneracy The book gives a balanced treatment to both the traditional simplex method d the newer interior-point methods. The notation and analysis is de veloped to be consistent across the methods. As a result, the self-dual simplex method emerges as the variant of the simplex method with most connections to interior-point methods From the beginning and consistently throughout the book, linear program- ming problems are formulated in symmetric form. By highlighting sym metry throughout, it is hoped that the reader will more fully understand and appreciate duality theory. By slightly changing the right-hand side in the Klee-Minty problem, we are able to write down an explicit dictionary for each vertex of the Klee Minty problem and thereby uncover(as a homework problem )a simple, elegant argument why the Klee-Minty problem requires 2-1 pivots to solve e The chapter on regression includes an analysis of the expected number of pivots required by the self-dual variant of the simplex method. This analysis is supported by an empirical study There is an extensive treatment of modern interior-point methods ing the primal-dual method, the affine-scaling method, and the self-dual path-following method In addition to the traditional applications, which come mostly from busi- ness and economics, the book features other important applications such as the optimal design of truss-like structures and L-regression Exercises on the web. There is always a need for fresh exercises. Hence, I have created and plan to maintain a growing archive of exercises specifically created for use in conjunction with this book. This archive is accessible from the books web site http://www.princeton.edu/rvdb/lpbook/ The problems in the archive are arranged according to the chapters of this book and use notation consistent with that developed herein Advice on solving the exercises. Some problems are routine while others are fairly challenging. Answers to some of the problems are given at the back of the book PREFACE In general, the advice given to me by Leonard Gross(when I was a student) should help even on the hard problems: follow your nose Audience. This book evolved from lecture notes developed for my introductory graduate course in linear programming as well as my upper-level undergraduate course. A reasonable undergraduate syllabus would cover essentially all of Part 1 (Simplex method and Duality ) the first two chapters of Part 2(Network Flows and Applications), and the first chapter of Part 4(Integer Programming). At the graduate level, the syllabus should depend on the preparation of the students. For a well-prepared class, one could cover the material in Parts I and 2 fairly quickly and then spend more time on Parts 3(Interior-Point Methods and 4(Extensions) Dependencies. In general, Parts 2 and 3 are completely independent of each other. Both depend, however, on the material in Part I. The first Chapter in Part 4 (Integer Programming) depends only on material from Part 1, whereas the remaining chapters build on part 3 material Acknowledgments. My interest in linear programming was sparked by robert Garfinkel when we shared an office at bell labs. i would like to thank him for his constant encouragement, advice, and support. This book benefited greatly from the thoughtful comments and suggestions of David bernstein and michael Todd I would also like to thank the following colleagues for their help Ronny Ben-Tal eslie Hall, Yoshi ikura, Victor Klee, Irvin Lustig, Avi Mandelbaum, Marc Meke ton, Narcis Nabona, James Orlin, Andrzej ruszczynski, and Henry Wolkowicz. I would like to thank Gary Folven at Kluwer and Fred Hillier, the series editor, for encouraging me to undertake this project. I would like to thank my students for finding many typos and occasionally more serious errors: John Gilmartin, Jacinta Warnie, Stephen Woolbert, Lucia Wu, and Bing Yang. My thanks to Erhan Cinlar for the many times he offered advice on questions of style. I hope this book re- fects positively on his advice. Finally, I would like to acknowledge the support of the National Science Foundation and the air force office of scientific Research for supporting me while writing this book. In a time of declining resources, I am especially grateful for their support Princeton. NJ USA Robert j. vanderbei Preface to 2nd edition For the 2nd edition, many new exercises have been added also i have worked hard to develop online tools to aid in learning the simplex method and duality theory. These online tools can be found on the book's web page http://www.princeton.edu/orvdb/lpbook/ and are mentioned at appropriate places in the text besides the learning tools i have created several online exercises These exercises use randomly generated problems and therefore represent a virtually unlimited collection of"routine" exercises that can be used to test basic understanding. Pointers to these online exercises are i cluded in the exercises sections at appropriate points Some other notable changes include The chapter on network flows has been completely rewritten. Hopefully, the new version is an improvement on the original Two different fonts are now used to distinguish between the set of basic indices and the basis matrix The first edition placed great emphasis on the symmetry between the pri mal and the dual(the negative transpose property). The second edition carries this further with a discussion of the relationship between the basic and nonbasic matrices B and N as they appear in the primal and in the dual. We show that, even though these matrices differ ( they even have different dimensions), bN in the dual is the negative transpose of the corresponding matrix in the primal In the chapters devoted to the simplex method in matrix notation, the col- lection of variables 21, 22,..., in, 91, 92, .. 9m was replaced, in the first edition, with the single array of variables 91, 92, .. n+m. This caused great confusion as the variable i in the original notation was changed to yn+i in the new notation. For the second edition, I have changed the notation for the single array to 21, 22, .., 2n+m A number of figures have been added to the chapters on convex analysis and on network flow problems The algorithm refered to as the primal-dual simplex method in the first edition has been renamed the parametric self-dual simplex method in ac- cordance with prior standard usage

(系统自动生成,下载前可以参看下载内容)