Nondifferentiable Optimization

ISBN-13: 9781461382706 / Angielski / Miękka / 2012 / 452 str.

V. F. Dem'yanov; L. V. Vasil'ev; Tetsushi Sasagawa

Opis

Of recent coinage, the term "nondifferentiable optimization" (NDO) covers a spectrum of problems related to finding extremal values of nondifferentiable functions. Problems of minimizing nonsmooth functions arise in engineering applications as well as in mathematics proper. The Chebyshev approximation problem is an ample illustration of this. Without loss of generality, we shall consider only minimization problems. Among nonsmooth minimization problems, minimax problems and convex problems have been studied extensively ( 31], 36], 57], 110], 120]). Interest in NDO has been constantly growing in recent years (monographs: 30], 81], 127] and articles and papers: 14], 20], 87]- 89], 98], 130], 135], 140]- 142], 152], 153], 160], all dealing with various aspects of non- smooth optimization). For solving an arbitrary minimization problem, it is neces- sary to: 1. Study properties of the objective function, in particular, its differentiability and directional differentiability. 2. Establish necessary (and, if possible, sufficient) condi- tions for a global or local minimum. 3. Find the direction of descent (steepest or, simply, feasible--in appropriate sense). 4. Construct methods of successive approximation. In this book, the minimization problems for nonsmooth func- tions of a finite number of variables are considered. Of fun- damental importance are necessary conditions for an extremum (for example, 24], 45], 57], 73], 74], 103], 159], 163], 167], 168].

Spis treści

1. Fundamentals of Convex Analysis and Related Problems.- 1. Convex sets. Convex hulls. Separation theorem.- 2. Point-to-set mappings.- 3. Convex cone. Cone of feasible directions. Conjugate cone.- 4. Convex functions. Continuity and directional differentiability.- 5. Subgradients and subdifferentials of convex functions.- 6. Distance from a set to a cone. Conditions for a minimum.- 7. ?-subdifferentials.- 8. Directional ?-derivatives. Continuity of the ?-subdifferential mapping.- 9. Some properties and inequalities for convex functions.- 10. Conditional ?-subdifferentials.- 11. Conditional directional derivatives. Continuity of the conditional ?-subdifferential mapping.- 12. Representation of a convex set by means of inequalities.- 13. Normal cones. Conical mappings.- 14. Directional differentiability of a supremum function.- 15. Differentiability of a convex function.- 16. Conjugate functions.- 17. Computation of ?-subgradients of some classes of convex function.- 2. Quasidifferentiable Functions.- 1. Definition and examples of quasidifferentiable functions.- 2. Basic properties of quasidifferentiable functions. Basic formulas of quasidifferential calculus.- 3. Calculating quasidifferentials: examples.- 4. Quasidifferentiability of convexo-concave functions.- 5. Necessary conditions for an extremum of a quasidifferentiable function on En.- 6. Quasidifferentiable sets.- 7. Necessary conditions for an extremum of a quasidifferentiable function on a quasidifferentiable set.- 8. The distance function from a point to a set.- 9. Implicit function.- 3. Minimization on the Entire Space.- 1. Necessary and sufficient conditions for a minimum of a convex function on En.- 2. Minimization of a smooth function.- 3. The method of steepest descent.- 4. The subgradient method for minimizing a convex function.- 5. The multistep subgradient method.- 6. The relaxation-subgradient method.- 7. The relaxation ?-subgradient method.- 8. The Kelley method.- 9. Minimization of a supremum-type function.- 10. Minimization of a convex maximum-type function and the extremum-basis method.- 11. A numerical method for minimizing quasidifferentiable functions.- 4. Constrained Minimization.- 1. Necessary and sufficient conditions for a minimum of a convex function on a convex set.- 2. ?-stationary points.- 3. The conditional gradient method.- 4. The method of steepest descent for the minimization of convex functions.- 5. The (?,µ)-subgradient method in the presence of constraints.- 6. The subgradient method with a constant step-size.- 7. The modified (?,µ)-subgradient method in the presence of constraints.- 8. The nonsmooth penalty-function method.- 9. The Kelley method for the minimization on a convex set.- 10. The relaxation-subgradient method in the presence of constraints.- Notes and Comments.- References.- Appendix 1. Bibliography and guide to publications on Quasidifferential Calculus.- Appendix 2. Bibliography on Quasidifferential Calculus as of January 1, 1985.- List of forthcoming publications.- Transliteration table.