Quadratically and superlinearly convergent algorithms for the solution of inequality constrained minimization problems
Tóm tắt
In this paper, some Newton and quasi-Newton algorithms for the solution of inequality constrained minimization problems are considered. All the algorithms described produce sequences {x
k
} convergingq-superlinearly to the solution. Furthermore, under mild assumptions, aq-quadratic convergence rate inx 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.
Tài liệu tham khảo
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.
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.
Gabay, D.,Reduced Quasi-Newton Methods with Feasibility Improvement for Nonlinearly Constrained Optimization, Mathematical Programming Study, Vol. 16, pp. 18–44, 1982.
Wilson, R. B.,A Simplicial Algorithm for Concave Programming, Harvard University, Graduate School of Business Administration, PhD Thesis, 1963.
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.
Han, S. P.,Superlinearly Convergent Variable Metric Algorithm for General Nonlinear Programming Problems, Mathematical Programming, Vol. 11, pp. 263–282, 1976.
Bertsekas, D. P.,Constrained Optimization and Lagrange Multiplier Methods, Academic Press, New York, New York, 1982.
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.
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.
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.
Glad, T.,Properties of Updating Methods for Multipliers in Augmented Lagrangians, Journal of Optimization Theory and Applications, Vol. 28, pp. 135–156, 1977.
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.
Han, S. P.,Dual Variable Metric Algorithms for Constrained Optimization, SIAM Journal on Control and Optimization, Vol. 15, pp. 546–565, 1977.
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.
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.
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.
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.
Nocedal, J., andOverton, M.,Projected Hessian Updating Algorithms for Nonlinearly Constrained Optimization, SIAM Journal on Numerical Analysis, Vol. 22, pp. 821–850, 1983.
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.
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.
Bartholomew-Biggs, M. C.,Recursive Quadratic Programming Based on the Augmented Lagrangian, Mathematical Programming Study, Vol. 31, pp. 21–41, 1987.
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.
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.
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.
Kanzow, C.,Newton-Type Methods for Nonlinearly Constrained Optimization, Universitat Hamburg, Institute fur Angewandte Mathematik, Report No. 62, 1992.
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.
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.
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.
Facchinei, F., andLucidi, S.,A Globalization Technique for Constrained Newton-Like Algorithms, Università di Roma-La Sapienza, Report, 1994.
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.
Glad, T., andPolak, E.,A Multiplier Method with Automatic Limitation of Penalty Growth, Mathematical Programming, Vol. 17, pp. 140–155, 1979.
Lucidi, S.,New Results on a Continuously Differentiable Exact Penalty Function, SIAM Journal on Optimization, Vol. 2, pp. 558–574, 1992.
Hestenes, M. R.,Optimization Theory: The Finite-Dimensional Case, Wiley, New York, New York, 1975.
Bellman, R.,Introduction to Matrix Analysis, McGraw-Hill, New York, New York, 1970.
Facchinei, F., andLucidi, S.,A Class of Penalty Functions for Optimization Problems with Bound Constraints, Optimization, Vol. 26, pp. 239–259, 1992.