A class of accelerated conjugate direction methods for linearly constrained minimization problems
Authors:
Michael J. Best and Klaus Ritter
Journal:
Math. Comp. 30 (1976), 478504
MSC:
Primary 65K05; Secondary 90C30
MathSciNet review:
0431675
Fulltext 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 twostep 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 (32 #8480)
 [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
(53 #9632)
 [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
(52 #12322)
 [4]
Jerome
Bracken and Garth
P. McCormick, Selected applications of nonlinear programming,
John Wiley & Sons, Inc., New YorkLondonSydney, 1968. MR 0233590
(38 #1911)
 [5]
A. R. COLVILLE, A Comparative Study on Nonlinear Programming Codes, IBM, New York Scientific Center, Report No. 3202949, 1968.
 [6]
Allen
A. Goldstein, Constructive real analysis, Harper & Row,
Publishers, New YorkLondon, 1967. MR 0217616
(36 #705)
 [7]
Klaus
Ritter, A superlinearly convergent method for minimization problems
with linear inequality constraints, Math. Programming
4 (1973), 44–71. MR 0323354
(48 #1711)
 [8]
Klaus
Ritter, A method of conjugate directions for linearly constrained
nonlinear programming problems, SIAM J. Numer. Anal.
12 (1975), 273–303. MR 0383745
(52 #4625)
 [9]
K.
Ritter, Accelerating procedures for methods of conjugate
directions, Computing 14 (1975), no. 12,
79–105 (English, with German summary). MR 0405850
(53 #9642)
 [10]
M.
M. Vainberg, Variational methods for the study of nonlinear
operators, HoldenDay, Inc., San Francisco, Calif.LondonAmsterdam,
1964. With a chapter on Newton’s method by L. V. Kantorovich and G.
P. Akilov. Translated and supplemented by Amiel Feinstein. 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.
 [1]
 L. ARMIJO, "Minimization of functions having Lipschitz continuous first partial derivatives," Pacific J. Math., v. 16, 1966, pp. 13. 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. 139160. 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. 295322. 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. 3202949, 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. 4471. 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. 273303. MR 0383745 (52:4625)
 [9]
 K. RITTER, "Accelerating procedures for methods of conjugate directions," Computing, v. 14, 1975, pp. 79105. MR 0405850 (53:9642)
 [10]
 M. M. VAĬNBERG, Variational Methods for the Study of Nonlinear Operators, GITTL, Moscow, 1956; English transl., HoldenDay, 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
DOI:
http://dx.doi.org/10.1090/S00255718197604316753
PII:
S 00255718(1976)04316753
Keywords:
Conjugate direction methods,
superlinear convergence,
mathematical programming,
linearly constrained optimization
Article copyright:
© Copyright 1976
American Mathematical Society
