A class of accelerated conjugate direction methods for linearly constrained minimization problems

Authors:
Michael J. Best and Klaus Ritter

Journal:
Math. Comp. **30** (1976), 478-504

MSC:
Primary 65K05; Secondary 90C30

DOI:
https://doi.org/10.1090/S0025-5718-1976-0431675-3

MathSciNet review:
0431675

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: A class of algorithms are described for the minimization of a function of *n* variables subject to linear inequality constraints. Under weak conditions convergence to a stationary point is demonstrated. The method uses a mixture of conjugate direction constructing and accelerating steps. Any mixture, for example alternation, may be used provided that the subsequence of conjugate direction constructing steps is infinite. The mixture of steps may be specified so that under appropriate assumptions the rate of convergence of the method is two-step superlinear or -step cubic where *p* is the number of constraints active at a stationary point. The accelerating step is always superlinearly convergent. A condition is given under which the alternating policy is every step superlinear. Computational results are given for several test problems.

**[1]**L. ARMIJO, "Minimization of functions having Lipschitz continuous first partial derivatives,"*Pacific J. Math.*, v. 16, 1966, pp. 1-3. MR**32**#8480. MR**0191071 (32:8480)****[2]**M. J. BEST, "A method to accelerate the rate of convergence of a class of optimization algorithms,"*Math. Programming*, v. 8, 1975, pp. 139-160. MR**0405840 (53:9632)****[3]**M. J. BEST & K. RITTER, "An accelerated conjugate direction method to solve linearly constrained minimization problems,"*J. Comput. System Sci.*, v. 11, 1975, pp. 295-322. MR**0391501 (52:12322)****[4]**J. BRACKEN & G. P. McCORMICK,*Selected Applications of Nonlinear Programming*, Wiley, New York, 1968. MR**38**#1911. MR**0233590 (38:1911)****[5]**A. R. COLVILLE,*A Comparative Study on Nonlinear Programming Codes*, IBM, New York Scientific Center, Report No. 320-2949, 1968.**[6]**A. A. GOLDSTEIN,*Constructive Real Analysis*, Harper & Row, New York, 1967. MR**36**#705. MR**0217616 (36:705)****[7]**K. RITTER, "A superlinearly convergent method for minimization problems with linear inequality constraints,"*Math. Programming*, v. 4, 1973, pp. 44-71. MR**48**#1711. MR**0323354 (48:1711)****[8]**K. RITTER, "A method of conjugate directions for linearly constrained nonlinear programming problems,"*SIAM J. Numer. Anal.*, v. 12, 1975, pp. 273-303. MR**0383745 (52:4625)****[9]**K. RITTER, "Accelerating procedures for methods of conjugate directions,"*Computing*, v. 14, 1975, pp. 79-105. MR**0405850 (53:9642)****[10]**M. M. VAĬNBERG,*Variational Methods for the Study of Nonlinear Operators*, GITTL, Moscow, 1956; English transl., Holden-Day, San Francisco, Calif., 1964. MR**19**, 567;**31**#638. MR**0176364 (31:638)****[11]**G. ZOUTENDIJK,*Methods of Feasible Directions, A Study in Linear and Nonlinear Programming*, American Elsevier, New York, 1960. MR**23**#B2156.

Retrieve articles in *Mathematics of Computation*
with MSC:
65K05,
90C30

Retrieve articles in all journals with MSC: 65K05, 90C30

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1976-0431675-3

Keywords:
Conjugate direction methods,
superlinear convergence,
mathematical programming,
linearly constrained optimization

Article copyright:
© Copyright 1976
American Mathematical Society