In recent years, there has been intense work in linear and nonlinear programming, much of it centered on understanding and extending the ideas underlying N. Karmarkar's interior-point linear programming algorithm, which was presented in 1984. This interdisciplinary research was the subject of an AMS Summer Research Conference on Mathematical Developments Arising from Linear Programming, held at Bowdoin College in the summer of 1988, which brought together researchers in mathematics, computer science, and operations research. This volume contains the proceedings from the conference. Among the topics covered in this book are: completely integrable dynamical systems arising in optimization problems, Riemannian geometry and interior-point linear programming methods, concepts of approximate solution of linear programs, average case analysis of the simplex method, and recent results in convex polytopes. Some of the papers extend interior-point methods to quadratic programming, the linear complementarity problem, convex programming, multi-criteria optimization, and integer programming. Other papers study the continuous trajectories underlying interior point methods. This book will be an excellent resource for those interested in the latest developments arising from Karmarkar's linear programming algorithm and in path-following methods for solving differential equations.
There has been much recent work in linear and non-linear programming centred on understanding and extending the ideas underlying Karmarkar's interior-point linear programming algorithm. This volume is the result of an AMS conference on mathematical developments arising from linear programming.
This volume contains the proceedings of the AMS Summer Research Conference on Mathematical Developments Arising from Linear Programming held at Bowdoin College, June 25-July 1, 1988. This conference presented current research in linear and nonlinear programming and related areas of mathematics. There has been intense work in this area, much of it in extending and understanding the ideas underlying N. Karmarkar's interior-point linear programming algorithm, which was proposed in 1984. This research effort is interdisciplinary, and the conference brought together mathematicians, computer scientists, and operations researchers.
Acta Numerica is an annual volume presenting survey papers in numerical analysis. Each year the editorial board selects significant topics and invites papers from authors who have made notable contributions to the development of that topic. The articles are intended to summarize the field at a level accessible to graduate students and researchers. Acta Numerica is a valuable tool not only for researchers and professionals wishing to develop their understanding of the subject and follow developments, but also as an advanced teaching aid at colleges and universities. This volume was originally published in 1992.
This work is concerned with theoretical developments in the area of mathematical programming, development of new algorithms and software and their applications in science and industry. It aims to expose recent mathematical developments to a larger audience in science and industry.
In Linear Programming: A Modern Integrated Analysis, both boundary (simplex) and interior point methods 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 interior point 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.
Though the volume covers 22 papers by 36 authors from 12 countries, the history in the background is bound to Hungary where, in 1973 Andras PnĀ§kopa started to lay the foundation of a scientific forum, which can be a regular meeting spot for experts of the world in the field. Since then, there has been a constant interest in that forum. Headed at present by Tamas Rapcsak, the Laboratory of Operations Research and Decisions Systems of the Computer and Automation Institute, Hungarian Academy of Sciences followed the tradition in every respect, namely conferences were organized almost in every second year and in the same stimulating area, in the Matra mountains. The basic fields were kept, providing opportunities for the leading personalities to give voice to their latest results. The floor has been widened recently for the young generation, ensuring this way both a real location for the past, present and future experts to meet and also the possibility for them to make the multicoloured rainbow of the fields unbroken and continuous. The volume is devoted to the memory of Steven Vajda, one of the pioneers on mathematical programming, born is Hungary. In 1992 he took part in the XIth International Conference on Mathematical Programming at Matrafiired where, with his bright personality, he greatly contributed to the good spirituality of the event. We thank Jakob Krarup for his reminiscence on the life and scientific activities of late Steven Vajda.