Numerical Optimization Techniques, 1985, 472 pp., ISBN 0-911575-07-3, $98.00
Describes theoretical foundations as well as applications of important techniques for Nonlinear Programming problems and Optimization problems for ordinary differential equations. Examples illustrate strong and weak points of particular methods and the advantages of combining them. Emphasizes interactive techniques for complex problems and experience gained with the DISO system at the Computing Center in Moscow. Includes hitherto unpublished material on Global Optimization. Edited by J. Stoer.
TABLE OF CONTENTS
Foreword ..... xi
Preface ..... xiii
Notation ..... 1
CHAPTER 1. AN INTRODUCTION TO OPTIMIZATION THEORY ..... 6
1. Convex Sets and Convex Functions ..... 6
2. Differentiability of Convex Functions ..... 16
3. Necessary and Sufficient Conditions of a Local Extremum of Functions of Many Variables ..... 27
4. Necessary and Sufficient Conditions for a Minimum of Functions on Sets ..... 34
5. Properties of Minimax Problems ..... 40
6. Conditions for a Minimum in Nonlinear Programming Problems without Differentiability ..... 60
7. Conditions for a Minimum in Nonlinear Programming Problems with Differentiability ..... 75
8. Necessary Conditions for a Minimum in Optimal Control
Problems ..... 94
CHAPTER 2. CONVERGENCE THEOREMS AND THEIR APPLICATION
TO THE INVESTIGATION OF NUMERICAL METHODS ..... 107
1. Stability of the First-Order Approximation ..... 107
2. The Method of Lyapunov Functions ..... 115
3. Theorems on Convergence of Iterative Processes ..... 129
4. Convergence of Processes Generated by Multivalued Mappings ..... 145
5. Methods for Solving Systems of Nonlinear Equations ..... 152
6. Numerical Methods for Finding a Minimax ..... 177
CHAPTER 3. THE PENALTY-FUNCTION METHOD ..... 196
1. The Exterior Penalty-Function Method ..... 197
2. Estimation of Accuracy ..... 215
3. The Cost-Function Parametrization Method ..... 234
4. The Interior Penalty-Function Method ..... 245
5. The Linearization Method ..... 255
CHAPTER 4. NUMERICAL METHODS FOR SOLVING NONLINEAR PROGRAMMING PROBLEMS USING MODIFIED LAGRANGIANS ..... 264
1. The Simplest Modification of the Lagrangian ..... 265
2. Modified Lagrangians ..... 279
3. Proof of Convergence for the Simple Iteration Method ..... 286
4. Solution of Convex Programming Problems ..... 301
5. Reduction to a Maximin Problem ..... 310
6. Reduction to a Minimax Problem ..... 321
CHAPTER 5. RELAXATION METHODS FOR SOLVING
NONLINEAR PROGRAMMING PROBLEMS ..... 330
1. Application of the Reduced Gradient Method to Solving Problems with Equality-Type Constraints ..... 330
2. A Generalization of the Reduced Gradient Method ..... 336
3. A Discrete Version of the Reduced Gradient Method ..... 351
4. The Conditional Gradient Method ..... 355
5. The Gradient Projection Method ..... 361
CHAPTER 6. NUMERICAL METHODS FOR SOLVING
OPTIMAL CONTROL PROBLEMS ..... 364
1. Basic Computational Formulas ..... 367
2. Necessary and Sufficient Conditions for a Minimum ..... 383
3. Numerical Methods Based on the Reduction to Nonlinear Programming Problems ..... 388
4. Discrete Minimum Principles ..... 398
5. Numerical Methods Based on Discrete Minimum Principle ..... 418
6. Some Generalizations ..... 423
7. Examples of Numerical Computations ..... 434
8. An Application to Differential Games ..... 455
CHAPTER 7. SEARCH FOR GLOBAL SOLUTIONS ..... 465
1. The General Notion of Coverings ..... 466
2. Covering a Parallelepiped ..... 474
3. Solution of Nonlinear Programming Problems ..... 491
4. Solution of Systems of Algebraic Equations ..... 502
5. Solution of Minimax Problems ..... 505
6. Solution of Multicriteria Problems ..... 509
Appendix I. Differentiability ..... 517
Appendix II. Some Properties of Matrices ..... 522
Appendix III. Some Properties of Mappings ..... 530
Notes and Comments ..... 533
References ..... 539
Index ..... 554
List of Forthcoming Publications ..... 559
Transliteration Table (Russian-English) ..... 561