Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



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

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 $ (n - p + 1)$-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.

References [Enhancements On Off] (What's this?)

  • [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.

Similar Articles

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

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

Additional Information

Keywords: Conjugate direction methods, superlinear convergence, mathematical programming, linearly constrained optimization
Article copyright: © Copyright 1976 American Mathematical Society

American Mathematical Society