The era of interior point methods (IPMs) was initiated by N. Karmarkar’s 1984 paper, which triggered turbulent research and reshaped almost all areas of optimization theory and computational practice. This book offers comprehensive coverage of IPMs. It details the main results of more than a decade of IPM research. Numerous exercises are provided to aid in understanding the material.

This book discusses an important area of numerical optimization, called interior-point method. This topic has been popular since the 1980s when people gradually realized that all simplex algorithms were not convergent in polynomial time and many interior-point algorithms could be proved to converge in polynomial time. However, for a long time, there was a noticeable gap between theoretical polynomial bounds of the interior-point algorithms and efficiency of these algorithms. Strategies that were important to the computational efficiency became barriers in the proof of good polynomial bounds. The more the strategies were used in algorithms, the worse the polynomial bounds became. To further exacerbate the problem, Mehrotra's predictor-corrector (MPC) algorithm (the most popular and efficient interior-point algorithm until recently) uses all good strategies and fails to prove the convergence. Therefore, MPC does not have polynomiality, a critical issue with the simplex method. This book discusses recent developments that resolves the dilemma. It has three major parts. The first, including Chapters 1, 2, 3, and 4, presents some of the most important algorithms during the development of the interior-point method around the 1990s, most of them are widely known. The main purpose of this part is to explain the dilemma described above by analyzing these algorithms' polynomial bounds and summarizing the computational experience associated with them. The second part, including Chapters 5, 6, 7, and 8, describes how to solve the dilemma step-by-step using arc-search techniques. At the end of this part, a very efficient algorithm with the lowest polynomial bound is presented. The last part, including Chapters 9, 10, 11, and 12, extends arc-search techniques to some more general problems, such as convex quadratic programming, linear complementarity problem, and semi-definite programming.

Operations research and mathematical programming would not be as advanced today without the many advances in interior point methods 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 interior point methods have influenced virtually all areas of mathematical programming including: analyzing and solving linear and nonlinear programming 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. Audience: The book is intended for students, researchers and practitioners with a background in operations research, mathematics, mathematical programming, or statistics.

The first volume of this popular handbook mirrors the modern taxonomy of computer science and software engineering as described by the Association for Computing Machinery (ACM) and the IEEE Computer Society (IEEE-CS). Written by established leading experts and influential young researchers, it examines the elements involved in designing and implementing software, new areas in which computers are being used, and ways to solve computing problems. The book also explores our current understanding of software engineering and its effect on the practice of software development and the education of software professionals.

Provides an introduction to the applications, theory, and algorithms of linear and nonlinear optimization. The emphasis is on practical aspects - discussing modern algorithms, as well as the influence of theory on the interpretation of solutions or on the design of software. The book includes several examples of realistic optimization models that address important applications. The succinct style of this second edition is punctuated with numerous real-life examples and exercises, and the authors include accessible explanations of topics that are not often mentioned in textbooks, such as duality in nonlinear optimization, primal-dual methods for nonlinear optimization, filter methods, and applications such as support-vector machines. The book is designed to be flexible. It has a modular structure, and uses consistent notation and terminology throughout. It can be used in many different ways, in many different courses, and at many different levels of sophistication.

The goal of the Encyclopedia of Optimization is to introduce the reader to a complete set of topics that show the spectrum of research, the richness of ideas, and the breadth of applications that has come from this field. The second edition builds on the success of the former edition with more than 150 completely new entries, designed to ensure that the reference addresses recent areas where optimization theories and techniques have advanced. Particularly heavy attention resulted in health science and transportation, with entries such as "Algorithms for Genomics", "Optimization and Radiotherapy Treatment Design", and "Crew Scheduling".

The book presents a graduate level, rigorous, and self-contained introduction to linear optimization (LO), the presented topics being

In the past decade, primal-dual algorithms have emerged as the most important and useful algorithms from the interior-point class. This book presents the major primal-dual algorithms for linear programming in straightforward terms. A thorough description of the theoretical properties of these methods is given, as are a discussion of practical and computational aspects and a summary of current software. This is an excellent, timely, and well-written work. The major primal-dual algorithms covered in this book are path-following algorithms (short- and long-step, predictor-corrector), potential-reduction algorithms, and infeasible-interior-point algorithms. A unified treatment of superlinear convergence, finite termination, and detection of infeasible problems is presented. Issues relevant to practical implementation are also discussed, including sparse linear algebra and a complete specification of Mehrotra's predictor-corrector algorithm. Also treated are extensions of primal-dual algorithms to more general problems such as monotone complementarity, semidefinite programming, and general convex programming problems.

Operations Research and Cyber-Infrastructure is the companion volume to the Eleventh INFORMS Computing Society Conference (ICS 2009), held in Charleston, South Carolina, from January 11 to 13, 2009. It includes 24 high-quality refereed research papers. As always, the focus of interest for ICS is the interface between Operations Research and Computer Science, and the papers in this volume reflect that interest. This is naturally an evolving area as computational power increases rapidly while decreasing in cost even more quickly, and the papers included here illustrate the wide range of topics at this interface.

Do you want easy access to the latest methods in scientific computing? This greatly expanded third edition of Numerical Recipes has it, with wider coverage than ever before, many new, expanded and updated sections, and two completely new chapters. The executable C++ code, now printed in colour for easy reading, adopts an object-oriented style particularly suited to scientific applications. Co-authored by four leading scientists from academia and industry, Numerical Recipes starts with basic mathematics and computer science and proceeds to complete, working routines. The whole book is presented in the informal, easy-to-read style that made earlier editions so popular. Highlights of the new material include: a new chapter on classification and inference, Gaussian mixture models, HMMs, hierarchical clustering, and SVMs; a new chapter on computational geometry, covering KD trees, quad- and octrees, Delaunay triangulation, and algorithms for lines, polygons, triangles, and spheres; interior point methods for linear programming; MCMC; an expanded treatment of ODEs with completely new routines; and many new statistical distributions. For support, or to subscribe to an online version, please visit www.nr.com.