Nondifferentiable Optimization, 1985, 472 pp., ISBN 0-911575-09-X, $96.00

Systematic exposition of the theory and numerical techniques for optimization of nondifferentiable functions, including minimization of convex functions and maximum functions. Both Relaxation and Nonrelaxation methods are treated. Computational experience at the Institute of Computational Mathematics of Leningrad State University is detailed.

Preface ..... xi

Notation ..... xvi

CHAPTER 1. FUNDAMENTALS OF CONVEX ANALYSIS AND RELATED PROBLEMS ..... 1

1. Convex Sets. Convex Hulls. Separation Theorem ..... 1

2. Point-to-Set Mappings ..... 11

3. Convex Cone. Cone of Feasible Directions. Conjugate Cone ..... 22

4. Convex Functions. Continuity and Directional Differentiability ..... 33

5. Subgradients and Subdifferentials of Convex Functions ..... 49

6. Distance from a Set to a Cone. Conditions for a Minimum ..... 68

7. -subdifferentials ..... 76

8. Directional -derivatives. Continuity of the -subdifferential mapping ..... 88

9. Some Properties and Inequalities for Convex Functions ..... 101

10. Conditional -subdifferentials ..... 113

11. Conditional Directional Derivatives. Continuity of the Conditional -subdifferential mapping ..... 125

12. Representation of a Convex Set by Means of Inequalities ..... 138

13. Normal Cones. Conical Mappings ..... 147

14. Directional Differentiability of a Supremum Function ..... 153

15. Differentiability of a Convex Function ..... 161

16. Conjugate Functions ..... 177

17. Computation of -subgradients of some classes of convex functions ..... 192

CHAPTER 2. QUASIDIFFERENTIAL FUNCTIONS ..... 199

1. Definition and Examples of Quasidifferentiable Functions ..... 199

2. Basic Properties of Quasidifferentiable Functions. Basic Properties of Quasidifferential Calculus ..... 206

3. Calculating Quasidifferentials: Examples ..... 216

4. Quasidifferentiability of Convex-Concave Functions ..... 227

5. Necessary Conditions for an Extremum of a Quasidifferentiable Function on E_n ..... 235

6. Quasidifferentiable Sets ..... 242

7. Necessary Conditions for an Extremum of a Quasidifferentiable Function on a Quasidifferentiable Set ..... 251

8. The Distance Function from a Point to a Set ..... 265

9. Implicit Function ..... 276

CHAPTER 3. MINIMIZATION ON THE ENTIRE SPACE ..... 281

1. Necessary and Sufficient Conditions for a Minimum of a Convex Function on E_n ..... 281

2. Minimization of a Smooth Function ..... 284

3. The Method of Steepest Descent ..... 286

4. The Subgradient Method for Minimizing a Convex Function ..... 294

5. The Multistep Subgradient Method ..... 308

6. The Relaxation-Subgradient Method ..... 317

7. The Relaxation -subgradient method ..... 336

8. The Kelley Method ..... 345

9. Minimization of a Supremum-Type Function ..... 355

10. Minimization of a Convex Maximum-Type Function and the Extremum-Basis Method ..... 358

11. A Numerical Method for Minimizing Quasidifferentiable Functions ..... 367

CHAPTER 4. CONSTRAINED MINIMIZATION ..... 375

1. Necessary and Sufficient Conditions for a Minimum of a Convex Function on a Convex Set ..... 375

2. -stationary Points ..... 384

3. The Conditional Gradient Method ..... 387

4. The Method of Steepest Descent for the Minimization of Convex Functions ..... 393

5. The (,)-subgradient Method in the Presence of Constraints ..... 400

6. The Subgradient Method with a Constant Step-Size ..... 404

7. The Modified (,)-subgradient Method in the Presence of Constraints ..... 408

8. The Nonsmooth Penalty-Function Method ..... 413

9. The Kelley Method for the Minimization on a Convex Set ..... 420

10. The Relaxation-Subgradient Method in the Presence of Constraints ..... 423

Notes and Comments ..... 429

References ..... 433

Appendix 1. Bibliography and Guide to Publications on Quasidifferential Calculus ..... 443

Appendix 2. Bibliography on Quasidifferential Calculus as of January 1, 1985 ..... 445

Index ..... 449

List of Forthcoming Publications ..... 453

Transliteration Table (Russian-English) ..... 455