Convex analysis and minimization algorithms II: Advanced theory and bundle methods.

*(English)*Zbl 0795.49002
Grundlehren der Mathematischen Wissenschaften. 306. Berlin: Springer- Verlag. xvii, 346 p. (1993).

As the second book in a two-volume series, this text retains the notation and organization of Volume I. In particular, its chapters are numbered 9- 15.Three of these deal with advanced topics in “pure” convex analysis in finite-dimensional spaces – the Legendre-Fenchel conjugate (Chap. 10), the theory of the \(\epsilon\)-subdifferential (Chap. 11), and abstract duality in convex programming (Chap. 12). The other four build toward a selection of implementable algorithms for the numerical minimization of nondifferentiable convex functions, including bundle methods, cutting plane methods, trust region ideas, and other refinements. All of these algorithms use only the following information about the minimand \(f\): there is some “black box” (U1) which takes as input a point \(x\), and returns the number \(f(x)\) and a vector \(s(x)\) lying somewhere in the subdifferential \(\partial f(x)\). The development starts in Chapter 9, with a description of how, given a point \(x\), repeated calls to (U1) can be used to build up a convex polyhedron inside \(\partial f(x)\). Either this polyhedron eventually contains a descent direction for \(f\) based at \(x\), or else \(0\) lies in \(\partial f(x)\) and hence \(x\) gives the desired minimum. The authors describe a descent method built around this iteration, taking care to point out that it is “bad but basic”. Likewise, \(\epsilon\)-descent methods built around inner constructions of the \(\epsilon\)-subgradient (the topic of Chap. 13) turn out to be as impractical for real computing as they are essential for explaining how the useful methods set out later actually work.

Chapters 14 and 15 contain several algorithms for practical nonsmooth convex programming. The highlight of Chapter 14 is a bundle method in dual form, complete with thorough discussions of direction-finding, line- search, and convergence properties. In Chapter 15, the simplest form of the cutting-plane algorithm is shown to be inadequate, and a variety of remedies is proposed. Three of these work in the primal space, and can be motivated by the basic method’s inherent instability; a fourth works in the dual space, and is proposed to overcome the slow convergence of the basic steepest descent algorithm. One primal variant, “stabilization by penalty” is singled out for deeper analysis: here the cutting plane function \(\check f_ k\) underestimating the minimand \(f\) is augmented with a quadratic penalty term to produce a quadratic function whose minimum defines the next point of interest. This selection is motivated by the method’s intimate relation to the procedure of Moreau-Yosida regularization, which is clearly explained; its convergence properties are analysed in detail.

Throughout this work, the emphasis is on the mathematical principles underlying the effective design of convex programming algorithms. Some details concerning implementation are present, and the results of some numerical experiments appear, but there is no simple appendix listing (for example) a FORTRAN program capable of minimizing any convex function. This is not so much an oversight as an understated expression of the philosophy implicit in both volumes: numerical methods should be chosen with care and implemented with understanding. Any reader who has understood Chapters 14 and 15 (and who has access to a standard subroutine that can minimize convex quadratic functions subject to linear constraints) will be in an excellent position not only to write computer code in the language of his/her choice, but also to claim real expertise in its theoretical foundations.

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

Chapters 14 and 15 contain several algorithms for practical nonsmooth convex programming. The highlight of Chapter 14 is a bundle method in dual form, complete with thorough discussions of direction-finding, line- search, and convergence properties. In Chapter 15, the simplest form of the cutting-plane algorithm is shown to be inadequate, and a variety of remedies is proposed. Three of these work in the primal space, and can be motivated by the basic method’s inherent instability; a fourth works in the dual space, and is proposed to overcome the slow convergence of the basic steepest descent algorithm. One primal variant, “stabilization by penalty” is singled out for deeper analysis: here the cutting plane function \(\check f_ k\) underestimating the minimand \(f\) is augmented with a quadratic penalty term to produce a quadratic function whose minimum defines the next point of interest. This selection is motivated by the method’s intimate relation to the procedure of Moreau-Yosida regularization, which is clearly explained; its convergence properties are analysed in detail.

Throughout this work, the emphasis is on the mathematical principles underlying the effective design of convex programming algorithms. Some details concerning implementation are present, and the results of some numerical experiments appear, but there is no simple appendix listing (for example) a FORTRAN program capable of minimizing any convex function. This is not so much an oversight as an understated expression of the philosophy implicit in both volumes: numerical methods should be chosen with care and implemented with understanding. Any reader who has understood Chapters 14 and 15 (and who has access to a standard subroutine that can minimize convex quadratic functions subject to linear constraints) will be in an excellent position not only to write computer code in the language of his/her choice, but also to claim real expertise in its theoretical foundations.

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 |