Optimization. Algorithms and consistent approximations.

*(English)*Zbl 0899.90148
Applied Mathematical Sciences 124. New York, NY: Springer. xx, 779 p. (1997).

This book is a serious and interesting monograph devoted to optimization problems seen from a specific point of view based on the concept of optimality functions and implementable algorithms. The author’s approach allows him to give an enormous volume of information about conditions of optimality in the form of zeros of (auxiliary) optimality functions, about numerical algorithms of solving optimality problems in terms of suitable point-to-set iterative mappings, and, moreover, to analyse such properties of these algorithms as efficiency, consistency, and implementation. Deep relations between the optimality conditions and the corresponding algorithms are proved. Finally, the similarity between finite-dimensional and infinite-dimensional problems is clarified.

Chapter 1 “Unconstrained optimization” deals with unconstrained optimization problems of the form \(\min_{X\in \mathbb{R}^n} f(x)\), or sometimes, \(\min_{x\in X}f(x)\) with an “unstructured” convex constraint set \(X\); the function \(f(\cdot)\) is assumed continuously differentiable. The chapter presents different (first- and second-order) necessary and sufficient conditions for optimiality, a general analysis of different algorithms and their convergence conditions, and, in consequence, an analysis of gradient methods, Newton’s method and its modification, methods of conjugate directions, secant methods; the case of one-dimensional optimization is considered in a special section. The chapter is completed by some special analysis of Newton’s method of solving equations and inequalities.

Chapter 2 “Finite min-max and constrained optimization” deals with the min-max problem \(\min_{x\in\mathbb{R}^n} \max_{j\in{\mathbf q}}f^j(x)\) and constrained optimization problem of the form \(\min\{f^0(x): x\in\mathbb{R}^n\), \(f^j(x)\leq 0\) \((j\in{\mathbf q})\), \(g^k(x)=0 (k\in{\mathbf r})\}\), where \(f^0(\cdot)\) is an either continuous differentiable function or a function of type \(f^0(x)= \max_{k\in{\mathbf p}}c^k(x)\) with continuously differentiable functions \(c^k(\cdot)\) and a finite set \({\mathbf p}\). The chapter presents optimality conditions for both problems, a general analysis and their convergence conditions, and then some concrete algorithms such as first-order min-max algorithms, Newton’s min-max algorithms, methods of centers, penalty function algorithms, augmented Lagrangian methods; sequential quadratic programming methods.

Chapter 3 “Semi-infinite optimization” in its basic part repeats results of chapter 2, however, for the problems \(\min_{x\in\mathbb{R}^n} \max_{j\in{\mathbf q}} \psi^j(x)\) and the constrained optimization problem of the form \(\min\{\psi^0(x): x\in\mathbb{R}^n\), \(\psi^j(x)\leq 0\) \((j\in{\mathbf q})\), \(g^k(x)=0\) \((k\in{\mathbf r})\}\), where \(\psi^j(\cdot)\), \(j=0,1,\dots, q\) are of the form \(\psi^j(x)= \max_{y_j\in{\mathbf Y}_{\mathbf j}} \psi^j(x,y_j)\), \(\psi^j: \mathbb{R}^n\times \mathbb{R}^{m_j}\to \mathbb{R}\), \(Y_j\) are compact subsets in \(\mathbb{R}^{m_j}\).

Chapter 4 “Optimal control” is devoted to optimality conditions and algorithms for several classes of optimal control problems. The author describes canonical forms of optimal control problems, formulates optimality conditions and describes consistent approximations to these problems in the form of a master algorithm that controls the precision of the approximation. The author’s approach allows to use results of previous chapters for the effective searching for error estimates. The algorithm of solving unconstrained problems, problems with inequality constraints, ones with equality constraints, and ones with mixed constraints are considered separately.

Chapter 5 “Mathematical background”, is a short summary of results from the calculus of Banach spaces, the theory of convex sets and functions, the analysis of set-valued functions, minimax theorems, differential equations and so on.

In general the book presents an exhaustive modern treatment of numerous finite-dimensional and infinite-dimensional optimization problems; it is among the first in which one can find the concepts of optimality functions, consistent approximations to infinite-dimensional problems, and implementable optimization algorithms. The book will be useful to graduate and postgraduate students studying optimality problems as well as to specialists in the field. Undoubtedly, it will be also useful as a reference book.

Chapter 1 “Unconstrained optimization” deals with unconstrained optimization problems of the form \(\min_{X\in \mathbb{R}^n} f(x)\), or sometimes, \(\min_{x\in X}f(x)\) with an “unstructured” convex constraint set \(X\); the function \(f(\cdot)\) is assumed continuously differentiable. The chapter presents different (first- and second-order) necessary and sufficient conditions for optimiality, a general analysis of different algorithms and their convergence conditions, and, in consequence, an analysis of gradient methods, Newton’s method and its modification, methods of conjugate directions, secant methods; the case of one-dimensional optimization is considered in a special section. The chapter is completed by some special analysis of Newton’s method of solving equations and inequalities.

Chapter 2 “Finite min-max and constrained optimization” deals with the min-max problem \(\min_{x\in\mathbb{R}^n} \max_{j\in{\mathbf q}}f^j(x)\) and constrained optimization problem of the form \(\min\{f^0(x): x\in\mathbb{R}^n\), \(f^j(x)\leq 0\) \((j\in{\mathbf q})\), \(g^k(x)=0 (k\in{\mathbf r})\}\), where \(f^0(\cdot)\) is an either continuous differentiable function or a function of type \(f^0(x)= \max_{k\in{\mathbf p}}c^k(x)\) with continuously differentiable functions \(c^k(\cdot)\) and a finite set \({\mathbf p}\). The chapter presents optimality conditions for both problems, a general analysis and their convergence conditions, and then some concrete algorithms such as first-order min-max algorithms, Newton’s min-max algorithms, methods of centers, penalty function algorithms, augmented Lagrangian methods; sequential quadratic programming methods.

Chapter 3 “Semi-infinite optimization” in its basic part repeats results of chapter 2, however, for the problems \(\min_{x\in\mathbb{R}^n} \max_{j\in{\mathbf q}} \psi^j(x)\) and the constrained optimization problem of the form \(\min\{\psi^0(x): x\in\mathbb{R}^n\), \(\psi^j(x)\leq 0\) \((j\in{\mathbf q})\), \(g^k(x)=0\) \((k\in{\mathbf r})\}\), where \(\psi^j(\cdot)\), \(j=0,1,\dots, q\) are of the form \(\psi^j(x)= \max_{y_j\in{\mathbf Y}_{\mathbf j}} \psi^j(x,y_j)\), \(\psi^j: \mathbb{R}^n\times \mathbb{R}^{m_j}\to \mathbb{R}\), \(Y_j\) are compact subsets in \(\mathbb{R}^{m_j}\).

Chapter 4 “Optimal control” is devoted to optimality conditions and algorithms for several classes of optimal control problems. The author describes canonical forms of optimal control problems, formulates optimality conditions and describes consistent approximations to these problems in the form of a master algorithm that controls the precision of the approximation. The author’s approach allows to use results of previous chapters for the effective searching for error estimates. The algorithm of solving unconstrained problems, problems with inequality constraints, ones with equality constraints, and ones with mixed constraints are considered separately.

Chapter 5 “Mathematical background”, is a short summary of results from the calculus of Banach spaces, the theory of convex sets and functions, the analysis of set-valued functions, minimax theorems, differential equations and so on.

In general the book presents an exhaustive modern treatment of numerous finite-dimensional and infinite-dimensional optimization problems; it is among the first in which one can find the concepts of optimality functions, consistent approximations to infinite-dimensional problems, and implementable optimization algorithms. The book will be useful to graduate and postgraduate students studying optimality problems as well as to specialists in the field. Undoubtedly, it will be also useful as a reference book.

Reviewer: P.Zabreiko (Minsk)

##### MSC:

90C30 | Nonlinear programming |

90-02 | Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming |

49-02 | Research exposition (monographs, survey articles) pertaining to calculus of variations and optimal control |

65K05 | Numerical mathematical programming methods |