×

Convergence analysis of perturbed feasible descent methods. (English) Zbl 0899.90149

Summary: We develop a general approach to convergence analysis of feasible descent methods in the presence of perturbations. The important novel feature of our analysis is that perturbations need not tend to zero in the limit. In that case, standard convergence analysis techniques are not applicable. Therefore, a new approach is needed. We show that, in the presence of perturbations, a certain \(\varepsilon\)-approximate solution can be obtained, where \(\varepsilon\) depends linearly on the level of perturbations. Applications to the gradient projection, proximal minimization, extragradient and incremental gradient algorithms are described.

MSC:

90C30 Nonlinear programming
65K05 Numerical mathematical programming methods
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Luo, Z. Q., and Tseng, P., Error Bounds and Convergence Analysis of Feasible Descent Methods: A General Approach, Annals of Operations Research, Vol. 46, pp. 157–178, 1993. · Zbl 0793.90076 · doi:10.1007/BF02096261
[2] Goldstein, A. A., Convex Programming in Hilbert Space, Bulletin of the American Mathematical Society, Vol. 70, pp. 709–710, 1964. · Zbl 0142.17101 · doi:10.1090/S0002-9904-1964-11178-2
[3] Levitin, E. S., and Polyak, B. T., Constrained Minimization Methods, USSR Computational Mathematics and Mathematical Physics, Vol. 6, pp. 1–50, 1965. · doi:10.1016/0041-5553(66)90114-5
[4] Martinet, B., Regularisation d’Inéquations Variationelles per Approximations Successives, RAIRO-Operations Research, Vol. 4, pp. 154–159, 1970.
[5] Rockafellar, R. T., Monotone Operators and the Proximal Point Algorithm, SIAM Journal on Control and Optimization, Vol. 14, pp. 877–898, 1976. · Zbl 0358.90053 · doi:10.1137/0314056
[6] Korpelevich, G. M., The Extragradient Method for Finding Saddle Points and Other Problems, Matecon, Vol. 12, pp. 747–756, 1976. · Zbl 0342.90044
[7] Marcotte, P., Application of Khobotov’s Algorithm to Variational Inequalities and Network Equilibrium Problems, Information Systems and Operational Research, Vol. 29, pp. 258–270, 1991. · Zbl 0781.90086 · doi:10.1080/03155986.1991.11732174
[8] Solodov, M. V., Incremental Gradient Algorithms with Stepsizes Bounded Away from Zero, Technical Report B-096, Instituto de Matematica Pura e Aplicada, Jardim Botanico, Rio de Janeiro, Brazil, 1995. · Zbl 0915.65061
[9] Mangasarian, O. L., Convergence of Iterates of an Inexact Matrix Splitting Algorithm for the Symmetric Monotone Linear Complementarity Problem, SIAM Journal on Optimization, Vol. 1, pp. 114–122, 1991. · Zbl 0777.90070 · doi:10.1137/0801009
[10] Luo, Z. Q., and Tseng, P., Error Bound and Convergence Analysis of Matrix Splitting Algorithms for the Affine Variational Inequality Problem, SIAM Journal on Optimization, Vol. 2, pp. 43–54, 1992. · Zbl 0777.49010 · doi:10.1137/0802004
[11] Li, W., Remarks on Matrix Splitting Algorithms for Symmetric Linear Complementarity Problems, SIAM Journal on Optimization, Vol. 3, pp. 155–163, 1993. · Zbl 0786.90074 · doi:10.1137/0803008
[12] Solodov, M. V., New Inexact Parallel Variable Distribution Algorithms, Computational Optimization and Applications, (to appear). · Zbl 0884.90138
[13] Dembo, R. S., Eisenstat, S. C., and Steihaug, T., Inexact Newton Methods, SIAM Journal on Numerical Analysis, Vol. 19, pp. 400–408, 1982. · Zbl 0478.65030 · doi:10.1137/0719025
[14] Polyak, B. T., Introduction to Optimization. Optimization Software, Publications Division, New York, New York, 1987.
[15] Polak, E., Computational Methods in Optimization: A Unified Approach, Academic Press, New York, New York, 1971. · Zbl 0301.90040
[16] Boggs, P. T., and Dennis, J. E., A Stability Analysis for Perturbed Nonlinear Iterative Methods, Mathematics of Computation, Vol. 30, pp. 199–215, 1976. · Zbl 0337.65032 · doi:10.1090/S0025-5718-1976-0395209-4
[17] Mangasarian, O. L., and Solodov, M. V., Serial and Parallel Backpropagation Convergence via Nonmonotone Perturbed Minimization, Optimization Methods and Software, Vol. 4, pp. 103–116, 1994. · doi:10.1080/10556789408805581
[18] Mangasarian, O. L., and Solodov, M. V., Backpropagation Convergence via Deterministic Nonmonotone Perturbed Minimization, Neural Information Processing Systems, Edited by G. Tesauro, J. D. Cowan, and J. Alspector, Morgan Kaufmann Publishers, San Francisco, California, Vol. 6, pp. 383–390, 1994.
[19] Zavriev, S. K., Convergence Properties of the Gradient Method under Variable Level Interference, USSR Computational Mathematics and Mathematical Physics, Vol. 30, pp. 997–1007, 1990. · Zbl 0738.90075 · doi:10.1016/0041-5553(90)90040-Y
[20] Solodov, M. V., and Zavriev, S. K., Error-Stability Properties of Generalized Gradient-Type Algorithms, Mathematical Programming Technical Report 94-05, Computer Science Department, University of Wisconsin, Madison, Wisconsin, 1994 (Revised 1995). · Zbl 0913.90245
[21] Luo, Z. Q., and Tseng, P., Analysis of an Approximate Gradient Projection Method with Applications to the Backpropagation Algorithm, Optimization Methods and Software, Vol. 4, pp. 85–101, 1994. · doi:10.1080/10556789408805580
[22] Mangasarian, O. L., Nonlinear Programming, McGraw-Hill, New York, New York, 1969.
[23] Robinson, S. M., Some Continuity Properties of Polyhedral Multifunctions, Mathematical Programming Study, Vol. 14, pp. 206–214, 1981. · Zbl 0449.90090 · doi:10.1007/BFb0120929
[24] Luo, Z. Q., Mangasarian, O. L., Ren, J., and Solodov, M. V., New Error Bounds for the Linear Complementarity Problem, Mathematics of Operations Research, Vol. 19, pp. 880–892, 1994. · Zbl 0833.90113 · doi:10.1287/moor.19.4.880
[25] Pang, J. S., A Posteriori Error Bounds for the Linearly-Constrained Variational Inequality Problem, Mathematics of Operations Research, Vol. 12, pp. 474–484, 1987. · doi:10.1287/moor.12.3.474
[26] Luo, X. D., and Tseng, P., On Global Projection-Type Error Bound for the Linear Complementarity Problem, Linear Algebra and Its Applications, (to appear). · Zbl 0872.90099
[27] Zangwill, W. I., Nonlinear Programming: A Unified Approach, Prentice-Hall, Englewood Cliffs, New Jersey, 1969. · Zbl 0195.20804
[28] Gafni, E. M., and Bertsekas, D. P., Two-Metric Projection Methods for Constrained Optimization, SIAM Journal on Control and Optimization, Vol. 22, pp. 936–964, 1984. · Zbl 0555.90086 · doi:10.1137/0322061
[29] Rockafellar, R. T., Convex Analysis, Princeton University Press, Princeton, New Jersey, 1970. · Zbl 0193.18401
[30] Mangasarian, O. L., Mathematical Programming in Neural Networks, ORSA Journal on Computing, Vol. 5, pp. 349–360, 1993. · Zbl 0789.90053 · doi:10.1287/ijoc.5.4.349
[31] Bertsekas, D. P., Incremental Least Squares Methods and the Extended Kalman Filter, SIAM Journal on Optimization, Vol. 6, pp. 807–822, 1996. · Zbl 0945.93026 · doi:10.1137/S1052623494268522
[32] Bertsekas, D. P., A New Class of Incremental Gradient Methods for Least Squares Problems, Report, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, Massachusetts, 1995.
[33] Luo, Z. Q., On the Convergence of the LMS Algorithm with Adaptive Learning Rate for Linear Feedforward Networks, Neural Computation, Vol. 3, pp. 226–245, 1991. · doi:10.1162/neco.1991.3.2.226
[34] Tseng, P., Incremental Gradient(-Projection) Method with Momentum Term and Adaptive Stepsize Rule, Report, Department of Mathematics, University of Washington, Seattle, Washington, 1995. · Zbl 0922.90131
[35] Solodov, M. V., and Tseng, P., Modified Projection-Type Methods for Monotone Variational Inequalities, SIAM Journal on Control and Optimization, Vol. 34,No. 5, 1996. · Zbl 0866.49018
[36] Tseng, P., On Linear Convergence of Iterative Methods for the Variational Inequality Problem, Journal of Computational and Applied Mathematics, Vol. 60, pp. 237–252, 1995. · Zbl 0835.65087 · doi:10.1016/0377-0427(94)00094-H
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.