OPTIMIZATION
Edited by G.L. Nemhauser, A.H.G. Rinnooy Kan and M.J. Todd
PREFACE
Not surprisingly, the first volume in this series of handbooks is devoted to the topic of Optimization. No other class of techniques is so central to operations research and management science, both as a solution tool and as a modeling device. To translate a problem into a mathematical optimization model is characteristic of the discipline, located as it is at the crossroads of economics, mathematics and engineering.
Optimization deals with problems of minimizing or maximizing a function of several variables usually subject to equality and/or inequality constraints. This book collects together ten state-of-the-art expository articles on the most important topics in optimization, written by leading experts in the field. It therefore provides a primary reference for those performing research in some area of optimization or for those who have some basic knowledge of optimization techniques but wish to learn the most up-to-date and efficient algorithms for particular classes or problems. Each chapter starts at an introductory level suitable for master's level graduate students, but includes discussion of the references to the latest developments in the area.
Optimization has undergone very rapid development in recent years; articles in the book describe for instance the polynomial-time linear programming algorithms of Khachian and Karmarkar, the strongly-polynomial network flow algorithms of Tardos, Orlin, and others, and the techniques used to solve combinatorial and integer programming problems an order of magnitude larger than was possible just a few years ago.
The book includes chapters on unconstrained optimization, linear programming, constrained nonlinear programming, network flows, combinatorial optimization, integer programming, nondifferentiable optimization, stochastic programming, global optimization, and multicriterion optimization, thus providing broad coverage of finite-dimensional optimization theory and methods.
The first chapter, by Dennis and Schnabel, discusses the most basic optimization problems, those without constraints. A fundamental role is played by first-or second order Taylor approximations to the nonlinear functions involved, which can be viewed as model functions. This viewpoint leads to Newton's method for nonlinear equations or for nonlinear minimization. In order to avoid the calculation of matrices of derivatives at every iteration, methods using approximate derivative information are next considered, including quasi-Newton and finite-difference approximations; the latter can be very effective for large sparse problems. To obtain globally convergent algorithms, these methods must be modified to recognize the fact that only local information is used. Some control of the step size, either by a line search or by using trust regions, is necessary. The latter methods have become popular recently due to their excellent convergence properties. Dennis and Schnabel next discuss two methods that are not based on Taylor series; the Nelder-Mead simplex method can be very effective in low dimensions, and conjugate gradient approaches are attractive in high dimensions where matrices of derivatives cannot be stored. The final section discusses recent research on large-scale problems, data-fitting applications, secant updates, singular problems, and the exciting new area of parallel computation.
The second chapter, by Goldfarb and Todd, covers linear programming. After a discussion of typical linear programming formulations, a section on the structure of convex polyhedra leads into a geometrical treatment of Dantzig's simplex method and a description of efficient schemes to maintain and update representations of the basis inverse matrix. The key duality results and their use in sensitivity analysis are next presented. The ability to exploit special structure is essential in solving large-scale linear programming problems, and Goldfarb and Todd describe how to streamline the computations for problems with various upper bounding constraints and for network flow problems. Column generation techniques and the Dantzig-Wolfe decomposition principle are presented, and then the focus changes to discussion of the complexity of linear programming and recent results on the expected behavior of the simplex method. The final sections provide detailed descriptions of two polynomial algorithms - the ellipsoid method and Karmarkar's new projective algorithm for linear programming. While the former has attractive theoretical properties that have important consequences in combinatorial optimization (see Chapter 5), it seems to have no computational significance for linear programming. By contrast, the recent interior methods have considerable potential in practical computation.
Chapter 3, by Gill, Murray, Saunders and Wrigbt, discusses constrained nonlinear programming. The first part covers the easier case of equality constraints. Ile optimality conditions lead to a system of linear equations in the fundamental case of quadratic programming, and the authors describe several numerical methods to solve these for the optimal solution and the associated multiplier vector. Several classes of algorithms are presented for the general nonlinear case. Penalty methods reduce constrained to unconstrained problems, although either the penalty parameter must become infinite or a nonsmooth problem must be solved. Other methods involve solving a sequence of quadratic programming (one reason for the importance of such problems) or linearly constrained subproblems (e.g., the well-known MINOS code of Murtagh and Saunders). Finally, augmented Lagrangian methods are discussed. The second part considers inequality constraints, again first presenting the optimality conditions and the important special case of quadratic programming. The authors show how to extend sequential quadratic programming, sequential linearly-constrained and augmented Lagrangian methods to the case of inequality constraints. Finally, barrier-function methods are discussed in detail. While unpopular for many years, these have received enormous attention recently because of their close relationship with the new polynomial approaches to linear programming arising from the work of Karmarkar.
Chapter 4, by Ahuja, Magnanti and Orlin, treats network optimization, concentrating on network flow problems and, in particular, the design of efficient algorithms. Network flow problems have provided: (1) a fertile domain for operations research applications, (2) significant theoretical developments, which, among other things, yielded the historical bridge between linear programming and combinatorial optimization and (3) a rich collection of efficient algorithms that, in part, has arisen from a synergism. between optimization and computer science. The chapter begins with a section on applications and some key ideas from computer science that underlie the design of many algorithms. This is followed by a section that gives basic properties of network flow problems including the characterization of the structure of optimal solutions. The three fundamental problems of network flows, namely, the shortest path problem, the maximum flow problem and the minimum cost flow problem are presented in the subsequent sections. For each of these problems, the chapter gives an up-to-date account of recent algorithmic developments, especially, from the perspective of computational complexity.
Polyhedral combinatorics is the subject of Chapter 5 by Pulleyblank. The goal of polyhedral combinatorics is to represent the feasible region of a discrete optimization problem by a polyhedron and thus reduce the problem to a linear program. The chapter systematically develops the techniques of polyhedral combinatorics with emphasis placed on min-max or dual relationships between pairs of problems, e.g. the famous max-flow min-cut theorem of network flow theory. The first two sections illustrate min-max relations and their connection to decision problems with 'good characterizations'. This is followed by two sections giving algebraic and geometric results on the description of polyhedra, and the connection between linear systems and combinatorial optimization problems. Subsequent sections develop the techniques of separation and polarity and show how to obtain strengthened min-max relations by identifying essential inequalities and dual integrality. There are also sections on the dimension and adjacency relations of polyhedra, and the use of extended formulations and projection. The chapter closes with an appendix on computational complexity, which provides prerequisite material for several other chapters as well.
Chapter 6 on integer programming, by Nemhauser and Wolsey, continues the development of discrete optimization to encompass more general and computationally difficult problems for which polyhedral results are, at boot. incomplete. The chapter begins with model formulation with emphasis placed on representations that are 'good' with respect to the efficiency of solving them.. The following sections present some theoretical aspects of integer programs, including complexity, relaxation and duality. They lay the foundation for the algorithms that are presented in the remainder of the chapter in sections on cutting plane, branch-and-bound and approximation algorithms.
Nondifferentiable optimization is the subject of Chapter 7, by Lemaréchal. Several examples of nonsmooth problems are discussed; they arise, in minimax problems, for instance in data-fitting or exact penalty functions, and in various decomposition schemes, in particular in obtaining good bounds in integer programming via Lagrangian relaxation. The reasons that smooth methods fail are then discussed, to motivate how successful algorithms can be designed. First special methods for composite optimization problems are described, which are close to classical smooth (constrained) nonlinear approaches. Then the general problem is considered, and the two main classes of algorithms, subgradient and bundle methods, are discussed in detail. Subgradient methods include algorithms employing the acceleration techniques of Shor, and in particular the ellipsoid method of Judin and Nernirovski (developed well before Khachian's use of it in linear programming); they also include cutting plane methods, which leads to a discussion of notions of 'center', also fundamental in barrier-function methods and Karmarkar's algorithm and its extensions. Bundle methods, developed by Lemaréchal, Wolfe, Kiwiel and others, achieve a better approximation to a nonsmooth function by retaining a 'bundle' of useful previously-computed subgradients on which to base the current step. The final section describes recent work of Lemaréchal and his coworkers in attempting to build a 'second-order' model for nonsmooth optimization and raises a number of issues for future research.
Chapter 8, by Wets, is on the subject of stochastic programming, i.e. optimization models in which uncertainty about model parameters is represented by probabilistic tools. Mostly, one assumes that the true value of these parameters is only known (in the form of a realization of a random variable) after one or more initial decisions have been made. Hence, these decisions have to be based on a priori information about the random variables involved. In principle, the maximization or minimization of an expected objective function value is, of course. a deterministic problem, but its special structure warrants the development of a range of specialized techniques. Careful modelling of the prevailing uncertainty is always the first step towards a successful application. The chapter provides the mathematical basis for several of the better known solution methods, such as stochastic quasi-gradient methods, scenario aggregation (in which an attempt is made to focus on a subset Of computationally relevant future scenarios), decomposition (e.g., Benders decomposition for linear stochastic programming, leading to the L-shaped algorithm, and the Lagrangean relaxation for the nonlinear case) and Monte Carlo methods. A final section deals with the important issues of stability and incomplete information.
Global optimization is the subject of Chapter 9, by Rinnooy Kan and Timmer. Here, the focus is on the seemingly impossibly difficult problem, of finding the global optimum of an objective function which may have a large number of local optima. Additional assumptions on the objective function are obviously necessary to secure a deterministic guarantee of success, and several examples of such assumptions are given. E.g., if the objective function is Lipschitzian with known Lipschitz constant, then implicit enumeration techniques can be devised that solve the global problem in a finite amount of time. From a computational point of view, much better results have been obtained by dropping the requirement of a deterministic guarantee and substituting an asymptotic probabilistic guarantee, thus allowing the development of sampling based techniques whose accuracy can only be guaranteed in the long run. The chapter pays special attention to a scheme that combines sampling with clustering techniques, through which prominent local optima are identified. But it also addresses a wide range of other, sometimes quite esoteric techniques, ranging from heuristics such as the method that tunnels through hills in search of better and better valleys, to more sophisticated approaches based on stochastic differential equations.
The final chapter, by Yu, reports on how to proceed in the (realistic) case of more than one objective function being present. Starting from a survey of useful results on binary relations, the chapter introduces a variety, of approaches from multi-criterion decision making, including goal programming, maximum programming, interactive methods that elicit useful information from the decision maker, the construction of utility functions, the elimination of all but undominated feasible points, and special simplex methods to cover the linear programming subclass. A survey of this broad area cannot be exhaustive; however, the reader will find extensive references to the rest of the literature.
Overall, we hope that these articles provide a comprehensive yet lively and up-to-date discussion of the state-of-the-art in optimization. We believe that this book contains a coherent view of the important unifying ideas throughout the many facets of optimization and a guide to the most significant current areas of research.
G.L. Nemhauser
A.H.G. Rinnooy Kan
M.J. Todd
Complete chapters on ScienceDirect
[Description and order information]
Home | Elsevier Sites | Privacy Policy | Terms and Conditions | Feedback | Site Map | A Reed Elsevier Company