Mangasarian / Meyer / Robinson Nonlinear Programming 3

Proceedings of the Special Interest Group on Mathematical Programming Symposium Conducted by the Computer Sciences Department at the University of Wisconsin-Madison, July 11-13, 1977
1. Auflage 2014
ISBN: 978-1-4832-6032-7
Verlag: Elsevier Science & Techn.
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, 486 Seiten, Web PDF

Nonlinear Programming 3 covers the proceedings of the Special Interest Group on Mathematical Programming Symposium conducted by the Computer Sciences Department at the University of Wisconsin, Madison, on July 11-13, 1977. This book is composed of 17 chapters. The first eight chapters describe some of the most effective methods available for solving linearly and nonlinearly constrained optimization problems. The subsequent chapter gives algorithms for the solution of nonlinear equations together with computational experience. Other chapters provide some applications of optimization in operations research and a measurement procedure for optimization algorithm efficiency. These topics are followed by discussion of the methods for solving large quadratic programs and algorithms for solving stationary and fixed point problems. The last chapters consider the minimization of certain types of nondifferentiable functions and a type of Newton method. This book will prove useful to mathematicians and computer scientists.

Autoren/Hrsg.

Mangasarian, Olvi L.

Meyer, Robert R.

Robinson, Stephen M.

Inhaltsverzeichnis

1;Front Cover;1
2;Nonlinear Programming 3;4
3;Copyright Page;5
4;Table of Contents;6
5;CONTRIBUTORS;8
6;PREFACE;10
7;CHAPTER 1. MONOTONE OPERATORS AND AUGMENTED LAGRANGIAN METHODS IN NONLINEAR PROGRAMMING;12
7.1;ABSTRACT;12
7.2;1. INTRODUCTION;13
7.3;2. MONOTONE OPERATORS AND VARIATIONAL INEQUALITIES;17
7.4;3. PROXIMAL POINT ALGORITHM FOR MONOTONE OPERATORS;22
7.5;4. APPLICATION TO CONVEX PROGRAMMING;25
7.6;5. APPLICATION TO VARIATIONAL INEQUALITIES;31
7.7;REFERENCES;35
8;CHAPTER 2. THE CONVERGENCE OF VARIABLE METRIC METHODS FOR NONLINEARLY CONSTRAINED OPTIMIZATION CALCULATIONS;38
8.1;ABSTRACT;38
8.2;1. INTRODUCTION;39
8.3;2. SOME CONDITIONS AND THEIR CONSEQUENCES;44
8.4;3. A GENERAL THEOREM EOR SUPERLINEAR CONVERGENCE;52
8.5;4. THE DEFINITION OF Bk+1;57
8.6;5. AN R-SUPERLINEAR CONVERGENCE THEOREM;67
8.7;ACKNOWLEDGMENT;72
8.8;REFERENCES;73
9;CHAPTER 3. A HYBRID METHOD FOR NONLINEAR PROGRAMMING;76
9.1;ABSTRACT;76
9.2;1. INTRODUCTION;77
9.3;2. THE METHOD;80
9.4;3. GLOBAL PROPERTIES;87
9.5;4. LOCAL PROPERTIES;95
9.6;5. CONCLUSIONS;105
9.7;REFERENCES;106
10;CHAPTER 4. TWO-PHASE ALGORITHM FOR NONLINEAR CONSTRAINT PROBLEMS;108
10.1;ABSTRACT;108
10.2;1. INTRODUCTION;109
10.3;2. LINEARIZATION OF NONLINEAR CONSTRAINTS;114
10.4;3. EXTERNAL SQUARED PENALTY;120
10.5;4. PRACTICAL IMPLEMENTATION;123
10.6;5. DISCUSSION;128
10.7;REFERENCES;134
11;CHAPTER 5. QUASI-NEWTON METHODS FOR EQUALITY CONSTRAINED OPTIMIZATION: EQUIVALENCE OF EXISTING METHODS AND A NEW IMPLEMENTATION;136
11.1;1. INTRODUCTION;136
11.2;2. THE MULTIPLIER EXTENSION QUASI-NEWTON METHODS;144
11.3;3. THE STRUCTURED MULTIPLIER EXTENSION QUASI-NEWTON METHODS;145
11.4;4. THE MULTIPLIER UPDATE QUASI-NEWTON METHODS;147
11.5;5. THE BALANCED MULTIPLIER UPDATE QUASI-NEWTON METHODS;149
11.6;6. THE QUADRATIC PROGRAMMING QUASI-NEWTON METHOD;152
11.7;7. THE ADDITION OF SUPERSTRUCTURE;157
11.8;8. THE MULTIPLIER SUBSTITUTION QUASI-NEWTON METHODS;160
11.9;9. THE STRUCTURED MULTIPLIER SUBSTITUTION QUASI-NEWTON METHODS;162
11.10;10. THE BEST OF THE MULTIPLIER QUASI-NEWTON METHODS;164
11.11;11. AN IMPLEMENTATION BASED ON THE SVD;171
11.12;REFERENCES;173
12;CHAPTER 6. AN IDEALIZED EXACT PENALTY FUNCTION;176
12.1;ABSTRACT;176
12.2;1. INTRODUCTION;177
12.3;2. MOVEMENT OF A PARTICLE UNDER DIFFERENT FORCES;178
12.4;3. FLETCHER'S EXACT PENALTY FUNCTION (EQUALITY CASE);188
12.5;4. THE INEQUALITY CONSTRAINED PROBLEM;193
12.6;5. FLETCHER'S EXACT PENALTY FUNCTION (INEQUALITY CASE);202
12.7;REFERENCES;206
13;CHAPTER 7. EXACT PENALTY ALGORITHMS FOR NONLINEAR PROGRAMMING;208
13.1;ABSTRACT;208
13.2;1. INTRODUCTION;209
13.3;2. DEFINITIONS AND NOTATIONS;211
13.4;3. STATIONARY POINTS OF THE EXACT PENALTY FUNCTION AND OPTIMALITY FUNCTIONS;212
13.5;4. DESCRIPTION OF THE ALGORITHM;215
13.6;5. RATE OF CONVERGENCE OF THE EXACT PENALTY ALGORITHMS;227
13.7;6. COMPUTATIONAL RESULTS;232
13.8;7. ADDITIONAL RESULTS;233
13.9;ACKNOWLEDGMENTS;234
13.10;REFERENCES;235
14;CHAPTER 8. A VARIABLE METRIC METHOD FOR LINEARLY CONSTRAINED MINIMIZATION PROBLEMS;236
14.1;1. INTRODUCTION;236
14.2;2. GENERAL DESCRIPTION OF THE ALGORITHM;237
14.3;3. DETAILED STATEMENT OF THE ALGORITHM;245
14.4;4. SUPERLINEAR CONVERGENCE;250
14.5;REFERENCES;254
15;CHAPTER 9. SOLVING SYSTEMS OF NONLINEAR EQUATIONS BY BROYDEN'S METHOD WITH PROJECTED UPDATES;256
15.1;ABSTRACT;256
15.2;1. INTRODUCTION;257
15.3;2. THE NEW METHOD;260
15.4;3. BEHAVIOR ON LINEAR OR PARTLY LINEAR PROBLEMS;269
15.5;4. LOCAL Q-SUPERLINEAR CONVERGENCE ON NONLINEAR PROBLEMS;276
15.6;5. COMPUTATIONAL RESULTS;285
15.7;6. SUMMARY AND CONCLUSIONS;290
15.8;7. REFERENCES;291
16;CHAPTER 10. AT THE INTERFACE OF MODELING AND ALGORITHMS RESEARCH;294
16.1;ABSTRACT;294
16.2;I. INTRODUCTION AND SUMMARY;295
16.3;II. THE MID-1976 PILOT—A SUMMARY DESCRIPTION;297
16.4;III. COMPUTER SOLUTION OF THE PILOT MODEL;302
16.5;IV. TESTING ALGORITHMS AND DEVELOPING CODES;306
16.6;V. WELFARE EQUILIBRIUM VARIANT OF PILOT;309
16.7;REFERENCES;312
17;CHAPTER 11. MODELING COMBINATORIAL MATHEMATICAL PROGRAMMING PROBLEMS BY NETFORMS: AN ILLUSTRATIVE APPLICATION;314
17.1;ABSTRACT;314
17.2;INTRODUCTION;315
17.3;THE PROBLEM;318
17.4;A NETFORM MODEL;322
17.5;A MORE ADVANCED COMBINATORIAL REQUIREMENT;327
17.6;PATHS WITHOUT UNIQUE NODES;333
17.7;PATH SEPARATIONS FROM THE ORIGIN;338
17.8;HANDLING THE SINGLE PATH RESTRICTION;342
17.9;TELESCOPING THE NETFORM FOR SOLUTION EFFICIENCY;344
17.10;CONCLUSION;345
17.11;REFERENCES;346
18;CHAPTER 12. ON THE COMPARATIVE EVALUATION OF ALGORITHMS FOR MATHEMATICAL PROGRAMMING PROBLEMS;348
18.1;ABSTRACT;348
18.2;1. INTRODUCTION;350
18.3;2. MEASUREMENT OF COMPUTATIONAL SPEED;353
18.4;3. TIME-EQUIVALENT NUMBER OF FUNCTION EVALUATIONS;356
18.5;4. NUMERICAL EXPERIMENTS;360
18.6;5. NUMERICAL RESULTS;364
18.7;6. CONCLUSIONS AND RECOMMENDATIONS;368
18.8;REFERENCES;370
19;CHAPTER 13. A SPECIAL CLASS OF LARGE QUADRATIC PROGRAMS;372
19.1;ABSTRACT;372
19.2;1. INTRODUCTION;373
19.3;2. PRELIMINARY RESULTS;375
19.4;3. ALGORITHMS;380
19.5;4. APPLICATIONS AND COMPUTATIONAL EXPERIENCE;388
19.6;TABLE;395
19.7;REFERENCES;399
20;CHAPTER 14. COMPUTING STATIONARY POINTS, AGAIN;402
20.1;1. INTRODUCTION;402
20.2;2. A SPECIAL CASE;404
20.3;3. OVERVIEW OF TRANSFORMATION;406
20.4;4. THE GENERAL CASE;407
20.5;5 . AN EXAMPLE;411
20.6;6. APPENDIX;415
20.7;BIBLIOGRAPHY;416
21;CHAPTER 15. A COMBINATORIAL LEMMA FOR FIXED POINT ALGORITHMS;418
21.1;ABSTRACT;418
21.2;1. INTRODUCTION;419
21.3;2. MAIN RESULT;421
21.4;3. SPERNER'S LEMMA FOR POLYHEDRA;429
21.5;4. ALGORITHMS FOR FINDING APPROXIMATELY FIXED POINTS OF CONTINUOUS FUNCTIONS MAPPING A SIMPLEX INTO ITSELF;432
21.6;REFERENCES;438
22;CHAPTER 16. MINIMISATION DE FONCTIONS LOCALEMENT LIPSCHITZIENNES: APPLICATIONS A LA PROGRAMMATION MI-CONVEXE, MI-DIFFERENTIABLE;440
22.1;INTRODUCTION;440
22.2;I. UNE MÉTHODE GÉNÉRALE POUR LA MINIMISATION SANS CONTRAINTES DE FONCTIONS LOCALEMENT LIPSCHITZIENNES;442
22.3;II. APPLICATIONS À LA PROGRAMMATION MI-CONVEXE, MI-DIFFÉRENTIABLE;450
22.4;III. MINIMISATION DE FONCTIONS LOCALEMENT LIPSCHITZIENNES SUR DES FERMÉS;466
22.5;BIBLIOGRAPHIE;470
23;CHAPTER 17. A MODIFIED NEWTON ALGORITHM FOR FUNCTIONS OVER CONVEX SETS;472
23.1;ABSTRACT;472
23.2;1. INTRODUCTION;473
23.3;2. ALGORITHM;474
23.4;3. CONVERGENCE ANALYSIS;476
23.5;4. THE FINITE-DIMENSIONAL CASE;480
23.6;5. NUMERICAL EXAMPLES;482
23.7;ACKNOWLEDGEMENTS;483
23.8;REFERENCES;484
24;SUBJECT INDEX;486