On secant updates for use in general constrained optimization
Author:
Richard Tapia
Journal:
Math. Comp. 51 (1988), 181202
MSC:
Primary 90C30; Secondary 49D37, 90C20
MathSciNet review:
942149
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: In this paper we present two new classes of successive quadratic programming (SQP) secant methods for the equalityconstrained optimization problem. One class of methods uses the SQP augmented Lagrangian formulation, while the other class uses the SQP Lagrangian formulation. We demonstrate, under the standard assumptions, that in both cases the BFGS and DFP versions of the algorithm are locally qsuperlinearly convergent. To our knowledge this is the first time that either local or qsuperlinear convergence has been established for an SQP Lagrangian secant method which uses either the BFGS or DFP updating philosophy and assumes no more than the standard assumptions. Since the standard assumptions do not require positive definiteness of the Hessian of the Lagrangian at the solution, it is no surprise that our BFGS and DFP updates possess the hereditary positive definiteness property only on a proper subspace.
 [1]
Mordecai
Avriel, Nonlinear programming, PrenticeHall, Inc., Englewood
Cliffs, N.J., 1976. Analysis and methods; PrenticeHall Series in Automatic
Computation. MR
0489892 (58 #9264)
 [2]
M. C. BartholomewBiggs, Matrix Updating in Nonlinear Programming Calculation, TR No. 156, The Hatfield Polytechnic Numerical Optimization Center, Hatfield, Hertfordshire, England, 1985.
 [3]
P. T. Boggs & J. W. Tolle, An Efficient Strategy for Utilizing a Merit Function in Nonlinear Programming Algorithms, TR 855, Curriculum in Operations Research and Systems Analysis, University of North Carolina, Chapel Hill.
 [4]
Paul
T. Boggs, Jon
W. Tolle, and Pyng
Wang, On the local convergence of quasiNewton methods for
constrained optimization, SIAM J. Control Optim. 20
(1982), no. 2, 161–171. MR 646946
(83d:90174), http://dx.doi.org/10.1137/0320014
 [5]
C.
G. Broyden, J.
E. Dennis Jr., and Jorge
J. Moré, On the local and superlinear convergence of
quasiNewton methods, J. Inst. Math. Appl. 12 (1973),
223–245. MR 0341853
(49 #6599)
 [6]
Thomas
F. Coleman and Andrew
R. Conn, On the local convergence of a quasiNewton method for the
nonlinear programming problem, SIAM J. Numer. Anal.
21 (1984), no. 4, 755–769. MR 749369
(85i:90116), http://dx.doi.org/10.1137/0721051
 [7]
J.
E. Dennis Jr. and Jorge
J. Moré, QuasiNewton methods, motivation and theory,
SIAM Rev. 19 (1977), no. 1, 46–89. MR 0445812
(56 #4146)
 [8]
John
E. Dennis Jr. and Robert
B. Schnabel, Numerical methods for unconstrained optimization and
nonlinear equations, Prentice Hall Series in Computational
Mathematics, Prentice Hall, Inc., Englewood Cliffs, NJ, 1983. MR 702023
(85j:65001)
 [9]
J.
E. Dennis Jr. and Homer
F. Walker, Convergence theorems for leastchange secant update
methods, SIAM J. Numer. Anal. 18 (1981), no. 6,
949–987. MR
638993 (83a:65052a), http://dx.doi.org/10.1137/0718067
 [10]
R.
Fletcher, Practical methods of optimization. Vol. 1, John
Wiley & Sons, Ltd., Chichester, 1980. Unconstrained optimization; A
WileyInterscience Publication. MR 585160
(83i:65055a)
 [11]
R. Fontecilla, The Lack of Positive Definiteness in the Hessian in Constrained Optimization, TR 1334, Department of Computer Science, University of Maryland, College Park, Maryland 20742, 1983.
 [12]
Rodrigo
Fontecilla, Trond
Steihaug, and Richard
A. Tapia, A convergence theory for a class of quasiNewton methods
for constrained optimization, SIAM J. Numer. Anal. 24
(1987), no. 5, 1133–1151. MR 909070
(89b:65155), http://dx.doi.org/10.1137/0724075
 [13]
Philip
E. Gill, Walter
Murray, and Margaret
H. Wright, Practical optimization, Academic Press, Inc.
[Harcourt Brace Jovanovich, Publishers], LondonNew York, 1981. MR 634376
(83d:65195)
 [14]
S.
T. Glad, Properties of updating methods for the multipliers in
augmented Lagrangians, J. Optim. Theory Appl. 28
(1979), no. 2, 135–156. MR 536718
(80f:90116), http://dx.doi.org/10.1007/BF00933239
 [15]
Shih
Ping Han, Superlinearly convergent variable metric algorithms for
general nonlinear programming problems, Math. Programming
11 (1976/77), no. 3, 263–282. MR 0483440
(58 #3441)
 [16]
Shih
Ping Han, Dual variable metric algorithms for constrained
optimization, SIAM J. Control Optimization 15 (1977),
no. 4, 546–565. MR 0459635
(56 #17827)
 [17]
Jorge
Nocedal and Michael
L. Overton, Projected Hessian updating algorithms for nonlinearly
constrained optimization, SIAM J. Numer. Anal. 22
(1985), no. 5, 821–850. MR 799115
(86m:90141), http://dx.doi.org/10.1137/0722050
 [18]
M.
J. D. Powell, The convergence of variable metric methods for
nonlinearly constrained optimization calculations, Nonlinear
programming, 3 (Proc. Sympos., Special Interest Group Math. Programming,
Univ. Wisconsin, Madison, Wis., 1977) Academic Press, New YorkLondon,
1978, pp. 27–63. MR 507858
(80c:90138)
 [19]
R.
A. Tapia, Diagonalized multiplier methods and quasiNewton methods
for constrained optimization, J. Optimization Theory Appl.
22 (1977), no. 2, 135–194. MR 0459641
(56 #17833)
 [20]
R.
A. Tapia, QuasiNewton methods for equality constrained
optimization: equivalence of existing methods and a new
implementation, Nonlinear programming, 3 (Proc. Sympos., Special
Interest Group Math. Programming, Univ. Wisconsin, Madison, Wis., 1977)
Academic Press, New YorkLondon, 1978, pp. 125–164. MR 507861
(80a:90128)
 [1]
 M. Avriel, Nonlinear Programming: Analysis and Methods, PrenticeHall, Englewood Cliffs, N. J., 1976. MR 0489892 (58:9264)
 [2]
 M. C. BartholomewBiggs, Matrix Updating in Nonlinear Programming Calculation, TR No. 156, The Hatfield Polytechnic Numerical Optimization Center, Hatfield, Hertfordshire, England, 1985.
 [3]
 P. T. Boggs & J. W. Tolle, An Efficient Strategy for Utilizing a Merit Function in Nonlinear Programming Algorithms, TR 855, Curriculum in Operations Research and Systems Analysis, University of North Carolina, Chapel Hill.
 [4]
 P. T. Boggs, J. W. Tolle & P. Wang, "On the local convergence of quasiNewton methods for constrained optimization," SIAM J. Control Optim., v. 20, 1982, pp. 161171. MR 646946 (83d:90174)
 [5]
 C. G. Broyden, J. E. Dennis, Jr. & J. J. Moré, "On the local and superlinear convergence of quasiNewton methods," J. Inst. Math. Appl., v. 12, 1973, pp. 223245. MR 0341853 (49:6599)
 [6]
 T. F. Coleman & A. R. Conn, "On the local convergence of a quasiNewton method for the nonlinear programming problem," SIAM J. Numer. Anal., v. 21, 1984, pp. 755769. MR 749369 (85i:90116)
 [7]
 J. E. Dennis, Jr. & J. J. Moré, "QuasiNewton methods, motivation and theory," SIAM Rev., v. 19, 1974, pp. 4689. MR 0445812 (56:4146)
 [8]
 J. E. Dennis, Jr. & R. B. Schnabel, Numerical Methods for Unconstrained Optimization and Nonlinear Equations, PrenticeHall, Englewood Cliffs, N. J., 1983. MR 702023 (85j:65001)
 [9]
 J. E. Dennis, Jr. & H. F. Walker, "Convergence theorems for leastchange secant update methods," SIAM J. Numer. Anal., v. 18, 1981, pp. 949987. MR 638993 (83a:65052a)
 [10]
 R. Fletcher, Practical Methods of Optimization, vol. 1, Wiley, New York, 1980. MR 585160 (83i:65055a)
 [11]
 R. Fontecilla, The Lack of Positive Definiteness in the Hessian in Constrained Optimization, TR 1334, Department of Computer Science, University of Maryland, College Park, Maryland 20742, 1983.
 [12]
 R. Fontecilla, T. Steihaug & R. A. Tapia, "A convergence theory for a class of quasiNewton methods for constrained optimization," SIAM J. Numer. Anal., v. 24, 1987, pp. 11331152. MR 909070 (89b:65155)
 [13]
 P. Gill, W. Murray & M. Wright, Practical Optimization, Academic Press, New York, 1981. MR 634376 (83d:65195)
 [14]
 S. T. Glad, "Properties of updating methods for the multipliers in augmented Lagrangians," J. Optim. Theory Appl., v. 28, 1979, pp. 135156. MR 536718 (80f:90116)
 [15]
 S.P. Han, "Superlinearly convergent variable metric algorithms for general nonlinear programming problems," Math. Programming, v. 11, 1976, pp. 263283. MR 0483440 (58:3441)
 [16]
 S.P. Han, "Dual variable metric algorithms for constrained optimization," SIAM J. Control Optim., v. 15, 1977, pp. 546565. MR 0459635 (56:17827)
 [17]
 J. Nocedal & M. Overton, "Projected Hessian updating algorithms for nonlinearly constrained optimization," SIAM J. Numer. Anal., v. 22, 1985, pp. 821850. MR 799115 (86m:90141)
 [18]
 M. J. D. Powell, "The convergence of variable metric methods for nonlinearly constrained optimization problems," in Nonlinear Programming 3 (O. Mangasarian, R. Meyer and S. Robinson, eds.), Academic Press, New York, 1978, pp. 2763. MR 507858 (80c:90138)
 [19]
 R. A. Tapia, "Diagonalized multiplier methods and quasiNewton methods for constrained optimization," J. Optim. Theory Appl., v. 22, 1977, pp. 135194. MR 0459641 (56:17833)
 [20]
 R. A. Tapia, "QuasiNewton methods for equality constrained optimization: equivalence of existing methods and a new implementation," in Nonlinear Programming 3 (O. Mangasarian, R. Meyer and S. Robinson, eds.), Academic Press, New York, 1978, pp. 125163. MR 507861 (80a:90128)
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC:
90C30,
49D37,
90C20
Retrieve articles in all journals
with MSC:
90C30,
49D37,
90C20
Additional Information
DOI:
http://dx.doi.org/10.1090/S00255718198809421493
PII:
S 00255718(1988)09421493
Keywords:
QuasiNewton,
nonlinear programming,
superlinear convergence
Article copyright:
© Copyright 1988
American Mathematical Society
