Convex analysis and minimization algorithms. Part 1: Fundamentals.

*(English)*Zbl 0795.49001
Grundlehren der Mathematischen Wissenschaften 305. Berlin: Springer-Verlag (ISBN 3-540-56850-6/hbk; 978-3-642-08161-3/pbk). xvii, 417 p. (1993).

This is a carefully presented and beautifully illustrated exposition of the fundamentals of convex analysis in finite-dimensional vector spaces. It is almost completely elementary, in two senses: first, almost all of the mathematical techniques involved are available to a third-year undergraduate student of mathematics; second, the exposition so clear and detailed that anyone who has reached (or surpassed) this level of education will have no trouble understanding every word. As the text’s subtitle – “Fundamentals” – suggests, the balance between the two topics in the title lies very much in favour of the basics of convex analysis. Minimization algorithms are discussed comparatively briefly, and at quite a high level of abstraction (Chaps. 2 and 8): their role in this first volume is to motivate the key results and to clarify which of these are truly the “fundamentals.” (The balance is approximately reversed in volume II.) This motivational scheme is very successful. The reader always knows not only what is being asserted, but why it is interesting and how it might be useful.

The text’s structure is logical, and draws the reader steadily through the basics of convex analysis. It does not, however, solve the optimization problem, “Prove all the major theorems in least time.” Instead, the authors deliberately take time out to draw connections between different aspects of the theory, to suggest applications, and to point out alternative proofs and interpretations as they arise. Students who follow these side-trips will gain depth; “experts” will also find in them much to appreciate.

The text opens (Chap. 1) with a discussion of convex functions of one real variable – a convenient introduction to the continuity properties, subgradients, and conjugate functions that show up in more generality later on. Convex sets in finite-dimensional spaces, together with the usual apparatus (relative interior, recession cone, extreme points, tangent and normal cones), form the subject of Chap. 3, where one also meets the central Separation Theorem. Then general convex functions are discussed (Chap. 4), and the duality between sublinear functions and convex sets is examined (Chap. 5). The subdifferential (Chap. 6) and its calculus is presented for finite-valued convex functions only. (Extended- valued functions are treated in volume II.) This is sufficient to treat convex programming problems with explicit equality and inequality constraints: suitable constraint qualifications and the multiplier rule are discussed (Chap. 7), and there is an introduction to the Lagrangian function and theory of duality. (Much more on abstract duality appears in volume II, along with two other essential topics – namely, the subdifferential calculus for extended-real-valued convex functions, and the full story on the Legendre-Fenchel transform.)

The discussion of numerical minimization techniques in Chapter 2 is purely introductory. The basic scheme of iterating between direction- finding and line-search is introduced, together with three direction- finding methods (steepest descent, Newton-type, and conjugate gradient) and Wolfe’s line-search algorithm. Only smooth, unconstrained problems are considered; convexity is not exploited. The basic issues are revisited in Chapter 8, where descent directions for convex problems are discussed. The main lesson of this chapter, however, is that nondifferentiability makes the problem much more difficult: this propels the reader into the deeper study of convex minimization algorithms in volume II.

The bibliography is excellent; it is the same in both volumes.

The text’s structure is logical, and draws the reader steadily through the basics of convex analysis. It does not, however, solve the optimization problem, “Prove all the major theorems in least time.” Instead, the authors deliberately take time out to draw connections between different aspects of the theory, to suggest applications, and to point out alternative proofs and interpretations as they arise. Students who follow these side-trips will gain depth; “experts” will also find in them much to appreciate.

The text opens (Chap. 1) with a discussion of convex functions of one real variable – a convenient introduction to the continuity properties, subgradients, and conjugate functions that show up in more generality later on. Convex sets in finite-dimensional spaces, together with the usual apparatus (relative interior, recession cone, extreme points, tangent and normal cones), form the subject of Chap. 3, where one also meets the central Separation Theorem. Then general convex functions are discussed (Chap. 4), and the duality between sublinear functions and convex sets is examined (Chap. 5). The subdifferential (Chap. 6) and its calculus is presented for finite-valued convex functions only. (Extended- valued functions are treated in volume II.) This is sufficient to treat convex programming problems with explicit equality and inequality constraints: suitable constraint qualifications and the multiplier rule are discussed (Chap. 7), and there is an introduction to the Lagrangian function and theory of duality. (Much more on abstract duality appears in volume II, along with two other essential topics – namely, the subdifferential calculus for extended-real-valued convex functions, and the full story on the Legendre-Fenchel transform.)

The discussion of numerical minimization techniques in Chapter 2 is purely introductory. The basic scheme of iterating between direction- finding and line-search is introduced, together with three direction- finding methods (steepest descent, Newton-type, and conjugate gradient) and Wolfe’s line-search algorithm. Only smooth, unconstrained problems are considered; convexity is not exploited. The basic issues are revisited in Chapter 8, where descent directions for convex problems are discussed. The main lesson of this chapter, however, is that nondifferentiability makes the problem much more difficult: this propels the reader into the deeper study of convex minimization algorithms in volume II.

The bibliography is excellent; it is the same in both volumes.

Reviewer: P.D.Loewen (Vancouver)

##### MSC:

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

49J52 | Nonsmooth analysis |

90C25 | Convex programming |

52A41 | Convex functions and convex programs in convex geometry |

65K10 | Numerical optimization and variational techniques |

26B25 | Convexity of real functions of several variables, generalizations |