On secant updates for use in general constrained optimization

Author:
Richard Tapia

Journal:
Math. Comp. **51** (1988), 181-202

MSC:
Primary 90C30; Secondary 49D37, 90C20

DOI:
https://doi.org/10.1090/S0025-5718-1988-0942149-3

MathSciNet review:
942149

Full-text 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 equality-constrained 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 *q*-superlinearly convergent. To our knowledge this is the first time that either local or *q*-superlinear 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]**M. Avriel,*Nonlinear Programming: Analysis and Methods*, Prentice-Hall, Englewood Cliffs, N. J., 1976. MR**0489892 (58:9264)****[2]**M. C. Bartholomew-Biggs,*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*, T-R 85-5, 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 quasi-Newton methods for constrained optimization,"*SIAM J. Control Optim.*, v. 20, 1982, pp. 161-171. MR**646946 (83d:90174)****[5]**C. G. Broyden, J. E. Dennis, Jr. & J. J. Moré, "On the local and superlinear convergence of quasi-Newton methods,"*J. Inst. Math. Appl.*, v. 12, 1973, pp. 223-245. MR**0341853 (49:6599)****[6]**T. F. Coleman & A. R. Conn, "On the local convergence of a quasi-Newton method for the nonlinear programming problem,"*SIAM J. Numer. Anal.*, v. 21, 1984, pp. 755-769. MR**749369 (85i:90116)****[7]**J. E. Dennis, Jr. & J. J. Moré, "Quasi-Newton methods, motivation and theory,"*SIAM Rev.*, v. 19, 1974, pp. 46-89. MR**0445812 (56:4146)****[8]**J. E. Dennis, Jr. & R. B. Schnabel,*Numerical Methods for Unconstrained Optimization and Nonlinear Equations*, Prentice-Hall, Englewood Cliffs, N. J., 1983. MR**702023 (85j:65001)****[9]**J. E. Dennis, Jr. & H. F. Walker, "Convergence theorems for least-change secant update methods,"*SIAM J. Numer. Anal.*, v. 18, 1981, pp. 949-987. 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 quasi-Newton methods for constrained optimization,"*SIAM J. Numer. Anal.*, v. 24, 1987, pp. 1133-1152. 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. 135-156. MR**536718 (80f:90116)****[15]**S.-P. Han, "Superlinearly convergent variable metric algorithms for general nonlinear programming problems,"*Math. Programming*, v. 11, 1976, pp. 263-283. MR**0483440 (58:3441)****[16]**S.-P. Han, "Dual variable metric algorithms for constrained optimization,"*SIAM J. Control Optim.*, v. 15, 1977, pp. 546-565. 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. 821-850. 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. 27-63. MR**507858 (80c:90138)****[19]**R. A. Tapia, "Diagonalized multiplier methods and quasi-Newton methods for constrained optimization,"*J. Optim. Theory Appl.*, v. 22, 1977, pp. 135-194. MR**0459641 (56:17833)****[20]**R. A. Tapia, "Quasi-Newton 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. 125-163. MR**507861 (80a:90128)**

Retrieve articles in *Mathematics of Computation*
with MSC:
90C30,
49D37,
90C20

Retrieve articles in all journals with MSC: 90C30, 49D37, 90C20

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1988-0942149-3

Keywords:
Quasi-Newton,
nonlinear programming,
superlinear convergence

Article copyright:
© Copyright 1988
American Mathematical Society