×

zbMATH — the first resource for mathematics

Quadratically and superlinearly convergent algorithms for the solution of inequality constrained minimization problems. (English) Zbl 0830.90125
Some Newton and quasi-Newton algorithms for the solution of inequality constrained minimization problems are considered. All the algorithms described produce sequences \(\{x_k\}\) converging \(q\)-superlinearly to the solution. Furthermore, under mild assumptions, a \(q\)-quadratic convergence rate in \(x\) is also attained. Other features of these algorithms are that only the solution of linear systems of equations is required at each iteration and that the strict complementarity assumption is never invoked. First, the superlinear or quadratic convergence rate of a Newton-like algorithm is proved. Then, a simpler version of this algorithm is studied, and it is shown that it is superlinearly convergent. Finally, quasi-Newton versions of the previous algorithms are considered and, provided the sequence defined by the algorithms converges, a characterization of superlinear convergence extending the result of Boggs, Tolle, and Wang is given.
Reviewer: F.Facchinei (Roma)

MSC:
90C30 Nonlinear programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Robinson, S. M.,Generalized Equations, Mathematical Programming: The State of the Art, Edited by A. Bachem, M. Grotschel, and B. Korte, Springer Verlag, Berlin, Germany, pp. 346–367, 1983.
[2] Schönefeld, K. A Superlinearly and Globally Convergent Optimization Method Independent of Strict Complementarity Slackness, Technische Universitat Dresden, Sektion Mathematik, Report No. 07-16-90, 1990.
[3] Gabay, D.,Reduced Quasi-Newton Methods with Feasibility Improvement for Nonlinearly Constrained Optimization, Mathematical Programming Study, Vol. 16, pp. 18–44, 1982. · Zbl 0477.90065 · doi:10.1007/BFb0120946
[4] Wilson, R. B.,A Simplicial Algorithm for Concave Programming, Harvard University, Graduate School of Business Administration, PhD Thesis, 1963.
[5] Robinson, S. M.,Perturbed Kuhn-Tucker Points and Rates of Convergence for a Class of Nonlinear Programming Algorithms, Mathematical Programming, Vol. 7, pp. 1–16, 1974. · Zbl 0294.90078 · doi:10.1007/BF01585500
[6] Han, S. P.,Superlinearly Convergent Variable Metric Algorithm for General Nonlinear Programming Problems, Mathematical Programming, Vol. 11, pp. 263–282, 1976. · Zbl 0364.90097 · doi:10.1007/BF01580395
[7] Bertsekas, D. P.,Constrained Optimization and Lagrange Multiplier Methods, Academic Press, New York, New York, 1982. · Zbl 0572.90067
[8] Bonnans, J. F.,Rates of Convergence of Newton Type Methods for Variational Inequalities and Nonlinear Programming, Applied Mathematics and Optimization, Vol. 29, pp. 161–186, 1994. · Zbl 0809.90115 · doi:10.1007/BF01204181
[9] Bonnans, J. F.,Local Study of Newton-Type Algorithms for Constrained Problems, Optimization, Edited by S. Dolecki, Springer Verlag, Berlin, Germany, pp. 13–24, 1989. · Zbl 0693.49016
[10] Tapia, R. A.,Diagonalized Multiplier Methods and Quasi-Newton Methods for Constrained Optimization, Journal of Optimization Theory and Applications, Vol. 22, pp. 135–194, 1977. · Zbl 0336.65034 · doi:10.1007/BF00933161
[11] Glad, T.,Properties of Updating Methods for Multipliers in Augmented Lagrangians, Journal of Optimization Theory and Applications, Vol. 28, pp. 135–156, 1977. · Zbl 0403.90070 · doi:10.1007/BF00933239
[12] Garcia Palomares, U. M., andMangasarian, O. L.,Superlinearly Convergent Quasi-Newton Algorithms for Nonlinearly Constrained Optimization Problems, Mathematical Programming, Vol. 11, pp. 1–13, 1976. · Zbl 0362.90103 · doi:10.1007/BF01580366
[13] Han, S. P.,Dual Variable Metric Algorithms for Constrained Optimization, SIAM Journal on Control and Optimization, Vol. 15, pp. 546–565, 1977. · Zbl 0361.90074 · doi:10.1137/0315037
[14] Powell, M. J. D.,The Convergence of Variable Metric Methods for Nonlinear Constrained Optimization Calculations, Nonlinear Programming 3, Edited by O. L. Mangasarian, R. R. Meyer, and S. M. Robinson, Academic Press, New York, New York, pp. 27–63, 1978.
[15] Boggs, P. T., Tolle, J. W., andWang, P.,On the Local Convergence of Quasi-Newton Methods for Constrained Optimization, SIAM Journal on Control and Optimization, Vol. 20, pp. 161–171, 1982. · Zbl 0494.65036 · doi:10.1137/0320014
[16] Dennis, J. E., andMoré, J. J.,A Characterization of Superlinear Convergence and Its Application to Quasi-Newton Methods, Mathematics of Computation, Vol. 28, pp. 549–560, 1974. · Zbl 0282.65042 · doi:10.1090/S0025-5718-1974-0343581-1
[17] Fontecilla, R., Steihaug, T., andTapia, R. A.,A Convergence Theory for a Class of Quasi-Newton Methods for Constrained Optimizations, SIAM Journal on Numerical Analysis, Vol. 24, pp. 1133–1151, 1987. · Zbl 0634.65045 · doi:10.1137/0724075
[18] Nocedal, J., andOverton, M.,Projected Hessian Updating Algorithms for Nonlinearly Constrained Optimization, SIAM Journal on Numerical Analysis, Vol. 22, pp. 821–850, 1983. · Zbl 0593.65043 · doi:10.1137/0722050
[19] Stoer, J., andTapia, A.,On the Characterization of q-Superlinear Convergence of Quasi-Newton Methods for Constrained Optimization, Mathematics of Computation, Vol. 49, pp. 581–584, 1987. · Zbl 0632.90052
[20] Biggs, M. C.,On the Convergence of Some Constrained Minimization Algorithms Based on Recursive Quadratic Programming, Journal of the Institute of Mathematics and Its Applications, Vol. 21, pp. 67–82, 1978. · Zbl 0373.90056 · doi:10.1093/imamat/21.1.67
[21] Bartholomew-Biggs, M. C.,Recursive Quadratic Programming Based on the Augmented Lagrangian, Mathematical Programming Study, Vol. 31, pp. 21–41, 1987. · Zbl 0636.90079
[22] Di Pillo, G., andGrippo, L.,A Class of Continuously Differentiable Exact Penalty Function Algorithms for Nonlinear Programming Problems, System Modelling and Optimization, Edited by P. Toft-Christensen, Springer Verlag, Berlin, Germany, pp. 246–256, 1984.
[23] Kleinmichel, H., Richter, C., andSchönefeld, K.,On a Class of Hybrid Methods for Smooth Constrained Optimization, Journal of Optimization Theory and Applications, Vol. 73 pp. 465–499, 1992. · Zbl 0794.90064 · doi:10.1007/BF00940052
[24] Di Pillo, G., Grippo, L., andLucidi, S.,Globally Convergent Exact Penalty Algorithms for Constrained Optimization, System Modelling and Optimization, Edited by A. Prekopa, J. Szelezsan, and B. Strazicky, Springer Verlag, Berlin, Germany, pp. 694–703, 1986. · Zbl 0679.90068
[25] Kanzow, C.,Newton-Type Methods for Nonlinearly Constrained Optimization, Universitat Hamburg, Institute fur Angewandte Mathematik, Report No. 62, 1992.
[26] Kanzow, C. andKleinmichel, H.,A Class of Newton-Type Methods for Equality and Inequality Constrained Optimization, Universitat Hamburg, Institut fur Angewandte Mathematik, Report No. 61, 1992.
[27] Pang, J. S.,A B-Differentiable Equation-Based, Globally and Locally Quadratically Convergent Algorithm for Nonlinear Programs, Complementarity, and Variational Inequality Problems, Mathematical Programming, Vol. 51, pp. 101–131, 1991. · Zbl 0733.90063 · doi:10.1007/BF01586928
[28] Facchinei, F., andLucidi, S.,Local Properties of a Newton-Like Direction for Equality Constrained Minimization Problems, Optimization Methods and Software, Vol. 3, pp. 13–26, 1994. · doi:10.1080/10556789408805553
[29] Facchinei, F., andLucidi, S.,A Globalization Technique for Constrained Newton-Like Algorithms, Università di Roma-La Sapienza, Report, 1994.
[30] Fletcher, R.,A Class of Methods for Nonlinear Programming with Termination and Convergence Properties, Integer and Nonlinear Programming, Edited by J. Abadie, North-Holland, Amsterdam, Holland, pp. 157–173, 1970. · Zbl 0332.90039
[31] Glad, T., andPolak, E.,A Multiplier Method with Automatic Limitation of Penalty Growth, Mathematical Programming, Vol. 17, pp. 140–155, 1979. · Zbl 0414.90078 · doi:10.1007/BF01588240
[32] Lucidi, S.,New Results on a Continuously Differentiable Exact Penalty Function, SIAM Journal on Optimization, Vol. 2, pp. 558–574, 1992. · Zbl 0761.90089 · doi:10.1137/0802027
[33] Hestenes, M. R.,Optimization Theory: The Finite-Dimensional Case, Wiley, New York, New York, 1975. · Zbl 0327.90015
[34] Bellman, R.,Introduction to Matrix Analysis, McGraw-Hill, New York, New York, 1970. · Zbl 0216.06101
[35] Facchinei, F., andLucidi, S.,A Class of Penalty Functions for Optimization Problems with Bound Constraints, Optimization, Vol. 26, pp. 239–259, 1992. · Zbl 0817.90106 · doi:10.1080/02331939208843855
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.