INSEAD Library

Includes bibliographical references and index

Digitized

Introduction to Minimax Contents PREFACE Chapter I. BEST APPROXIMATION BY ALGEBRAIC POLYNOMIALS DISCRETE CASE ............................................................................................ 6 § 1. Statement of the problem ..................................................................................... 6 § 2. Chebyshev interpolation ...................................................................................... 7 §3. General discrete case; de la Vallée-Poussin algorithm .......................................... 15 §4. R -algorithm ............................................................................................. 22 § 5. Reduction to linear programming ....................................................................... 26 Chapter II. BEST APPROXIMATION BY ALGEBRAIC POLYNOMIALS CONTINUOUS CASE .................................................................................... 31 §1. Statement of the problem .................................................................................... 31 §2. Chebyshev theorem. Chebyshev polynomials ...................................................... 32 §3. Limit theorems 37 §4. Remet' method of successive Chebyshev interpolations ....................................... 40 §5. Method of grids ................................................................................................... 44 § 6*. Behavior of coefficients of polynomials of best approximation ............................ 46 Chapter III. THE DISCRETE MINIMAX PROBLEM ............................................................ 50 § 1. Statement of the problem ................................................................................... 50 § 2. Properties of the maximum function .................................................................. 51 §3. Necessary conditions for a minimax .................................................................... 57 §4. Sufficient conditions for a local minimax. Some estimates .................................... 66 §5. Method of coordinatewise descent. Method of steepest descent. Counterexamples .............................................................................................. 73 §6. First method of successive approximations ......................................................... 82 §7. e -Stationary points. Second method of successive approximations...................... 91 § 8. The D-function. Third method of successive approximations .............................. 98 §9. Concluding remarks ......................................................................................... 107 Chapter IV. THE DISCRETE MINIMAX PROBLEM WITH CONSTRAINTS 113 1 § 1. Statement of the problem ................................................................................. 113 §2. Necessary conditions for a minimax .................................................................. 113 §3. Geometric interpretation of the necessary conditions 117 §4. Sufficient conditions for a local minimax with constraints ................................. 123 §5. Some estimates ............................................................................................... 127 §6. Method of successive approximations .............................................................. 130 Chapter V. THE GENERALIZED PROBLEM OF NONLINEAR PROGRAMMING ................ 137 §1. Statement of the problem ................................................................................ 137 §2. Properties of sets defined by inequalities ......................................................... 137 §3. Necessary conditions for a minimax ................................................................ 146 §4. Dependence of direction of descent on specific features of Q............................. 151 §5. Lagrange multipliers and the Kuhn-Tucker theorem ........................................ 155 §6. First method of successive approximations ...................................................... 160 §7. Determination of ( e,u-quasistationary points. Second method of successive approximations ......................................................................... 170 §8. Method of steepest descent. Case of linear constraints ..................................... 173 §9. Nonlinear constraints. Correction of directions ................................................ 177 §10. Penalty functions 182 §11. Concluding remarks ...................................................................................... 185 Chapter VI. THE CONTINUOUS MINIMAX PROBLEM .................................................... 187 §1. Statement of the problem ................................................................................ 187 §2. Fundamental theorems ................................................................................... 187 §3. Geometric interpretation of the necessary condition for a minimax. Some corollaries 195 §4. Convergence of the grid method ...................................................................... 204 §5. Special case of the minimax theorem ............................................................... 216 § 6*. Determination of saddle points on polyhedra................................................. 221 §7. Best approximation of functions of several variables by generalized polynomials §8. Best approximation of functions by algebraic polynomials on an interval .......................................................................................................... 236 Appendix I. ALGEBRAIC INTERPOLATION ..................................................................... 242 §1. Divided differences .......................................................................................... 242 §2. Interpolating polynomials ................................................................................ 244 Appendix II. CONVEX SETS AND CONVEX FUNCTIONS ................................................ 248 §1. Convex hulls. Separation theorem ................................................................... 248 §2. Convex cones .................................................................................................. 254 §3. Convex functions ............................................................................................ 260 Appendix CONTINUOUS AND CONTINUOUSLY DIFFERENTIABLE 230 FUNCTIONS ......................................................................................... 264 §1. Continuous functions 264 §2. Some equalities and inequalities for continuous functions ............................... 265 § 3. Continuously differentiable functions ............................................................. 269 Appendix IV. DETERMINATION OF THE POINT NEAREST THE ORIGIN ON A POLYHEDRON. ITERATIVE METHODS .................................................. 276 Supplement. ON MANDEL'SHTAM'S PROBLEM ............................................................. 296 NOTES .......................................................................................................................... 300 BIBLIOGRAPHY ............................................................................................................ 303 SUBJECT INDEX .......................................................................................................... 307