Series On Optimization And Its Applications - Böcker

In full generality, minimizing a polynomial function over a closed semi-algebraic set requires complex mathematical equations. This book explains recent developments from singularity theory and semi-algebraic geometry for studying polynomial optimization problems. Classes of generic problems are defined in a simple and elegant manner by using only the two basic (and relatively simple) notions of Newton polyhedron and non-degeneracy conditions associated with a given polynomial optimization problem. These conditions are well known in singularity theory, however, they are rarely considered within the optimization community.Explanations focus on critical points and tangencies of polynomial optimization, Hölderian error bounds for polynomial systems, Frank-Wolfe-type theorem for polynomial programs and well-posedness in polynomial optimization. It then goes on to look at optimization for the different types of polynomials. Through this text graduate students, PhD students and researchers of mathematics will be provided with the knowledge necessary to use semi-algebraic geometry in optimization.

The Moment-SOS hierarchy is a powerful methodology that is used to solve the Generalized Moment Problem (GMP) where the list of applications in various areas of Science and Engineering is almost endless. Initially designed for solving polynomial optimization problems (the simplest example of the GMP), it applies to solving any instance of the GMP whose description only involves semi-algebraic functions and sets. It consists of solving a sequence (a hierarchy) of convex relaxations of the initial problem, and each convex relaxation is a semidefinite program whose size increases in the hierarchy.The goal of this book is to describe in a unified and detailed manner how this methodology applies to solving various problems in different areas ranging from Optimization, Probability, Statistics, Signal Processing, Computational Geometry, Control, Optimal Control and Analysis of a certain class of nonlinear PDEs. For each application, this unconventional methodology differs from traditional approaches and provides an unusual viewpoint. Each chapter is devoted to a particular application, where the methodology is thoroughly described and illustrated on some appropriate examples.The exposition is kept at an appropriate level of detail to aid the different levels of readers not necessarily familiar with these tools, to better know and understand this methodology.

Many applications, including computer vision, computer arithmetic, deep learning, entanglement in quantum information, graph theory and energy networks, can be successfully tackled within the framework of polynomial optimization, an emerging field with growing research efforts in the last two decades. One key advantage of these techniques is their ability to model a wide range of problems using optimization formulations. Polynomial optimization heavily relies on the moment-sums of squares (moment-SOS) approach proposed by Lasserre, which provides certificates for positive polynomials. On the practical side, however, there is "no free lunch" and such optimization methods usually encompass severe scalability issues. Fortunately, for many applications, including the ones formerly mentioned, we can look at the problem in the eyes and exploit the inherent data structure arising from the cost and constraints describing the problem.This book presents several research efforts to resolve this scientific challenge with important computational implications. It provides the development of alternative optimization schemes that scale well in terms of computational complexity, at least in some identified class of problems. It also features a unified modeling framework to handle a wide range of applications involving both commutative and noncommutative variables, and to solve concretely large-scale instances. Readers will find a practical section dedicated to the use of available open-source software libraries.This interdisciplinary monograph is essential reading for students, researchers and professionals interested in solving optimization problems with polynomial input data.

Markov Decision Processes (MDPs) form a cornerstone of applied probability, with over 50 years of rich research history. Throughout this time, numerous foundational books and thousands of journal articles have shaped the field. The central objective of MDP theory is to identify the optimal control strategy for Markov random processes with discrete time. Interestingly, the best control strategies often display unexpected or counterintuitive behaviors, as documented by a wide array of studies.This book gathers some of the most compelling examples of such phenomena while introducing new ones. By doing so, it serves as a valuable companion to existing textbooks. While many examples require little to no prior knowledge, others delve into advanced topics and will primarily interest specialists.In this second edition, extensive revisions have been made, correcting errors and refining the content, with a wealth of new examples added. The range of examples spans from elementary to advanced, requiring background knowledge in areas like measure theory, convex analysis, and advanced probability. A new chapter on continuous time jump processes has also been introduced. The entire text has been reworked for clarity and accessibility.This book is an essential resource for active researchers and graduate students in the field of Markov Decision Processes.

Many important applications in global optimization, algebra, probability and statistics, applied mathematics, control theory, financial mathematics, inverse problems, etc. can be modeled as a particular instance of the Generalized Moment Problem (GMP).This book introduces a new general methodology to solve the GMP when its data are polynomials and basic semi-algebraic sets. This methodology combines semidefinite programming with recent results from real algebraic geometry to provide a hierarchy of semidefinite relaxations converging to the desired optimal value. Applied on appropriate cones, standard duality in convex optimization nicely expresses the duality between moments and positive polynomials.In the second part, the methodology is particularized and described in detail for various applications, including global optimization, probability, optimal control, mathematical finance, multivariate integration, etc., and examples are provided for each particular application.

This invaluable book provides approximately eighty examples illustrating the theory of controlled discrete-time Markov processes. Except for applications of the theory to real-life problems like stock exchange, queues, gambling, optimal search etc, the main attention is paid to counter-intuitive, unexpected properties of optimization problems. Such examples illustrate the importance of conditions imposed in the theorems on Markov Decision Processes. Many of the examples are based upon examples published earlier in journal articles or textbooks while several other examples are new. The aim was to collect them together in one reference book which should be considered as a complement to existing monographs on Markov decision processes.The book is self-contained and unified in presentation.The main theoretical statements and constructions are provided, and particular examples can be read independently of others. Examples in Markov Decision Processes is an essential source of reference for mathematicians and all those who apply the optimal control theory to practical purposes. When studying or using mathematical methods, the researcher must understand what can happen if some of the conditions imposed in rigorous theorems are not satisfied. Many examples confirming the importance of such conditions were published in different journal articles which are often difficult to find. This book brings together examples based upon such sources, along with several new ones. In addition, it indicates the areas where Markov decision processes can be used. Active researchers can refer to this book on applicability of mathematical methods and theorems. It is also suitable reading for graduate and research students where they will better understand the theory.