×

Modern nonconvex nondifferentiable optimization. (English) Zbl 1489.90001

MOS/SIAM Series on Optimization 29. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM) (ISBN 978-1-61197-673-1/hbk; 978-1-61197-674-8/ebook). xx, 756 p. (2021).
In the expressive preface of the book it is shown that applications of optimization for problems from the modern real world (examples are given, see, e.g. Chap. 3) require computational algorithms and convergence analysis, which are not dominated by the often dominant thought of classical optimization (smoothness, convexity, global solutions) but in which nondifferentiability, nonconvexity and uncertainty take a determining place. For this, the book, having almost lexicographic character, gives an up-to-date mathematical basis and (revised and new) solution methods. A richly equipped bibliography is appended. The book is divided into 11 chapters. All chapters are designed to be easy to read, as definitions, theorems, corollaries, remarks are highlighted in gray, algorithms in green; there are well-explanatory text sections, exercises and a lot of references to literature, sometimes references to ongoing research with respect to practically efficient algorithms (see, e.g., p. 148 below) or remarks that there are no solution procedures for certain problems yet. Chapter 1 summarizes (in \(\mathbb{R}^N\)) basic knowledge necessary for the book concerning smooth calculus, esp. directional differentiability, linear equations, matrix-splitting methods, conjugate gradient method and elements of set-valued analysis. Chapter 2 recalls elements of optimization theory and methods (convexity, KKT conditions, CQs, minimax, basic descent for smooth problems), contains (in Subsection 2.5) three algorithms and concludes with a four-page survey of nonlinear programming methods. Chapter 3 (with an explanatory introduction) deals with optimization problems derived from modern statistics-based learning models formulated as expected-value minimization problems (with variable selections). Such problems form a substantial part of (the above mentioned ) problems of the real world and are often nonconvex and nondifferentiable. Loss functions, deep learning, sparsity constraints, parametric and nonparametric learning are key words in this chapter. Chapter 4 presents nonsmooth analysis starting with Bouligand-differentiability for (as used in this book) locally Lipschitz continuous and directionally differentiable functions. The authors write, they intend to present the theory to be consistent with computations. Different kinds of subdifferentials, analytic properties of weakly convex functions and some pages on the difference of convex functions follow. The chapter ends with a diagram containing the introduced classes of nonsmooth functions and their relationships and with the remark that for optimization of dc functions one needs combined methods of penalization, surrogation and convex programming (as in Chapters 7 and 9). Chapter 5 deals with value functions of optimization problems and the authors write in their explanatory introduction that value functions are pervasive in optimization. Keywords used in this chapter are e.g. robustness and robustification, uncertainty, gap functions in connection with variational inequalities and CQ constraints (with a hint to chapter 11) and stochastic value functions. In Subsection 5.5, the authors give a modern presentation of results in connection with Danskin’s fundamental minmax theorem. Chapter 6 is titled by stationarity theory and starts with an interesting discussion on local minimizers and the definition of stationarity, containing the balance between theory and computation. So the authors characterize stationarity using B-differentiable functions (all one-sided directional derivatives exist) and Bouligand tangent cones (closed but not necessarily convex) and a fixed-point property. Then, for locally Lipschitz continuous functions, first-order and second-order theory, subdifferential-based stationarity theory and directional saddle-point theory can be constructed, a few examples are inserted. Chapter 7 deals (for deterministic problems) with computational algorithms by surrogation. Starting with a formal definition of surrogate functions, 13 algorithms are constructed for different cases of surrogations, e.g. Dinkelbach’s algorithm with surrogation and also for a generalized fractional programming problem (with vector-valued functions). Examples with randomized surrogation and inexact surrogation follow. The subsection ends with a hint to probabilistic convergence theory (Chapter 10). Chapter 8 is devoted to the theory of error bounds and shows the interaction between terminating algorithms, accumulation points, sequential convergence, residual function, types of stationarity, linear regularity and (local) error bounds and it is interesting that Ekeland’s variational principle (Lemma 8.3.1) together with Takahashi’s condition is helpful. Chapter 9 deals with exact penalization. Different kinds of penalization are discussed and two algorithms (enhanced double-loop surrogation, semismooth Newton method) are inserted. In Chapter 10 – nonconvex stochastic programs – the authors have the goal of extending the deterministic surrogation algorithms to an uncertain setting and add that the idea if sample average approximations will be the major computational tool. Some key-words give an impression about the contents of the chapter (expectation constraints, two-stage stochastic programs with quadratic recourse, probabilistic error bounds, stationary solutions, noisy amplitude-based phase retrievel). Three algorithms are inserted. Chapter 11 is on nonconvex game problems, a two-sided introduction informs on applications, on robustification (adversarial programming), on Nash solutions, \(N\)-person and noncooperative games. Then different kinds of such games and solutions (equilibria) are discussed together with (nonconvex and nondifferentiable) applications, followed by existence propositions and computational algorithms (Gauss-Seidel surrogation algorithm), presentation of so-called potential games leading to an optimization-based algorithm and finally algorithms, which uses statements oriented to formulations of a noncooperative game as a minmax problem.

MSC:

90-01 Introductory exposition (textbooks, tutorial papers, etc.) pertaining to operations research and mathematical programming
90C26 Nonconvex programming, global optimization
90-02 Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming
91-08 Computational methods for problems pertaining to game theory, economics, and finance
90C90 Applications of mathematical programming
90C17 Robustness in mathematical programming
90C15 Stochastic programming
90C20 Quadratic programming
90C30 Nonlinear programming
90C32 Fractional programming
90C56 Derivative-free methods and methods using generalized derivatives
PDFBibTeX XMLCite
Full Text: DOI