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

MathSciNet review:
0431675

Full-text PDF Free Access

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]**Larry Armijo,*Minimization of functions having Lipschitz continuous first partial derivatives*, Pacific J. Math.**16**(1966), 1–3. MR**0191071****[2]**Michael J. Best,*A method to accelerate the rate of convergence of a class of optimization algorithms*, Math. Programming**9**(1975), no. 2, 139–160. MR**0405840****[3]**Michael Best J. and Klaus Ritter,*An accelerated conjugate direction method to solve linearly constrained minimization problems*, J. Comput. System Sci.**11**(1975), no. 3, 295–322. MR**0391501****[4]**Jerome Bracken and Garth P. McCormick,*Selected applications of nonlinear programming*, John Wiley & Sons, Inc., New York-London-Sydney, 1968. MR**0233590****[5]**A. R. COLVILLE,*A Comparative Study on Nonlinear Programming Codes*, IBM, New York Scientific Center, Report No. 320-2949, 1968.**[6]**Allen A. Goldstein,*Constructive real analysis*, Harper & Row, Publishers, New York-London, 1967. MR**0217616****[7]**Klaus Ritter,*A superlinearly convergent method for minimization problems with linear inequality constraints*, Math. Programming**4**(1973), 44–71. MR**0323354****[8]**Klaus Ritter,*A method of conjugate directions for linearly constrained nonlinear programming problems*, SIAM J. Numer. Anal.**12**(1975), 273–303. MR**0383745****[9]**K. Ritter,*Accelerating procedures for methods of conjugate directions*, Computing**14**(1975), no. 1-2, 79–105 (English, with German summary). MR**0405850****[10]**M. M. Vainberg,*Variational methods for the study of nonlinear operators*, Holden-Day, Inc., San Francisco, Calif.-London-Amsterdam, 1964. With a chapter on Newton’s method by L. V. Kantorovich and G. P. Akilov. Translated and supplemented by Amiel Feinstein. MR**0176364****[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