Convergence of a projected gradient method variant for quasiconvex objectives. (English) Zbl 1198.90356
Summary: We present a version of the projected gradient method for solving constrained minimization problems with a competitive search strategy: an appropriate step size rule through an Armijo search along the feasible direction, thereby obtaining global convergence properties when the objective function is quasiconvex or pseudoconvex. In contrast to other similar step size rules, this one requires only one projection onto the feasible set per iteration, rather than one projection for each tentative step during the search for the step size, which represents a considerable saving when the projections are computationally expensive.
Keywords:
Armijo searchReferences:
| [1] | Goldstein, A. A., Convex programming in Hilbert space, Bulletin of the American Mathematical Society, 70, 709-710 (1964) · Zbl 0142.17101 |
| [2] | Levitin, E. S.; Polyak, B. T., Constrained minimization methods, Zhurnal Vychislitelńo iˇ Matematiki i Matematichesko iˇ Fiziki, 6, 787-823 (1966) · Zbl 0184.38902 |
| [3] | Bertsekas, D., On the Goldstein-Levitin-Polyak gradient projection method, IEEE Transactions on Automatic Control, 21, 174-184 (1976) · Zbl 0326.49025 |
| [4] | Iusem, A. N., On the convergence properties of the projected gradient method for convex optimization, Computational and Applied Mathematics, 22, 37-52 (2003) · Zbl 1213.90197 |
| [5] | Mangasarian, O. L., Nonlinear Programming (1969), McGraw-Hill: McGraw-Hill New York · Zbl 0194.20201 |
| [6] | Boyd, S.; Vandenberghe, L., Convex Optimization (2007), Cambridge University Press: Cambridge University Press New York |
| [7] | Burachik, R.; Graña Drummond, L. M.; Iusem, A. N.; Svaiter, B. F., Full convergence of the steepest descent method with inexact line searches, Optimization, 32, 137-146 (1995) · Zbl 0821.90089 |
| [8] | Bertsekas, D., Nonlinear Programming (1995), Athena Scientific: Athena Scientific Belmont · Zbl 0935.90037 |
| [9] | E.N. Gafni, D. Bertsekas, Convergence of a gradient projection method, Technical Report LIDS-P-1201, Laboratory for Information and Decision Systems, MIT. (1982).; E.N. Gafni, D. Bertsekas, Convergence of a gradient projection method, Technical Report LIDS-P-1201, Laboratory for Information and Decision Systems, MIT. (1982). |
| [10] | Alber, Ya. I.; Iusem, A. N.; Solodov, M. V., On the projected subgradient method for nonsmooth convex optimization in a Hilbert space, Mathematical Programming, 81, 23-37 (1998) · Zbl 0919.90122 |
| [11] | Alber, Ya. I.; Iusem, A. N., Extension of subgradient techniques for nonsmooth optimization in Banach spaces, Set-Valued Analysis, 9, 315-335 (2001) · Zbl 1049.90123 |
| [12] | Bello Cruz, J. Y.; Iusem, A. N., Convergence of direct methods for paramonotone variational inequalities, Computational Optimization and Applications, 46, 247-263 (2010) · Zbl 1220.90129 |
| [13] | Calamai, P. H.; Moré, J. J., Projected gradient methods for linearly constrained problems, Mathematical Programming, 39, 93-116 (1987) · Zbl 0634.90064 |
| [14] | Wang, C.; Xiu, N., Convergence of the gradient projection method for generalized convex minimization, Computational Optimization and Applications, 16, 111-120 (2000) · Zbl 0963.90058 |
| [15] | Cheng, Y. C., On the gradient-projection method for solving the nonsymmetric linear complementary problem, Journal of Optimization Theory and Applications, 43, 527-541 (1984) · Zbl 0517.90083 |
| [16] | Kiwiel, K. C.; Murty, K., Convergence of the steepest descent method for minimizing quasiconvex functions, Journal of Optimization Theory and Applications, 89, 221-226 (1996) · Zbl 0866.90094 |
| [17] | C.C. Chou, K.F. Ng, J.S. Pang, Minimizing and stationary sequences of optimization problems, Technical Reports, The Johns Hopkins University, Baltimore, Maryland, USA (1996).; C.C. Chou, K.F. Ng, J.S. Pang, Minimizing and stationary sequences of optimization problems, Technical Reports, The Johns Hopkins University, Baltimore, Maryland, USA (1996). · Zbl 0909.90235 |
| [18] | Wang, C. Y., Convergence characterization of both new pivot method and simplified Levitin-Polyak gradient projection method, Acta Mathematicae Applicatae Sinica, 4, 37-52 (1981) · Zbl 0485.65045 |
| [19] | C.Y. Wang, On convergence properties of an improved reduced gradient method, Ke Xue Tongbao, 17, 1030-1033.; C.Y. Wang, On convergence properties of an improved reduced gradient method, Ke Xue Tongbao, 17, 1030-1033. · Zbl 1092.93526 |
| [20] | Wu, F.; Wu, S., A modified Frank-Wolfe algorithm and its convergence properties, Acta Mathematicae Applicatae Sinica, 11, 286-291 (1995) · Zbl 0847.90130 |
| [21] | Xue, G. L., A family of gradient projection algorithm and their convergence properties, Acta Mathematicae Applicatae Sinica, 10, 396-404 (1987) · Zbl 0639.90083 |
| [22] | Xue, G. L., On convergence properties of a Least-Distance programming procedure for minimization problems under linear constraints, Journal of Optimization Theory and Applications, 50, 365-370 (1986) · Zbl 0577.90069 |
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.
