Search

This textbook presents a wide range of tools for a course in mathematical optimization for upper undergraduate and graduate students in mathematics, engineering, computer science, and other applied sciences. Basic optimization principles are presented with emphasis on gradient-based numerical optimization strategies and algorithms for solving both smooth and noisy discontinuous optimization problems. Attention is also paid to the difficulties of expense of function evaluations and the existence of multiple minima that often unnecessarily inhibit the use of gradient-based methods. This second edition addresses further advancements of gradient-only optimization strategies to handle discontinuities in objective functions. New chapters discuss the construction of surrogate models as well as new gradient-only solution strategies and numerical optimization using Python. A special Python module is electronically available (via springerlink) that makes the new algorithms featured in the text easily accessible and directly applicable. Numerical examples and exercises are included to encourage senior- to graduate-level students to plan, execute, and reflect on numerical investigations. By gaining a deep understanding of the conceptual material presented, students, scientists, and engineers will be able to develop systematic and scientific numerical investigative skills.

Just as in its 1st edition, this book starts with illustrations of the ubiquitous character of optimization, and describes numerical algorithms in a tutorial way. It covers fundamental algorithms as well as more specialized and advanced topics for unconstrained and constrained problems. Most of the algorithms are explained in a detailed manner, allowing straightforward implementation. Theoretical aspects of the approaches chosen are also addressed with care, often using minimal assumptions. This new edition contains computational exercises in the form of case studies which help understanding optimization methods beyond their theoretical, description, when coming to actual implementation. Besides, the nonsmooth optimization part has been substantially reorganized and expanded.

Since I started working in the area of nonlinear programming and, later on, variational inequality problems, I have frequently been surprised to find that many algorithms, however scattered in numerous journals, monographs and books, and described rather differently, are closely related to each other. This book is meant to help the reader understand and relate algorithms to each other in some intuitive fashion, and represents, in this respect, a consolidation of the field. The framework of algorithms presented in this book is called Cost Approxi­ mation. (The preface of the Ph.D. thesis [Pat93d] explains the background to the work that lead to the thesis, and ultimately to this book.) It describes, for a given formulation of a variational inequality or nonlinear programming problem, an algorithm by means of approximating mappings and problems, a principle for the update of the iteration points, and a merit function which guides and monitors the convergence of the algorithm. One purpose of this book is to offer this framework as an intuitively appeal­ ing tool for describing an algorithm. One of the advantages of the framework, or any reasonable framework for that matter, is that two algorithms may be easily related and compared through its use. This framework is particular in that it covers a vast number of methods, while still being fairly detailed; the level of abstraction is in fact the same as that of the original problem statement.

Nonlinear Optimization is an intriguing area of study where mathematical theory, algorithms and applications converge to calculate the optimal values of continuous functions. Within this subject, Global Optimization aims at finding global optima for difficult problems in which many local optima might exist. This book provides a compelling introduction to global and non-linear optimization providing interdisciplinary readers with a strong background to continue their studies into these and other related fields. The book offers insight in relevant concepts such as'region of attraction'and'Branch-and-Bound'by elaborating small numerical examples and exercises for the reader to follow.

In 1995 the Handbook of Global Optimization (first volume), edited by R. Horst, and P.M. Pardalos, was published. This second volume of the Handbook of Global Optimization is comprised of chapters dealing with modern approaches to global optimization, including different types of heuristics. Topics covered in the handbook include various metaheuristics, such as simulated annealing, genetic algorithms, neural networks, taboo search, shake-and-bake methods, and deformation methods. In addition, the book contains chapters on new exact stochastic and deterministic approaches to continuous and mixed-integer global optimization, such as stochastic adaptive search, two-phase methods, branch-and-bound methods with new relaxation and branching strategies, algorithms based on local optimization, and dynamical search. Finally, the book contains chapters on experimental analysis of algorithms and software, test problems, and applications.

Although this may seem a paradox, all exact science is dominated by the idea of approximation. Bertrand Russell (1872-1970) Most natural optimization problems, including those arising in important application areas, are NP-hard. Therefore, under the widely believed con­ jecture that P -=/= NP, their exact solution is prohibitively time consuming. Charting the landscape of approximability of these problems, via polynomial time algorithms, therefore becomes a compelling subject of scientific inquiry in computer science and mathematics. This book presents the theory of ap­ proximation algorithms as it stands today. It is reasonable to expect the picture to change with time. This book is divided into three parts. In Part I we cover combinato­ rial algorithms for a number of important problems, using a wide variety of algorithm design techniques. The latter may give Part I a non-cohesive appearance. However, this is to be expected - nature is very rich, and we cannot expect a few tricks to help solve the diverse collection of NP-hard problems. Indeed, in this part, we have purposely refrained from tightly cat­ egorizing algorithmic techniques so as not to trivialize matters. Instead, we have attempted to capture, as accurately as possible, the individual character of each problem, and point out connections between problems and algorithms for solving them.