Penalty functions, Newton’s method, and quadratic programming. (English) Zbl 0628.90056

Broyden, C. G.; Attia, N. F.

J. Optimization Theory Appl. 58, No. 3, 377-385 (1988).

The search directions computed by two versions of the sequential quadratic programming (SQP) algorithm are compared with that computed by attempting to minimize a quadratic penalty function by Newton’s method, and it is shown that the differences are attributable to ignoring certain terms in the equation for the Newton correction. Since the effect of ignoring these terms may be to make the resultant direction a poor descent direction for the quadratic penalty function, it is argued that the latter is an inappropriate merit function for use with SQP. A method is then suggested by which these terms may be included without losing the benefits gained from the use of the orthogonal transformations derived from the constraints Jacobian.

MSC:

90C20	Quadratic programming
65K05	Numerical mathematical programming methods

Keywords:

constrained optimization; search directions; sequential quadratic programming; quadratic penalty function; Newton’s method

References:

[1]	Fiacco, A. V., andMcCormick, G. P.,Nonlinear Programming: Sequential Unconstrained Minimization Techniques, John Wiley and Sons, New York, New York, 1968. · Zbl 0193.18805
[2]	Fletcher, R., andPowell, M. J. D.,A Rapidly Convergent Descent Method for Minimization, Computer Journal, Vol. 6, pp. 163-168, 1963. · Zbl 0132.11603
[3]	Murray, W.,Constrained Optimization, University of London, PhD Thesis, 1969. · Zbl 0194.47702
[4]	Bartholomew-Biggs, M. C.,Recursive Quadratic Programming Based on Penalty Functions for Constrained Minimization, Nonlinear Optimization, Theory and Algorithms, Edited by L. C. W. Dixon, E. Spedicato, and G. P. Szego, Birkhauser, Boston, Massachusetts, 1980. · Zbl 0446.49027
[5]	Biggs, M. C.,Constrained Minimization Using Recursive Equality Constrained Quadrantic Programming, Numerical Methods for Optimization, Edited by F. A. Lootsma, Academic Press, London, England, 1972. · Zbl 0267.90078
[6]	Murray, W., andWright, M. H.,Projected Lagrangian Methods Based on the Trajectories of Penalty and Barrier Functions, Technical Report No. SOL-78-23, Stanford University, 1978.
[7]	Gill, P. E., Murray, W., Saunders, M. A., andWright, M. H.,Recent Developments in Constrained Optimization, Numerical Algorithms Group, News-letter 1/84, 1984.
[8]	Han, S. P.,A Globally Convergent Method for Nonlinear Programming, Journal of Optimization Theory and Applications, Vol. 22, pp. 297-310, 1977. · Zbl 0336.90046
[9]	Powell, M. J. D.,A Fast Algorithm for Nonlinearly Constrained Optimization Calculations, Numerical Analysis: Proceedings of the Biennial Conference Held at Dundee, June-July 1977; Edited by G. A. Watson, Springer-Verlag, Berlin, Germany, pp. 144-157, 1978.
[10]	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
[11]	Di Pillo, G., andGrippo, L.,A Class of Continuously-Differentiable Exact Penalty Functions for Nonlinear Programming Problems, Systems Modelling and Optimization, Edited by P. Thoft-Christensen, Springer-Verlag, Berlin, Germany, pp. 246-256, 1983.
[12]	Broyden, C. G., andAttia, N. F.,A Smooth Sequential Penalty Function Method for Solving Nonlinear Programming Problems, Systems Modelling and Optimization, Edited by P. Thoft-Christense, Springer-Verlag, Berlin, Germany, pp. 237-245, 1983.
[13]	Gerencser, L.,A Second-Order Technique for the Solution of Nonlinear Optimization Problems, Colloquia Mathematica Societatis Janos Bolyai, Vol. 12, pp. 403-415, 1974.
[14]	Hock, W., andSchittkowski, K.,Test Examples for Nonlinear Programming Codes, Springer-Verlag, Berlin, Germany, 1981. · Zbl 0452.90038
[15]	Dembo, R. S.,A Set of Geometric Test Problems and Their Solutions, Mathematical Programming, Vol. 10, pp. 192-213, 1976. · Zbl 0349.90066
[16]	Gill, P. E., Murray, W., andWright, M. H.,Practical Optimization, Academic Press, London, England, 1981. · Zbl 0503.90062