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.
Similar content being viewed by others
References
Bartholomew-Biggs, M. C.,A Globally Convergent Version of REQP for Constrained Minimization, IMA Journal of Numerical Analysis, Vol. 8, pp. 253–271, 1988.
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.
Dixon, L. C. W.,Conjugate Bases for Constrained Optimization, Technical Report 181, Numerical Optimisation Centre, Hatfield Polytechnic, 1987.
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.
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.
Powell, M. J. D.,A Tolerant Algorithm for Linearly Constrained Optimization Calculations, Report DAMTP 1988/NA17, University of Cambridge, 1988.
Nguyen, T. T.,Conjugate Basis Methods for Solving the Equality Constrained Minimization Problem, Technical Report 215, Numerical Optimisation Centre, Hatfield Polytechnic, 1988.
Coleman, T. F., andConn, A. R.,Nonlinear Programming via an Exact Penalty Function: Asymptotic Analysis, Mathematical Programming, Vol. 24, pp. 123–136, 1982.
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.
Gill, P. E., Murray, W., andWright, M. A.,Practical Optimization, Academic Press, New York, New York, 1981.
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.
Powell, M. J. D.,On the Quadratic Programming Algorithm of Goldfarb and Idnani, Report DAMTP 1983/NA19, University of Cambridge, 1983.
Goldfarb, D., andIdnani, A.,A Numerically Stable Dual Method for Solving Strictly Convex Quadratic Programming Problems, Mathematical Programming, Vol. 27, pp. 1–33, 1983.
Nguyen, T. T.,Conjugate Basis Methods for Constrained Optimization, PhD Thesis, Hatfield Polytechnic, 1989.
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.
Fontecilla, R.,Local Convergence of Secant Methods for Nonlinear Constrained Optimization, SIAM Journal on Numerical Analysis, Vol. 25, pp. 692–712, 1988.
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.
Author information
Authors and Affiliations
Additional information
Communicated by L. C. W. Dixon
This work was supported by a SERC Studentship (TTN).
Rights 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
Issue Date:
DOI: https://doi.org/10.1007/BF00940038