×

Local convergence analysis for the REQP algorithm using conjugate basis matrices. (English) Zbl 0795.90059

Summary: 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 [see the first author, IMA J. Numer. Anal. 8, No. 2, 253-271 (1988; Zbl 0643.65030); J. Inst. Math. Appl. 21, 67-71 (1978; Zbl 0373.90056)]. This paper uses a novel approach to the analysis of the method near to the solution, based on the use of conjugate subspaces. The step \(p\) taken by a constrained minimization algorithm can be thought of as having two components, \(h\) in the subspace tangential to the constraints and \(v\) in the subspace spanned by the constraint normals. It is usual for \(h\) and \(v\) to be orthogonal components. Recently, L. C. W. Dixon [‘Conjugate bases for constrained optimization’, Tech. Rep. 181, Numer. Optimization Centre, Hatfield Polytechnic (1987)] has suggested constructing \(p\) from components which are not orthogonal. That is, we write \(p= h'+ v'\), where \(h'\) is in the subspace tangential to the constraints and where \(v'\) and \(h'\) 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.

MSC:

90C30 Nonlinear programming

Software:

ZQPCVX
Full Text: DOI

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. · Zbl 0643.65030 · doi:10.1093/imanum/8.2.253
[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. · Zbl 0373.90056 · doi:10.1093/imamat/21.1.67
[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. · Zbl 0374.65032
[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. · Zbl 0773.90065
[6] Powell, M. J. D.,A Tolerant Algorithm for Linearly Constrained Optimization Calculations, Report DAMTP 1988/NA17, University of Cambridge, 1988. · Zbl 0695.90084
[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. · Zbl 0501.90078 · doi:10.1007/BF01585100
[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. · Zbl 0503.90062
[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. · Zbl 0643.65030
[12] Powell, M. J. D.,On the Quadratic Programming Algorithm of Goldfarb and Idnani, Report DAMTP 1983/NA19, University of Cambridge, 1983. · Zbl 0584.90069
[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. · Zbl 0537.90081 · doi:10.1007/BF02591962
[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. · Zbl 0559.90074 · doi:10.1007/BF00940670
[16] Fontecilla, R.,Local Convergence of Secant Methods for Nonlinear Constrained Optimization, SIAM Journal on Numerical Analysis, Vol. 25, pp. 692-712, 1988. · Zbl 0698.65042 · doi:10.1137/0725042
[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.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.