Mangasarian / Meyer / Robinson Nonlinear Programming 4

Proceedings of the Nonlinear Programming Symposium 4 Conducted by the Computer Sciences Department at the University of Wisconsin-Madison, July 14-16, 1980
1. Auflage 2014
ISBN: 978-1-4832-6017-4
Verlag: Elsevier Science & Techn.
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, 560 Seiten, Web PDF

Nonlinear Programming, 4 focuses on linear, quadratic, and nonlinear programming, unconstrained minimization, nonsmooth and discrete optimization, ellipsoidal methods, linear complementarity problems, and software evaluation. The selection first elaborates on an upper triangular matrix method for quadratic programming, solving quadratic programs by an exact penalty function, and QP-based methods for large-scale nonlinearly constrained optimization. Discussions focus on large-scale linearly constrained optimization, search direction for superbasic variables, finite convergence, basic properties, comparison of three active set methods, and QP-based methods for dense problems. The book then examines an iterative linear programming algorithm based on an augmented Lagrangian and iterative algorithms for singular minimization problems. The publication ponders on the derivation of symmetric positive definite secant updates, preconditioned conjugate gradient methods, and finding the global minimum of a function of one variable using the method of constant signed higher order derivatives. Topics include effects of calculation errors, application to polynomial minimization, using moderate additional storage, updating Cholesky factors, and utilizing sparse second order information. The selection is a valuable source of data for researchers interested in nonlinear programming.

Autoren/Hrsg.

Mangasarian, Olvi L.

Meyer, Robert R.

Robinson, Stephen M.

Inhaltsverzeichnis

1;Front Cover;1
2;Nonlinear Programming 4;4
3;Copyright Page;5
4;Table of Contents;6
5;CONTRIBUTORS;8
6;PREFACE;10
7;CHAPTER 1. AN UPPER TRIANGULAR MATRIX METHOD FOR
QUADRATIC PROGRAMMING;12
7.1;ABSTRACT;12
7.2;1. INTRODUCTION;13
7.3;2. A COMPARISON OF THREE ACTIVE SET METHODS;16
7.4;3. THE CALCULATION OF d AND
.;21
7.5;4. THE REVISION OF U AND L;24
7.6;5. DISCUSSION;30
7.7;ACKNOWLEDGMENTS;34
7.8;REFERENCES;35
8;CHAPTER 2. SOLVING QUADRATIC PROGRAMS
BY AN EXACT PENALTY FUNCTION;36
8.1;ABSTRACT;36
8.2;1. INTRODUCTION;37
8.3;2. THE METHOD;40
8.4;3. BASIC PROPERTIES;44
8.5;4. FINITE CONVERGENCE;53
8.6;5. COMPUTATIONAL RESULTS;64
8.7;ACKNOWLEDGMENT;65
8.8;REFERENCES;66
9;CHAPTER 3. QP–BASED
METHODS FOR LARGE-SCALE NONLINEARLY CONSTRAINED OPTIMIZATION;68
9.1;ABSTRACT;68
9.2;1. INTRODUCTION;69
9.3;2. LARGE-SCALE LINEARLY CONSTRAINED OPTIMIZATION;73
9.4;3. QP-BASED METHODS FOR DENSE PROBLEMS;79
9.5;4. THE USE OF A LINEARLY CONSTRAINED SUBPROBLEM;83
9.6;5. EXTENSION OF QP-BASED METHODS TO THE LARGE-SCALE CASE;87
9.7;6. REPRESENTING THE BASIS INVERSE;91
9.8;7. THE SEARCH DIRECTION FOR THE SUPERBASIC VARIABLES;97
9.9;8. AN INEQUALITY QP
APPROACH;102
9.10;9. CONCLUSIONS;104
9.11;REFERENCES;105
10;CHAPTER 4. NUMERICAL EXPERIMENTS WITH AN EXACT L1
PENALTY FUNCTION METHOD;110
10.1;ABSTRACT;110
10.2;1. INTRODUCTION;111
10.3;2. A GLOBALLY CONVERGENT ALGORITHM;117
10.4;3. AN ACTIVE SET METHOD;123
10.5;4. NUMERICAL EXPERIMENTS AND DISCUSSION;130
10.6;ACKNOWLEDGMENTS;137
10.7;REFERENCES;138
11;CHAPTER 5. AN ITERATIVE LINEAR PROGRAMMING ALGORITHM
BASED ON AN AUGMENTED LAGRANGIAN;142
11.1;ABSTRACT;142
11.2;REFERENCES;157
12;CHAPTER 6. ITERATIVE ALGORITHMS
FOR SINGULAR MINIMIZATION PROBLEMS;158
12.1;ABSTRACT;158
12.2;1. INTRODUCTION;159
12.3;2. THE QUADRATIC CASE;161
12.4;3. NONQUADRATIC CASE;167
12.5;4. MINIMIZATION IN THE PRESENCE OF ERRORS;170
12.6;CONCLUSIONS;174
12.7;ACKNOWLEDGMENTS;175
12.8;REFERENCES;176
13;CHAPTER 7. A NEW DERIVATION OF SYMMETRIC
POSITIVE DEFINITE SECANT UPDATES;178
13.1;ABSTRACT;178
13.2;1. INTRODUCTION AND BACKGROUND;179
13.3;2. THE BFGS AND DFP FROM THE GOOD AND BAD BROYDEN METHODS;183
13.4;3. HEREDITARY POSITIVE DEFINITENESS AND IREN SIZING FOR
SYMMETRIC RANK-TWO UPDATES;188
13.5;4. A PROJECTED BFGS FROM THE PROJECTED BROYDEN UPDATE;195
13.6;5. UPDATING CHOLESKY FACTORS;204
13.7;REFERENCES;206
13.8;APPENDIX: THE SCALED BFGS DERIVATION;208
14;CHAPTER
8. ON PRECONDITIONED CONJUGATE GRADIENT METHODS;212
14.1;ABSTRACT;212
14.2;I. INTRODUCTION;213
14.3;II. USING MODERATE ADDITIONAL STORAGE;217
14.4;III. UTILIZING SPARSE SECOND ORDER INFORMATION;225
14.5;REFERENCES;231
15;CHAPTER 9. FINDING THE GLOBAL MINIMUM OF A FUNCTION OF ONE VARIABLE USING THE METHOD OF CONSTANT
SIGNED HIGHER ORDER DERIVATIVES;234
15.1;ABSTRACT;234
15.2;1. INTRODUCTION;235
15.3;2. PRELIMINARY THEOREMS AND LEMMAS;236
15.4;3. ALGORITHMIC CONSIDERATIONS;238
15.5;4. APPLICATION TO POLYNOMIAL MINIMIZATION;247
15.6;5. EFFECTS OF CALCULATION ERRORS;249
15.7;6. COMMENT;253
15.8;REFERENCES;254
16;CHAPTER 10. ON A BUNDLE ALGORITHM
FOR NONSMOOTH OPTIMIZATION;256
16.1;ABSTRACT;256
16.2;1. INTRODUCTION;257
16.3;2. THE ALGORITHM WITHOUT CONSTRAINTS;260
16.4;3. LINEARLY CONSTRAINED PROBLEMS;273
16.5;APPENDIX;281
16.6;REFERENCES;291
17;CHAPTER 11. CONVERGENCE RESULTS IN A CLASS OF VARIABLE METRIC SUBGRADIENT METHODS1;294
17.1;ABSTRACT;294
17.2;1. INTRODUCTION;295
17.3;2. EXAMPLES;297
17.4;3. A CLASS OF VARIABLE METRIC SUBGRADIENT OPTIMIZATION
METHODS;301
17.5;4. VARIOUS METHODS;309
17.6;5. BEHAVIOUR ON SYSTEMS OF LINEAR EQUALITIES AND ON
QUADRATICS;314
17.7;6. EXPERIMENTS;319
17.8;7. CONCLUSION;328
17.9;8. APPENDIX;329
17.10;9. ACKNOWLEDGEMENTS;330
17.11;REFERENCES;334
18;CHAPTER 12. MONOTROPIC PROGRAMMING: DESCENT
ALGORITHMS AND DUALITY;338
18.1;ABSTRACT;338
18.2;1. INTRODUCTION;339
18.3;2. OPTIMALITY AND ELEMENTARY DIRECTIONS OF DESCENT;346
18.4;3. CONJUGATE FUNCTIONS AND THE DUAL PROBLEM;355
18.5;4. FORTIFIED ALGORITHMS WITH GUARANTEED DESCENT;368
18.6;REFERENCES;377
19;CHAPTER 13. APPROXIMATION AND CONVERGENCE
IN NONLINEAR OPTIMIZATION;378
19.1;ABSTRACT;378
19.2;1. INTRODUCTION;379
19.3;2. e-CONVERGENCE;382
19.4;3. BARRIER METHODS;389
19.5;4. e-CONVERGENCE AND p-CONVERGENCE;393
19.6;5. (EXTERIOR) PENALIZATION METHODS;395
19.7;6. CONVERGENCE OF BIVARIATE FUNCTIONS;398
19.8;7. METHOD OF MULTIPLIERS;401
19.9;REFERENCES;403
20;CHAPTER 14. UPPER PLANES OF QUADRATIC 0-1 FUNCTIONS
AND STABILITY IN GRAPHS;406
20.1;ABSTRACT;406
20.2;1. BASIC DEFINITIONS AND NOTATIONS;408
20.3;2. A CLASS OF UPPER PLANES FOR QUADRATIC 0-1 OPTIMIZATION;411
20.4;3. PLANE DUALITY AND STABILITY IN GRAPHS;415
20.5;4. APPLICATIONS TO STABILITY IN GRAPHS;422
20.6;REFERENCES;424
21;CHAPTER 15. ON THE EXISTENCE OF FAST APPROXIMATION
SCHEMES;426
21.1;ABSTRACT;426
21.2;INTRODUCTION;427
21.3;NOTATION AND DEFINITIONS;428
21.4;EXISTENCE OF FULLY POLYNOMIAL APPROXIMATION SCHEMES;432
21.5;POLYNOMIAL APPROXIMATION SCHEMES;439
21.6;CONCLUSION;446
21.7;REFERENCES;447
22;CHAPTER 16. POLYNOMIALLY BOUNDED ELLIPSOID ALGORITHMS FOR
CONVEX QUADRATIC PROGRAMMING;450
22.1;ABSTRACT;450
22.2;1. INTRODUCTION;451
22.3;2. THE NEAREST POINT PROBLEM;454
22.4;3. LCPs ASSOCIATED WITH PD MATRICES;474
22.5;4. LCPs ASSOCIATED WITH PSD MATRICES;483
22.6;5. OTHER LCPs;490
22.7;ACKNOWLEDGMENTS;493
22.8;REFERENCES;494
23;CHAPTER
17. THE IMPLICIT COMPLEMENTARITY PROBLEM;498
23.1;ABSTRACT;498
23.2;1. INTRODUCTION;499
23.3;2. PRELIMINARY DISCUSSION;502
23.4;3. EXISTENCE AND UNIQUENESS;508
23.5;4. MONOTONE ITERATES;522
23.6;REFERENCES;527
24;CHAPTER 18. METHODS FOR EVALUATING NONLINEAR
PROGRAMMING SOFTWARE;530
24.1;ABSTRACT;530
24.2;1. INTRODUCTION;531
24.3;2. BATTERY TESTING;537
24.4;3. RANDOM TESTING;543
24.5;4. SINGLE PARAMETER TESTING;548
24.6;5. CONCLUSIONS;557
24.7;REFERENCES;558
25;SUBJECT INDEX;560