MOS-SIAM Series on Optimization – serie

This is the first comprehensive reference on trust-region methods, a class of numerical algorithms for the solution of nonlinear convex optimization methods. Its unified treatment covers both unconstrained and constrained problems and reviews a large part of the specialized literature on the subject. It also provides an up-to-date view of numerical optimization.Written primarily for postgraduates and researchers, the book features an extensive commented bibliography, which contains more than 1000 references by over 750 authors. The book also contains several practical comments and an entire chapter devoted to software and implementation issues. Its many illustrations, including nearly 100 figures, balance the formal and intuitive treatment of the presented topics.

Here is a book devoted to well-structured and thus efficiently solvable convex optimization problems, with emphasis on conic quadratic and semidefinite programming. The authors present the basic theory underlying these problems as well as their numerous applications in engineering, including synthesis of filters, Lyapunov stability analysis, and structural design. The authors also discuss the complexity issues and provide an overview of the basic theory of state-of-the-art polynomial time interior point methods for linear, conic quadratic, and semidefinite programming. The book's focus on well-structured convex problems in conic form allows for unified theoretical and algorithmical treatment of a wide spectrum of important optimization problems arising in applications.Lectures on Modern Convex Optimization presents and analyzes numerous engineering models, illustrating the wide spectrum of potential applications of the new theoretical and algorithmical techniques emerging from the significant progress taking place in convex optimization. It is hoped that the information provided here will serve to promote the use of these techniques in engineering practice. The book develops a kind of ""algorithmic calculus"" of convex problems, which can be posed as conic quadratic and semidefinite programs. This calculus can be viewed as a ""computationally tractable"" version of the standard convex analysis.

This compact book, through the simplifying perspective it presents, will take a reader who knows little of interior-point methods to within sight of the research frontier, developing key ideas that were over a decade in the making by numerous interior-point method researchers. It aims at developing a thorough understanding of the most general theory for interior-point methods, a class of algorithms for convex optimization problems. The study of these algorithms has dominated the continuous optimization literature for nearly 15 years. In that time, the theory has matured tremendously, but much of the literature is difficult to understand, even for specialists. By focusing only on essential elements of the theory and emphasizing the underlying geometry, A Mathematical View of Interior-Point Methods in Convex Optimization makes the theory accessible to a wide audience, allowing them to quickly develop a fundamental understanding of the material.The author begins with a general presentation of material pertinent to continuous optimization theory, phrased so as to be readily applicable in developing interior-point method theory. This presentation is written in such a way that even motivated Ph.D. students who have never had a course on continuous optimization can gain sufficient intuition to fully understand the deeper theory that follows. Renegar continues by developing the basic interior-point method theory, with emphasis on motivation and intuition. In the final chapter, he focuses on the relations between interior-point methods and duality theory, including a self-contained introduction to classical duality theory for conic programming; an exploration of symmetric cones; and the development of the general theory of primal-dual algorithms for solving conic programming optimization problems.Rather than attempting to be encyclopedic, A Mathematical View of Interior-Point Methods in Convex Optimization gives the reader a solid understanding of the core concepts and relations, the kind of understanding that stays with a reader long after the book is finished.

The Sharpest Cut is written in honor of Manfred Padberg, who has made fundamental contributions to both the theoretical and computational sides of integer programming and combinatorial optimization. This outstanding collection presents recent results in these areas that are closely connected to Padberg's research. His deep commitment to the geometrical approach to combinatorial optimization can be felt throughout this volume; his search for increasingly better and computationally efficient cutting planes gave rise to its title.The peer-reviewed papers contained here are based on invited lectures given at a workshop held in October 2001 to celebrate Padberg's 60th birthday. Grouped by topic (packing, stable sets, and perfect graphs; polyhedral combinatorics; general polytopes; semidefinite programming; computation), many of the papers set out to solve challenges set forth in Padberg’s work. The book also shows how Padberg's ideas on cutting planes have influenced modern commercial optimization software. In addition, the volume contains a short curriculum vitae, a personal account of Padberg’s work by Laurence Wolsey, and an appendix with reflections from Egon Balas, Claude Berge, and Harold Kuhn.Manfred Padberg was Research Professor, Stern School of Business, New York University until 2002. Over the course of his career he received many honors for his work, including the Lanchester Prize, Dantzig Prize, and the John von Neuman Theory Prize. He has published six books and over 100 articles.

Research on algorithms and applications of stochastic programming, the study of procedures for decision making under uncertainty over time, has been very active in recent years and deserves to be more widely known. This is the first book devoted to the full scale of applications of stochastic programming and also the first to provide access to publicly available algorithmic systems. The 32 contributed papers in this volume are written by leading stochastic programming specialists and reflect the high level of activity in recent years in research on algorithms and applications. The book introduces the power of stochastic programming to a wider audience and demonstrates the application areas where this approach is superior to other modeling approaches.Applications of Stochastic Programming consists of two parts. The first part presents papers describing publicly available stochastic programming systems that are currently operational. All the codes have been extensively tested and developed and will appeal to researchers and developers who want to make models without extensive programming and other implementation costs. The codes are a synopsis of the best systems available, with the requirement that they be user-friendly, ready to go, and publicly available.The second part of the book is a diverse collection of application papers in areas such as production, supply chain and scheduling, gaming, environmental and pollution control, financial modeling, telecommunications, and electricity. It contains the most complete collection of real applications using stochastic programming available in the literature. The papers show how leading researchers choose to treat randomness when making planning models, with an emphasis on modeling, data, and solution approaches.

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, and 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.

Provides a self-contained, accessible introduction to the mathematical advances and challenges resulting from the use of semidefinite programming in polynomial optimization. This quickly evolving research area with contributions from the diverse fields of convex geometry, algebraic geometry, and optimization is known as convex algebraic geometry.Each chapter addresses a fundamental aspect of convex algebraic geometry. The book begins with an introduction to nonnegative polynomials and sums of squares and their connections to semidefinite programming and quickly advances to several areas at the forefront of current research. These include:Semidefinite representability of convex sets.Duality theory from the point of view of algebraic geometry.Nontraditional topics such as sums of squares of complex forms and noncommutative sums of squares polynomials.

Presents recent advances in the mathematical theory of discrete optimization, particularly those supported by methods from algebraic geometry, commutative algebra, convex and discrete geometry, generating functions, and other tools normally considered outside the standard curriculum in optimization.Algebraic and Geometric Ideas in the Theory of Discrete Optimization:Offers several research technologies not yet well known among practitioners of discrete optimizationnMinimizes prerequisites for learning these methods. Provides a transition from linear discrete optimization to nonlinear discrete optimization.Offers several research technologies not yet well known among practitioners of discrete optimization, minimizes prerequisites for learning these methods, and provides a transition from linear discrete optimization to nonlinear discrete optimization.

Contains a thorough overview of the rapidly growing field of global optimization, with chapters on key topics such as complexity, heuristic methods, derivation of lower bounds for minimization problems, and branch-and-bound methods and convergence. The final chapter offers both benchmark test problems and applications of global optimization, such as finding the conformation of a molecule or planning an optimal trajectory for interplanetary space travel. An appendix provides fundamental information on convex and concave functions.

Variational analysis is the subject of this self-contained guide, which provides a detailed presentation of the most important tools in the field, as well as applications to geometry, mechanics, elasticity, and computer vision. This second edition introduces significant new material on several topics, including: quasi-open sets and quasi-continuity in the context of capacity theory and potential theory; mass transportation problems and the Kantorovich relaxed formulation of the Monge problem; and stochastic homogenization, with mathematical tools coming from ergodic theory. It also features an entirely new and comprehensive chapter devoted to gradient flows and the dynamical approach to equilibria, and extra examples in the areas of linearized elasticity systems, obstacles problems, convection-diffusion, semilinear equations, and the shape optimization procedure. The book is intended for PhD students, researchers, and practitioners who want to approach the field of variational analysis in a systematic way.

Vehicle routing problems, among the most studied in combinatorial optimization, arise in many practical contexts (freight distribution and collection, transportation, garbage collection, newspaper delivery, etc.). Operations researchers have made significant developments in the algorithms for their solution, and Vehicle Routing: Problems, Methods, and Applications, Second Edition reflects these advances. The text of the new edition is either completely new or significantly revised and provides extensive and complete state-of-the-art coverage of vehicle routing by those who have done most of the innovative research in the area; it emphasizes methodology related to specific classes of vehicle routing problems and, since vehicle routing is used as a benchmark for all new solution techniques, contains a complete overview of current solutions to combinatorial optimization problems. It also includes several chapters on important and emerging applications, such as disaster relief and green vehicle routing.Audience: This book is intended for both researchers and graduate level students in operations research and applied mathematics. Practitioners will find this book particularly useful. Readers need a basic knowledge of the main methods for the solution of combinatorial optimization problems.

This book provides a thorough and up-to-date discussion of arc routing by world-renowned researchers. Organized by problem type, the book offers a rigorous treatment of complexity issues, models, algorithms, and applications.Arc Routing opens with a historical perspective of the field and is followed by three sections that cover:Complexity and the Chinese Postman and the Rural Postman problems.The Capacitated Arc Routing Problem and routing problems with min-max and profit maximization objectives.Important applications, including meter reading, snow removal, and waste collection.

This book addresses a seemingly simple question: can a certain amount of gas be transported within a pipeline network? The question is difficult, however, when asked in relation to a meshed nationwide gas transportation network and when taking into account technical details and discrete decisions, as well as regulations, contracts, and varying demands involved.Evaluating Gas Network Capacities provides an introduction to the field of gas transportation planning and discusses in detail the advantages and disadvantages of several mathematical models that address gas transport within the context of the technical and regulatory framework. It shows how to solve the models using sophisticated mathematical optimization algorithms and includes examples of large-scale applications of mathematical optimization to this real-world industrial problem.Readers will also find a glossary of gas transport terms, tables listing the physical and technical quantities and constants used throughout the book, and a reference list of regulation and gas business literature.

Optimization is of critical importance in engineering. Engineers constantly strive for the best possible solutions, the most economical use of limited resources, and the greatest efficiency. As system complexity increases, these goals mandate the use of state-of-the-art optimization techniques.In recent years the theory and methodology of optimization have seen revolutionary improvements. Moreover, the exponential growth in computational power, along with the availability of multicore computing with virtually unlimited memory and storage capacity, has fundamentally changed what engineers can do to optimize their designs. This is a two-way process: engineers benefit from developments in optimization methodology, and challenging new classes of optimization problems arise from novel engineering applications.Advances and Trends in Optimization with Engineering Applications reviews 10 major areas of optimization and related engineering applications in a distinct part, providing a broad summary of state-of-the-art optimization techniques most important to engineering practice. Each part provides a clear overview of a specific area, followed by chapters detailing applications to a wide range of real-world problems.The book provides a solid foundation for engineers and mathematical optimizers alike who want to understand not only the importance of optimization methods to engineering but also the capabilities of current methods.

The primary goal of this book is to provide a self-contained, comprehensive study of the main ?rst-order methods that are frequently used in solving large-scale problems. First-order methods exploit information on values and gradients/subgradients (but not Hessians) of the functions composing the model under consideration. With the increase in the number of applications that can be modeled as large or even huge-scale optimization problems, there has been a revived interest in using simple methods that require low iteration cost as well as low memory storage.The author has gathered, reorganized, and synthesized (in a unified manner) many results that are currently scattered throughout the literature, many of which cannot be typically found in optimization books.First-Order Methods in Optimization offers comprehensive study of first-order methods with the theoretical foundations; provides plentiful examples and illustrations; emphasizes rates of convergence and complexity analysis of the main first-order methods used to solve large-scale problems; and covers both variables and functional decomposition methods.

This book is about making decisions driven by experience. In this context, a scenario is an observation that comes from the environment, and scenario optimization refers to optimizing decisions over a set of available scenarios. Scenario optimization can be applied across a variety of fields, including machine learning, quantitative finance, control, and identification.The scenario approach has been given a solid mathematical foundation in recent years, addressing fundamental questions such as: How should experience be incorporated in the decision process to optimize the result? How well will the decision perform in a new case that has not been seen before in the scenario sample? And how robust will results be when using this approach?This concise, practical book provides readers with an easy access point to make the scenario approach understandable to nonexperts, and offers an overview of various decision frameworks in which the method can be used. It contains numerous examples and diverse applications from a broad range of domains, including systems theory, control, biomedical engineering, economics, and finance. Practitioners can find ""easy-to-use recipes,"" while theoreticians will benefit from a rigorous treatment of the theoretical foundations of the method, making it an excellent starting point for scientists interested in doing research in this field. Introduction to the Scenario Approach will appeal to scientists working in optimization, practitioners working in myriad fields involving decision-making, and anyone interested in data-driven decision-making.

Lectures on Stochastic Programming: Modeling and Theory, Third Edition covers optimization problems involving uncertain parameters for which stochastic models are available. These problems occur in almost all areas of science and engineering.This substantial revision of the previous edition presents a modern theory of stochastic programming, including expanded coverage of sample complexity, risk measures, and distributionally robust optimization:Chapter 6 is updated and the interchangeability principle for risk measures is discussed in detail.Two new chapters, 'Distributionally Robust Stochastic Programming' (DRSP) and 'Computational Methods' provide readers with a solid understanding of emerging topics.Chapter 8 presents new material on formulation and numerical approaches to solving periodical multistage stochastic programs.This book is written for researchers and graduate students working on theory and applications of optimization.

Starting with the fundamentals of classical smooth optimization and building on established convex programming techniques, this research monograph presents a foundation and methodology for modern nonconvex nondifferentiable optimization. It provides readers with theory, methods, and applications of nonconvex and nondifferentiable optimization in statistical estimation, operations research, machine learning, and decision making. A comprehensive and rigorous treatment of this emergent mathematical topic is urgently needed in today's complex world of big data and machine learning. This book takes a thorough approach to the subject and includes examples and exercises to enrich the main themes, making it suitable for classroom instruction. Modern Nonconvex Nondifferentiable Optimization is intended for applied and computational mathematicians, optimizers, operations researchers, statisticians, computer scientists, engineers, economists, and machine learners. It could be used in advanced courses on optimization/operations research and nonconvex and nonsmooth optimization.

One of the most popular ways to assess the "effort" needed to solve a problem is to count how many evaluations of the problem functions (and their derivatives) are required. In many cases, this is often the dominating computational cost. Given an optimization problem satisfying reasonable assumptions—and given access to problem-function values and derivatives of various degrees—how many evaluations might be required to approximately solve the problem? Evaluation Complexity of Algorithms for Nonconvex Optimization: Theory, Computation, and Perspectives addresses this question for nonconvex optimization problems, those that may have local minimizers and appear most often in practice. This is the first bookon complexity to cover topics such as composite and constrained optimization, derivative-free optimization, subproblem solution, and optimal (lower and sharpness) bounds for nonconvex problems,to address the disadvantages of traditional optimality measures and propose useful surrogates leading to algorithms that compute approximate high-order critical points, and to compare traditional and new methods, highlighting the advantages of the latter from a complexity point of view.This is the go-to book for those interested in solving nonconvex problems. It is suitable for advanced undergraduate and graduate students in courses on Advanced Numerical Analysis, Special Topics on Numerical Analysis, Topics on Data Science, Topics on Numerical Optimization, and Topics on Approximation Theory.

Moment and polynomial optimization is an active research field used to solve difficult questions in many areas, including global optimization, tensor computation, saddle points, Nash equilibrium, and bilevel programs, and it has many applications. The author synthesizes current research and applications, providing a systematic introduction to theory and methods, a comprehensive approach for extracting optimizers and solving truncated moment problems, and a creative methodology for using optimality conditions to construct tight Moment-SOS relaxations.This book is intended for applied mathematicians, engineers, and researchers entering the field. It can be used as a textbook for graduate students in courses on convex optimization, polynomial optimization, and matrix and tensor optimization.

The only book offering solved exercises for integer and combinatorial optimization, this book contains 102 classroom tested problems of varying scope and difficulty chosen from a plethora of topics and applications. It has an associated website containing additional problems, miscellaneous material including suggested readings, and errata.Topics covered include modeling capabilities of integer variables, the Branch-and-Bound method, cutting planes, network optimization models, shortest path problems, optimum tree problems, maximal cardinality matching problems, matching-covering duality, symmetric and asymmetric TSP, 2-matching and 1-tree relaxations, VRP formulations, and dynamic programming.Problems and Solutions for Integer and Combinatorial Optimization: Building Skills in Discrete Optimization is meant for undergraduate and beginning graduate students in mathematics, computer science, and engineering to use for self-study and for instructors to use in conjunction with other course material and when teaching courses in discrete optimization.

This concise, self-contained volume introduces convex analysis and optimization algorithms, with an emphasis on bridging the two areas. It explores cutting-edge algorithms--such as the proximal gradient, Douglas-Rachford, Peaceman-Rachford, and FISTA--that have applications in machine learning, signal processing, image reconstruction, and other fields.An Introduction to Convexity, Optimization, and Algorithms contains algorithms illustrated by Julia examples and more than 200 exercises that enhance the reader's understanding of the topic. Clear explanations and step-by-step algorithmic descriptions facilitate self-study for individuals looking to enhance their expertise in convex analysis and optimization.

This book addresses an important class of problems in the field of mathematical optimization­ – those involving nonconvex and/or nonsmooth continuous functions. The authors introduce the theoretical foundations of nonconvex nonsmooth functions and discuss optimality conditions for optimization problems involving such functions. They also provide a wide-ranging review of the foundations underlying the most effective and efficient algorithms for solving nonconvex nonsmooth optimization problems. This challenging class of problems has applications in areas such as control systems, signal processing, and data science. In Practical Nonconvex Nonsmooth Optimization the authorsdefine problems over finite-dimensional real-vector spaces, so readers do not need an extensive background in functional analysis,use nonconvex smooth optimization as a starting point rather than convex optimization, making it easier for those who do not have an extensive background in convex analysis and optimization, and employ a conversational style and put long technical proofs at the end of each chapter so that the main ideas are understood before looking into the details of long, technical proofs.

This book is a self-contained introduction to quantum algorithms with an emphasis on quantum optimization, that is, quantum algorithms to solve optimization problems. The book provides all the tools necessary to understand the benefits and drawbacks of quantum optimization algorithms, paying particular attention to provable guarantees and computational complexity. The first comprehensive treatment of quantum optimization, Conditional Gradient Methods: From Core Principles to AI Applications provides a rigorous introduction to the computational model of quantum computers,contains detailed discussion of some of the most important developments in quantum optimization algorithms, and summarizes the most important developments in the open literature.