Convex and stochastic optimization (Q1738333)

This book appears in Universitext, a series of textbooks that presents material from a wide variety of mathematical disciplines at master's level and beyond. As already the author points out in his preface: ``These lecture notes are an extension of those given in the master programs at the Universities Paris VI and Paris-Saclay, and in the École Polytechnique. They give an introduction to convex analysis and its applications to stochastic programming, i.e., to optimization problems where the decision must be taken in the presence of uncertainties.'' The contents of this book are the follows: Preface; 1. A convex optimization toolbox; 2. Semidefinite and semi-infinite pogramming; 3. An integration toolbox; 4. Risk measures; 5. Sampling and optimizing; 6. Dynamic stochastic optimization; 7. Markov decision processes; 8. Algorithms; 9. Generalized convexity and transportation theory; References; Index. Each chapter ends with notes which contain historical notes and some commentaries. Chapter 1 presents the duality theory for optimization problems, by both the minimax and perturbation approach, in a Banach space setting. Under some stability (qualification) hypotheses, it is shown that the dual problem has a nonempty and bounded set of solutions. This leads to the subdifferential calculus, which appears to be a subdifferential rule. Applications are provided to the infinimal convolution, as well as recession and perspective functions. The relaxation of some nonconvex problems is analyzed like an application of the Shapley-Folkman theorem. Chapter 2 discusses optimization problems in the cone of positive semidefinite matrices, and the duality theory for such `linear' problems. The author relates convex rotationally invariant matrix functions to convex functions of the spectrum; this allows to compute the conjugate of the logarithmic barrier function and the dual of associate optimization problems. The semidefinite relaxation of problems with nonconvex quadratic cost and constraints is presented. Second-order cone optimization is shown to be a subclass of semidefinite programming. The second part of the chapter is devoted to semi-infinite programming and its dual in the space of measures with finite support, with application to Chebyshev approximation and to one-dimensional polynomial optimization. In Chapter 3, the author gives a concise presentation of integration theory in a general measure space, including classical theorems on the limit of integrals. It also gives an extension to Bochner integrals, needed for measurable functions with values in a Banach space. Then it shows how to compute the conjugate and subdifferential of integral functionals, either in the convex case, based on convex integrand theory, or in the case of Carathéodory integrands. Then optimization problems with integral cost and constraint functions are analyzed using the Shapley-Folkman theorem. Chapter 4 gives a concise introduction to the corresponding theory of risk measures. After an introduction to utility functions, the monetary measures of risk are introduced and connected to their acceptation sets. Then the case of deviation and semi-deviation, as well as the (conditional) value at risk, are discussed. Chapter 5 discusses what happens when, instead of minimizing an expectation, one minimizes the sample approximation obtained by getting a sample of independent events. The analysis relies on the theory of asymptotic laws (delta theorems) and its applications in stochastic programming, and extends the results to the case of constraints in expectation. Chapter 6 develops the conditional expectation of non-integrable functions for convex problems with full observation of the state. The resulting optimality system involves a backward costate equation, the control variable being a point of minimum of some Hamiltonian function. Chapter 7 considers the problem of minimizing the expectation of a reward for a controlled Markov chain process, either with a finite horizon, or an infinite one for which the reward has discounted values, including the cases of exit times and stopping decisions. The value and policy (Howard) iterations are also compared. Extensions of these results are provided for problems with expectations constraints, partial observation, and for the ergodic case, limit in some sense of large horizon problems with undiscounted cost. Chapter 8 studies the case of convex, dynamic problems, whose convex Bellman values can be approximated by a collection of affine minorands. Staring with static and deterministic problems, it is shown how this leads to the effective stochastic dual dynamic programming algorithm. The second part of the chapter is devoted to the promising approach of linear decision rules, which allows one to obtain upper and lower bounds of the value functions of stochastic optimization problems. Chapter 9 presents the generalization of convexity theory when replacing duality products with general coupling functions on arbitrary sets. The notions of Fenchel conjugates, cyclical monotonicity and duality of optimization problems, have a natural extension to this setting, in which the augmented Lagrangian approach has a natural interpretation. Convex functions over measure spaces, constructed as Fenchel conjugates of integral functions of continuous functions, are shown to be sometimes equal to some integral of a function of their density. This is used in the presentation of optimal transportation theory over compact sets, and the associated penalized problems. The chapter ends with a discussion of the multi-transport setting. The book ends with references having 128 titles and a subject index. The book will be of interest to students, engineers and researchers who are interested to take rigorous approach to the mathematics involved in the applications of duality theory to optimization with uncertainty.