Operations research and mathematical programming would not be as advanced today without the many advances in interiorpointmethods during the last decade. These methods can now solve very efficiently and robustly ...
详细信息
ISBN:
(数字)9781475755619
ISBN:
(纸本)9780792344308;9781441947727
Operations research and mathematical programming would not be as advanced today without the many advances in interiorpointmethods during the last decade. These methods can now solve very efficiently and robustly large scale linear, nonlinear and combinatorial optimization problems that arise in various practical applications. The main ideas underlying interiorpointmethods have influenced virtually all areas of mathematical programming including: analyzing and solving linear and nonlinearprogramming problems, sensitivity analysis, complexity analysis, the analysis of Newton's method, decomposition methods, polynomial approximation for combinatorial problems etc. This book covers the implications of interior techniques for the entire field of mathematical programming, bringing together many results in a uniform and coherent way. For the topics mentioned above the book provides theoretical as well as computational results, explains the intuition behind the main ideas, gives examples as well as proofs, and contains an extensive up-to-date bibliography.;The book is intended for students, researchers and practitioners with a background in operations research, mathematics, mathematical programming, or statistics.
This book describes the rapidly developing field of interiorpointmethods (IPMs). An extensive analysis is given of path-following methods for linearprogramming, quadratic programming and convex programming. Thes...
详细信息
ISBN:
(数字)9789401111348
ISBN:
(纸本)9780792327349;9789401044967
This book describes the rapidly developing field of interiorpointmethods (IPMs). An extensive analysis is given of path-following methods for linearprogramming, quadratic programming and convex programming. These methods, which form a subclass of interiorpointmethods, follow the central path, which is an analytic curve defined by the problem. Relatively simple and elegant proofs for polynomiality are given. The theory is illustrated using several explicit examples. Moreover, an overview of other classes of IPMs is given. It is shown that all these methods rely on the same notion as the path-following methods: all these methods use the central path implicitly or explicitly as a reference path to go to the optimum.;For specialists in IPMs as well as those seeking an introduction to IPMs. The book is accessible to any mathematician with basic mathematical programming knowledge.
One has to make everything as simple as possible but, never more simple. Albert Einstein Discovery consists of seeing what every body has seen and thinking what nobody has thought. Albert S. ent_Gyorgy; The prim...
详细信息
ISBN:
(数字)9781461334491
ISBN:
(纸本)9780792342014;9781461334514
One has to make everything as simple as possible but, never more simple. Albert Einstein Discovery consists of seeing what every body has seen and thinking what nobody has thought. Albert S. ent_Gyorgy; The primary goal of this book is to provide an introduction to the theory of interiorpointmethods (IPMs) in Mathematical programming. At the same time, we try to present a quick overview of the impact of extensions of IPMs on smooth nonlinear optimization and to demonstrate the potential of IPMs for solving difficult practical problems. The Simplex Method has dominated the theory and practice of mathematical pro gramming since 1947 when Dantzig discovered it. In the fifties and sixties several attempts were made to develop alternative solution methods. At that time the prin cipal base of interiorpointmethods was also developed, for example in the work of Frisch (1955), Caroll (1961), Huard (1967), Fiacco and McCormick (1968) and Dikin (1967). In 1972 Klee and Minty made explicit that in the worst case some variants of the simplex method may require an exponential amount of work to solve linearprogramming (LP) problems. This was at the time when complexity theory became a topic of great interest. People started to classify mathematical programming prob lems as efficiently (in polynomial time) solvable and as difficult (NP-hard) problems. For a while it remained open whether LP was solvable in polynomial time or not. The break-through resolution ofthis problem was obtained by Khachijan (1989).
In;, both boundary (simplex) and interiorpointmethods are derived from the complementary slackness theorem and, unlike most books, the duality theorem is derived from Farkas's Lemma, which is proved as a conv...
详细信息
ISBN:
(数字)9781461523116
ISBN:
(纸本)9780792396222;9781461359777
In;, both boundary (simplex) and interiorpointmethods are derived from the complementary slackness theorem and, unlike most books, the duality theorem is derived from Farkas's Lemma, which is proved as a convex separation theorem. The tedium of the simplex method is thus avoided.;A new and inductive proof of Kantorovich's Theorem is offered, related to the convergence of Newton's method. Of the boundary methods, the book presents the (revised) primal and the dual simplex methods. An extensive discussion is given of the primal, dual and primal-dual affine scaling methods. In addition, the proof of the convergence under degeneracy, a bounded variable variant, and a super-linearly convergent variant of the primal affine scaling method are covered in one chapter. Polynomial barrier or path-following homotopy methods, and the projective transformation method are also covered in the interiorpoint chapter. Besides the popular sparse Cholesky factorization and the conjugate gradient method, new methods are presented in a separate chapter on implementation. These methods use LQ factorization and iterative techniques.
linearprogramming represents one of the major applications of mathematics to business, industry, and economics. It provides a methodology for optimizing an output given that is a linear function of a number of inputs...
详细信息
ISBN:
(数字)9780387215693
ISBN:
(纸本)9780387986135;9781441931405
linearprogramming represents one of the major applications of mathematics to business, industry, and economics. It provides a methodology for optimizing an output given that is a linear function of a number of inputs. George Dantzig is widely regarded as the founder of the subject with his invention of the simplex algorithm in the 1940's. This second volume is intended to add to the theory of the items discussed in the first volume. It also includes additional advanced topics such as variants of the simplex method; interiorpointmethods (early and current methods), GUB, decomposition, integer programming, and game theory. Graduate students in the fields of operations research, industrial engineering and applied mathematics will find this volume of particular interest.
暂无评论