Skip to main content
Springer Nature Link
Log in

Local convergence analysis for the REQP algorithm using conjugate basis matrices

  • Contributed Papers
  • Published:
Journal of Optimization Theory and Applications Aims and scope Submit manuscript

Abstract

The REQP algorithm solves constrained minimization problems using a sequential quadratic programming technique based on the properties of penalty functions. The convergence of REQP has been studied elsewhere (Refs. 1, 2). This paper uses a novel approach to the analysis of the method near to the solution, based on the use of conjugate subspaces. The stepp taken by a constrained minimization algorithm can be thought of as having two components,h in the subspace tangential to the constraints andv in the subspace spanned by the constraint normals. It is usual forh andv to be orthogonal components. Recently, Dixon (Ref. 3) has suggested constructingp from components which are not orthogonal. That is, we writep=h′ + v′, whereh′ is in the subspace tangential to the constraints and wherev′ andh′ are conjugate with respect to the Hessian of the Lagrangian function. By looking at the conjugate components of the REQP search directions, it is possible to simplify the analysis of the behavior near the solution and to obtain new results about the local rate of convergence of the method.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Bartholomew-Biggs, M. C.,A Globally Convergent Version of REQP for Constrained Minimization, IMA Journal of Numerical Analysis, Vol. 8, pp. 253–271, 1988.

    Google Scholar 

  2. Biggs, M. C.,On the Convergence of Some Constrained Minimization Algorithms Based on Recursive Quadratic Programming, Journal of the Institute of Mathematics and Its Applications, Vol. 21, pp. 67–81, 1978.

    Google Scholar 

  3. Dixon, L. C. W.,Conjugate Bases for Constrained Optimization, Technical Report 181, Numerical Optimisation Centre, Hatfield Polytechnic, 1987.

  4. Powell, M. J. D.,A Fast Algorithm for Nonlinearly Constrained Optimization Calculations, Numerical Analysis, Dundee-1977, Edited by G. A. Watson, Springer-Verlag, Berlin, Germany, 1978.

    Google Scholar 

  5. Byrd, R. H., Tapia, R. A., andZhang, Y.,An SQP Augmented Lagrangian BFGS Algorithm for Constrained Optimization, Technical Report 89-4, Department of Mathematical Sciences, Rice University, 1989.

  6. Powell, M. J. D.,A Tolerant Algorithm for Linearly Constrained Optimization Calculations, Report DAMTP 1988/NA17, University of Cambridge, 1988.

  7. Nguyen, T. T.,Conjugate Basis Methods for Solving the Equality Constrained Minimization Problem, Technical Report 215, Numerical Optimisation Centre, Hatfield Polytechnic, 1988.

  8. Coleman, T. F., andConn, A. R.,Nonlinear Programming via an Exact Penalty Function: Asymptotic Analysis, Mathematical Programming, Vol. 24, pp. 123–136, 1982.

    Google Scholar 

  9. Byrd, R. H.,On the Convergence of Constrained Optimization Methods with Accurate Hessian Information on a Subspace, Report CU-CS-270, University of Colorado, 1984.

  10. Gill, P. E., Murray, W., andWright, M. A.,Practical Optimization, Academic Press, New York, New York, 1981.

    Google Scholar 

  11. Bartholomew-Biggs, M. C., andNguyen, T. T.,Orthogonal Basis Methods for Solving Equality Constrained Minimization Problems, Technical Report 207, Numerical Optimisation Centre, Hatfield Polytechnic, 1988.

  12. Powell, M. J. D.,On the Quadratic Programming Algorithm of Goldfarb and Idnani, Report DAMTP 1983/NA19, University of Cambridge, 1983.

  13. Goldfarb, D., andIdnani, A.,A Numerically Stable Dual Method for Solving Strictly Convex Quadratic Programming Problems, Mathematical Programming, Vol. 27, pp. 1–33, 1983.

    Google Scholar 

  14. Nguyen, T. T.,Conjugate Basis Methods for Constrained Optimization, PhD Thesis, Hatfield Polytechnic, 1989.

  15. Bartholomew-Biggs, M. C.,Numerical Examples of the Behavior of REQP on Nonlinear Programming Problems Involving Linear Dependence among the Constraint Normals, Journal of Optimization Theory and Applications, Vol. 48, pp. 215–227, 1986.

    Google Scholar 

  16. Fontecilla, R.,Local Convergence of Secant Methods for Nonlinear Constrained Optimization, SIAM Journal on Numerical Analysis, Vol. 25, pp. 692–712, 1988.

    Google Scholar 

  17. Bartholomew-Biggs, M. C.,A Note on Matrix Updating Strategies in Numerical Methods for Constrained Optimization, Technical Report 156, Numerical Optimisation Centre, Hatfield Polytechnic, 1990.

Download references

Author information

Authors and Affiliations

  1. Mathematics Division, Hatfield Polytechnic, Hatfield, England

    M. C. Bartholomew-Biggs (Reader)

  2. Numerical Optimisation Centre, Hatfield Polytechnic, Hatfield, England

    T. T. Nguyen (Research Student)

Authors
  1. M. C. Bartholomew-Biggs
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. T. T. Nguyen
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

Communicated by L. C. W. Dixon

This work was supported by a SERC Studentship (TTN).

Rights and permissions

Reprints and permissions

About this article

Cite this article

Bartholomew-Biggs, M.C., Nguyen, T.T. Local convergence analysis for the REQP algorithm using conjugate basis matrices. J Optim Theory Appl 71, 31–45 (1991). https://doi.org/10.1007/BF00940038

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF00940038

Key Words

Search

Navigation