×

A derivative-based bracketing scheme for univariate minimization and the conjugate gradient method. (English) Zbl 0684.65063

The author develops a derivative-based univariate minimization algorithm which combines a bracketing strategy, the bisection method and Hermite cubic interpolation. It is proved that the proposed algorithm achieves quadratic convergence using one function and one derivative evaluation each iteration. Also the author proposes an efficient conjugate gradient search scheme which incorporate the derivative-based univariate algorithm. Some experimental results are presented.
Reviewer: F.Luban

MSC:

65K05 Numerical mathematical programming methods
90C30 Nonlinear programming

Software:

BRENT; NAPACK
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Pierre, D. A., Optimization Theory with Applications (1969), Wiley: Wiley New York · Zbl 0205.15503
[2] Walsh, G. R., Methods of Optimization (1975), Wiley: Wiley London · Zbl 0313.90051
[3] Mifflin, R., Stationarity and superlinear convergence of an algorithm for univariate locally Lipschitz constrained minimization, Math. Program., 28, 50-71 (1984) · Zbl 0528.49024
[4] Dennis, J. E.; Schnabel, R. B., Numerical Methods for Unconstrained Optimization and Nonlinear Equations (1983), Prentice-Hall: Prentice-Hall Englewood Cliffs, N.J · Zbl 0579.65058
[5] Al-Baali, M.; Fletcher, R., An efficient line search for nonlinear least squares, J. Optim. Theory Applic., 48, 359-377 (1986) · Zbl 0562.90074
[6] Gill, P. E.; Murray, W., Safeguarded steplength algorithms for optimization using descent methods, (Report NAC 37 (1974), National Physics Laboratory: National Physics Laboratory Teddington, England)
[7] N. Ghosh and W. W. Hager, A derivative-free bracketing scheme for univariate minimization.; N. Ghosh and W. W. Hager, A derivative-free bracketing scheme for univariate minimization. · Zbl 0705.65040
[8] Luenberger, D. G., Introduction to Linear and Nonlinear Programming (1984), Addison-Wesley: Addison-Wesley Reading, Mass · Zbl 0241.90052
[9] Moré, J. J.; Sorensen, D. C., Newton’s method, (Research Report 82-8 (1982), Argonne National Laboratory: Argonne National Laboratory Argonne, Ill) · Zbl 0608.65037
[10] Davidon, W. C., Variable metric method for minimization, (Research Report 5990 (1959), Argonne National Laboratory: Argonne National Laboratory Lemont, Ill) · Zbl 0204.49602
[11] Dahlquist, G.; Björck, A., Numerical Methods (1974), Prentice-Hall: Prentice-Hall Englewood Cliffs, N.J, (Translated by N. Anderson)
[12] Brent, R. P., Algorithms for Minimization without Derivatives (1973), Prentice-Hall: Prentice-Hall Englewood Cliffs, N.J · Zbl 0245.65032
[13] Isaacson, E.; Keller, H. B., Analysis of Numerical Methods (1966), Wiley: Wiley New York · Zbl 0168.13101
[14] Tamir, A., Rates of convergence of a one-dimensional search based on interpolating polynomials, J. Optim. Theory Applic., 27, 187-203 (1979) · Zbl 0373.90063
[15] Ortega, J. M.; Rheinboldt, W. C., Iterative Solution of Nonlinear Equations in Several Variables (1970), Academic Press: Academic Press New York · Zbl 0241.65046
[16] Cohen, A., Rate of convergence for root finding and optimization algorithms, University of California at Berkeley, Ph.D. Thesis (1970)
[17] Daniel, J. W., The conjugate gradient method for linear and nonlinear operator equations, SIAM J. numer. Analysis, 4, 10-26 (1967) · Zbl 0154.40302
[18] Daniel, J. W., Convergence of the conjugate gradient method with computationally convinient modifications, Numer. Math., 10, 125-131 (1967) · Zbl 0178.18302
[19] Daniel, J. W., A correction concerning the convergence rate for the conjugate gradient method, SIAM J. numer. Analysis, 7, 277-280 (1970) · Zbl 0204.48001
[20] Klessig, R.; Polak, E., Efficient implementations of the Polak-Ribiere conjugate gradient algorithm, SIAM J. Control, 10, 524-549 (1972) · Zbl 0244.90034
[21] Lenard, M. L., Practical convergence conditions for unconstrained minimization, Math. Program., 4, 309-323 (1973) · Zbl 0268.90059
[22] Lenard, M. L., Convergence conditions for restarted conjugate gradient methods with inaccurate line searches, Math. Program., 10, 32-51 (1976) · Zbl 0325.90057
[23] Baptis, P.; Stoer, J., On the relation between quadratic termination and convergence properties of minimization algorithms, Part II, Applications, Numer. Math., 28, 367-391 (1977) · Zbl 0366.65028
[24] Stoer, J., On the relation between quadratic termination and convergence properties of minimization algorithms, Part I, Numer. Math., 28, 343-366 (1977) · Zbl 0366.65027
[25] Al-Baali, M., Descent property and global convergence of the Fletcher-Reeves method with inexact line search, IMA J. numer. Analysis, 5, 121-124 (1985) · Zbl 0578.65063
[26] Ecker, J. G.; Kupferschmid, M., A computational comparison of the ellipsoid algorithm with several nonlinear programming algorithms, SIAM J. Control Optim., 23, 657-674 (1985) · Zbl 0581.90078
[27] Kupferschmid, M.; Ecker, J. G., EA3: A practical implementation of an ellipsoid algorithm for nonlinear programming (1984), Department of Mathematical Sciences, Rensselaer Polytechnic Institute: Department of Mathematical Sciences, Rensselaer Polytechnic Institute Troy, N.Y
[28] Lasdon, L. S.; Waren, A.; Jain, A.; Ratner, M. W., Design and testing of a generalized reduced gradient code for nonlinear programming, ACM Trans. math. Software, 4, 34-50 (1978) · Zbl 0378.90080
[29] Han, S.-P., A globally convergent method for nonlinear programming, J. Optim. Theory Applic., 22, 297-309 (1977) · Zbl 0336.90046
[30] Powell, M. J.D., Algorithms for nonlinear constraints that use Lagrangian functions, Math. Program., 14, 224-248 (1978) · Zbl 0383.90092
[31] Crane, R. L.; Hillstrom, K. E.; Minkoff, M., Solution of the general nonlinear programming problem with subroutine VMCON, Argonne National Laboratory, Report Number ANL-80-64 (1980), Argonne, Ill.
[32] Gill, P. E.; Murray, W., Numerical Methods for Constrained Minimization (1974), Academic Press: Academic Press New York
[33] Biggs, M. C., Constrained minimization using recursive quadratic programming, (Dixon, L. C.W.; Szëgo, G. P., Toward Global Optimization (1975), North-Holland: North-Holland Amsterdam), 341-349 · Zbl 0267.90078
[34] Hatfield Subroutine Library, The Optima User’s Manual (1976), Numerical Optimisation Centre, Hatfield Polytechnic Institute: Numerical Optimisation Centre, Hatfield Polytechnic Institute Hatfield, Hertfordshire, U.K
[35] Colville, A. R., A comparative study of nonlinear programming codes, IBM New York Scientific Center Report Number 320-2949 (1968), 410 East 62nd Street, New York · Zbl 0224.90069
[36] Fletcher, R., Practical Methods of Optimization, (Unconstrained Optimization, Vol. 1 (1980), Wiley: Wiley Chichester) · Zbl 0905.65002
[37] Hager, W. W., Applied Numerical Linear Algebra (1988), Prentice-Hall: Prentice-Hall Englewood Cliffs, N.J · Zbl 0665.65021
[38] Dixon, L. C.W.; Ducksbury, P. G.; Singh, P., A new three-term conjugate gradient method, J. Optim. Theory Applic., 47, 285-300 (1985) · Zbl 0556.90077
[39] Shanno, D. F., Conjugate gradient methods with inexact searches, Math. Op. Res., 3, 244-256 (1978) · Zbl 0399.90077
[40] Forsythe, G. E.; Malcom, M. A.; Moler, C. B., Computer Methods for Mathematical Computations (1977), Prentice-Hall: Prentice-Hall Englewood Cliffs, N.J · Zbl 0361.65002
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.