A convergence theorem of Rosen’s gradient projection method.(English)Zbl 0626.90077
This paper offers a convergence theorem for Rosen’s gradient projection method. Since the method was published in 1960 a rigorous convergence proof has remained an open question.
For f(x)\(\to \max\), \(A^ tx\geq b\) let \(J(x)=\{f:\) \(a^ T_ jx=b_ j\}\), \(J^ k=J(x^ k)\), \(P_{Jk}=I-A_{Jk}(A^ T_{Jk}A_{Jk})^{-1}A^ T_{Jk}\), \(u^ k_ h=\max \{(A^ T_{Jk}A_{Jk})^{-1}A^ T_{Jk}f'(x^ k)_{(j)}| j\in J^ k\}.\)
In Rosen’s method at step k we choose \[ d^ k=\{P_{Jk}f(x^ k)\;if\;\| P_{Jk}f(x^ k)\| >cu^ k_ h,\quad d^ k=P_{J^ k\setminus \{h\}}f(x^ k)\quad else \] and use a line search process to find a new point \(x^{k+1}=x^ k+\lambda^ kd^ k\). In the paper conditions for the constant c are given that guarantee global convergence. The authors believe that the algorithm will be convergent for any \(c>0\).
For f(x)\(\to \max\), \(A^ tx\geq b\) let \(J(x)=\{f:\) \(a^ T_ jx=b_ j\}\), \(J^ k=J(x^ k)\), \(P_{Jk}=I-A_{Jk}(A^ T_{Jk}A_{Jk})^{-1}A^ T_{Jk}\), \(u^ k_ h=\max \{(A^ T_{Jk}A_{Jk})^{-1}A^ T_{Jk}f'(x^ k)_{(j)}| j\in J^ k\}.\)
In Rosen’s method at step k we choose \[ d^ k=\{P_{Jk}f(x^ k)\;if\;\| P_{Jk}f(x^ k)\| >cu^ k_ h,\quad d^ k=P_{J^ k\setminus \{h\}}f(x^ k)\quad else \] and use a line search process to find a new point \(x^{k+1}=x^ k+\lambda^ kd^ k\). In the paper conditions for the constant c are given that guarantee global convergence. The authors believe that the algorithm will be convergent for any \(c>0\).
Reviewer: E.Iwanow
MSC:
| 90C30 | Nonlinear programming |
| 49M37 | Numerical methods based on nonlinear programming |
| 65K05 | Numerical mathematical programming methods |
Cite
Full Text:DOI
References:
| [1] | M. Avriel,Nonlinear Programming: Analysis and Methods (Prentice-Hall, Englewood Cliffs, N.J., 1976). |
| [2] | M.S. Bazaraa and C.M. Shetty,Nonlinear Programming: Theory and Algorithms (John Wiley & Sons, New York, 1979). ·Zbl 0476.90035 |
| [3] | J. Denel, ”Extensions of the continuity of point-to-set maps: applications to fixed point algorithms,”Mathematical Programming Study 10 (1979) 48–68. ·Zbl 0414.90072 |
| [4] | D.-Z. Du, ”A modification of Rosen-Polak’s algorithm,”Kexue Tonbao 28 (1983) 301–305. ·Zbl 0525.90081 |
| [5] | C. Goffmand and C. Pedrick, First Course in Functional Analysis (Prentice-Hall, Englewood Cliffs, N.J., 1965). ·Zbl 0122.11206 |
| [6] | D. Goldfarb, ”Extension of Davidson’s variable metric method to maximization under linear equality and equality constraints,”SIAM Journal on Applied Mathematics 17 (1969) 739–764. ·Zbl 0185.42602 ·doi:10.1137/0117067 |
| [7] | D. Goldfarb and L. Lapidus, ”Conjugate gradient method for nonlinear programming problems with linear constraints,”Industrial and Engineering Chemistry Fundamentals 7 (1968) 142–151. ·doi:10.1021/i160025a024 |
| [8] | P. Huard, ”Optimization algorithms and point-to-set maps,”Mathematical Programming 8 (1975) 308–331. ·Zbl 0312.90052 ·doi:10.1007/BF01580449 |
| [9] | D.G. Luenberger, Introduction to Linear and Nonlinear Programming (Addison-Wesley, Reading, Mass., 1973). ·Zbl 0297.90044 |
| [10] | R.R. Meyer, ”The validity of a family of optimization methods,”SIAM Journal on Control and Optimization 8 (1970) 41–54. ·Zbl 0194.20501 ·doi:10.1137/0308003 |
| [11] | R.R. Meyer ”Sufficient conditions for the convergence of monotonic mathematical programming algorithms,”Journal of Computer and System Sciences 12 (1976) 108–121. ·Zbl 0337.65037 ·doi:10.1016/S0022-0000(76)80021-9 |
| [12] | B.A. Murtagh and R.W.H. Sargent, ”A constrained minimization method with quadratic convergence,” in R. Fletcher, ed.,Optimization (Academic Press, New York, 1969) 215–246. ·Zbl 0214.42401 |
| [13] | E. Palak, ”On the convergence of optimization algorithms,” Revue Francaise d’Informatique et de Recherche Operationelle 3 (1969) 17–34. |
| [14] | E. Polak,Computational Methods in Optimization (Academic Press, New York, 1971). ·Zbl 0257.90055 |
| [15] | J.B. Rosen, ”The gradient projection method for nonlinear programming, Part 1: linear constraints,”SIAM Journal on Applied Mathematics 8 (1960) 181–217. ·Zbl 0099.36405 ·doi:10.1137/0108011 |
| [16] | J.B. Rosen, ”The gradient projection method for nonlinear programming, Part 2: nonlinear constraints,”SIAM Journal on Applied Mathematics 9 (1961) 514–553. ·Zbl 0231.90048 ·doi:10.1137/0109044 |
| [17] | W.I. Zangwill, ”Convergence conditions for nonlinear programming algorithms,”Management Science 16 (1969) 1–13. ·Zbl 0191.49101 ·doi:10.1287/mnsc.16.1.1 |
| [18] | W.I. Zangwill,Nonlinear Programming: A Unified Approach (Prentice-Hall, Englewood Cliffs, N.J., 1969). |
| [19] | X.-S. Zhang, ”An improved Rosen-Polak method,”Acta Mathematicae Applacatae Sinica 2 (1979) 257–267 (in Chinese). |
| [20] | X.-S. Zhang, ”Discussion on Polak’s algorithm of nonlinear programming,”Acta Mathematicae Applacatae Sinica 4 (1981) 1–13 (in Chinese). ·Zbl 0485.90077 |
| [21] | X.-S. Zhang, ”On the convergence of Rosen’s gradient projection method: Three-dimensional case,”Acta Mathematicae Applacatae Sinica 8 (1985) (in Chinese). |
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.
