Stephen J. Wright

Presents the major primal-dual algorithms for linear programming. A thorough, straightforward description of the theoretical properties of these methods.

Primal-Dual Interior-Point Methods

Michael C. Ferris

Olvi L. Mangasarian

This textbook provides a self-contained introduction to linear programming using MATLAB software to elucidate the development of algorithms and theory. Early chapters cover linear algebra basics, the simplex method, duality, the solving of large linear problems, sensitivity analysis, and parametric linear programming. In later chapters, the authors discuss quadratic programming, linear complementarity, interior-point methods, and selected applications of linear programming to approximation and classification problems. Exercises are interwoven with the theory presented in each chapter, and two appendices provide additional information on linear algebra, convexity, nonlinear functions, and on available MATLAB commands, respectively. Readers can access MATLAB codes and associated mex files at a Web site maintained by the authors. Only a basic knowledge of linear algebra and calculus is required to understand this textbook, which is geared toward junior and senior-level undergraduate students, first-year graduate students, and researchers unfamiliar with linear programming.

Linear Programming with MATLAB

An Untapped National Resource

The Black Educational Policy Researcher

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.

Primal-dual Interior-Point Methods

Suvrit Sra

Sebastian Nowozin

An up-to-date account of the interplay between optimization and machine learning, accessible to students and researchers in both communities. The interplay between optimization and machine learning is one of the most important developments in modern computational science. Optimization formulations and methods are proving to be vital in designing algorithms to extract essential knowledge from huge volumes of data. Machine learning, however, is not simply a consumer of optimization technology but a rapidly evolving field that is itself generating new optimization ideas. This book captures the state of the art of the interaction between optimization and machine learning in a way that is accessible to researchers in both fields. Optimization approaches have enjoyed prominence in machine learning because of their wide applicability and attractive theoretical properties. The increasing complexity, size, and variety of today's machine learning models call for the reassessment of existing assumptions. This book starts the process of reassessment. It describes the resurgence in novel contexts of established frameworks such as first-order methods, stochastic approximations, convex relaxations, interior-point methods, and proximal methods. It also devotes attention to newer themes such as regularized optimization, robust optimization, gradient and subgradient methods, splitting techniques, and second-order methods. Many of these techniques draw inspiration from other fields, including operations research, theoretical computer science, and subfields of optimization. The book will enrich the ongoing cross-fertilization between the machine learning community and these other fields, and within the broader optimization community.

Optimization for Machine Learning

Benjamin Recht

"Optimization formulations and algorithms have long played a central role in data analysis and machine learning. Maximum likelihood concepts date to Gauss and Laplace in the late 1700s; problems of this type drove developments in unconstrained optimization in the latter half of the 20th century. Mangasarian's papers in the 1960s on pattern separation using linear programming made an explicit connection between machine learning and optimization in the early days of the former subject. During the 1990s, optimization techniques (especially quadratic programming and duality) were key to the development of support vector machines and kernel learning. The period 1997-2010 saw many synergies emerge between regularized / sparse optimization, variable selection, and compressed sensing. In the current era of deep learning, two optimization techniques-stochastic gradient and automatic differentiation (a.k.a. back-propagation)-are essential"--

Stephen J. Wright

About

Books

Join the club