Summary
The paper represents an outcome of an extensive comparative study of nonlinear optimization algorithms. This study indicates that quadratic approximation methods which are characterized by solving a sequence of quadratic subproblems recursively, belong to the most efficient and reliable nonlinear programming algorithms available at present. The purpose of this paper is to analyse the theoretical convergence properties and to investigate the numerical performance in more detail. In Part 1, the exactL 1-penalty function of Han and Powell is replaced by a differentiable augmented Lagrange function for the line search computation to be able to prove the global convergence and to show that the steplength one is chosen in the neighbourhood of a solution. In Part 2, the quadratic subproblem is exchanged by a linear least squares problem to improve the efficiency, and to test the dependence of the performance from different solution methods for the quadratic or least squares subproblem.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Armijo, L.: Minimization of functions having Lipschitz-continuous first partial derivatives. Pacific J. Math.16, 1–3 (1966)
Biggs, M.C.: On the convergence of some constrained minimization algorithms based on recursive quadratic programming. J. Inst. Math. Appl.21, 67–82 (1978)
Bartholomew-Biggs, M.C.: An improved implementation of the recursive quadratic programming method for constrained minimization. Technical Report No. 105, Numerical Optimisation Centre. The Hatfield Polytechnic, Hatfield, England, 1979
Chamberlain, R.M.: Some examples of cycling in variable metric methods for constrained minimization. Math. Programming,16, 378–384 (1979)
Crane, R.L., Garbow, B.S., Hillstrom, K.E., Minkoff, M.: LCLSQ: An implementation of an algorithm for linearly constrained linear least squares problems. ANL-80-116, Argonne National Laboratory, Argonne, Illinois, 1980
Dixon, L.C.W.: On the convergence properties of variable metric recursive quadratic programming methods. Presented at the Workshop on Linear and Nonlinear Programming, Brussels, 1980
Fletcher, R.: A general quadratic programming algorithm, J. Inst. Math. Appl.7, 76–91 (1971)
Fletcher, R.: Numerical experiments with an exactL 1 penalty function method. Nonlinear Programming 4, in: (O.L. Mangasarian et al. eds.), New York, San Francisco: Academic Press 1981
Gill, P.E., Murray, W., Saunders, M.A.: Methods for computing and modifying the LDV factors of a matrix. Math. Comput.29, 1051–1077 (1975)
Han, S.-P.: Superlinearly convergent variable metric algorithms for general nonlinear programming problems. Math. Programming11, 263–282 (1976)
Han, S.-P.: A globally convergent method for nonlinear programming. J. Optimization Theory Appl.22, 297–309 (1977)
Himmelblau, D.M.: Applied nonlinear programming. New York: McGraw-Hill, 1972
Hock, W., Schittkowski, K.: Test examples for nonlinear programming codes. Lecture Notes in Economics and Mathematical Systems. Vol. 187. Berlin, Heidelberg, New York: Springer 1981
Lawson, C.L., Hanson, R.J.: Solving least squares problems, Englewood Cliffs, New Jersey: Prentice Hall, 1974
Maratos, N.: Exact penalty function algorithms for finite dimensional and control optimization problems. Ph.D. Thesis, Imperial College. London, 1978
Mayne, D.Q.: On the use of exact penalty functions to determine step length in optimization algorithms. In: Numerical analysis, (G.A. Watson ed.). Lecture Notes in Mathematics, Vol. 773. Berlin, Heidelberg, New York: Springer 1980
Ortega, J.M., Rheinboldt, W.C.: Iterative solution of nonlinear equations in several variables. New York, San Francisco, London: Academic Press, 1970
Powell, M.J.D.: A hybrid method for nonlinear equations. In: Numerical methods for nonlinear algebraic equations. (P. Rabinowitz ed.), London: Gordon and Breach, 1970
Powell, M.J.D.: A fast algorithm for nonlinearly constrained optimization calculations. In: Numerical Analysis. Proceedings of the Biennial Conference Held at Dundee, June 1977. (G.A. Watson, ed.) Lecture Notes in Mathematics, Vol. 630. Berlin, Heidelberg, New York: Springer 1978
Powell, M.J.D.: The convergence of variable metric methods for nonlinearly constrained optimization calculations. In: Nonlinear programming 3, (O.L. Mangasarian, R.R. Meyer, S.M. Robinson eds.) New York, San Francisco, London, Academic Press, 1978
Schittkowski, K.: An adaptive precision method for nonlinear optimization problems. SIAMJ. Control Optimization,17, 82–98 (1979)
Schittkowski, K.: Nonlinear programming codes. Information, tests, perfomance. Lecture Notes in Economics and Mathematical Systems, Vol. 183, Berlin, Heidelberg, New York, Springer 1980
Schittkowski, K., Stoer, J.: A factorization method for the solution of constrained linear least squares problems allowing subsequent data changes. Numer. Math.31, 431–463 (1979)
Wilson, R.B.: A simplicial algorithm for concave programming. Ph.D. Dissertation, Graduate School of Business Administration, Harward University, Boston, 1963
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Schittkowski, K. The nonlinear programming method of Wilson, Han, and Powell with an augmented Lagrangian type line search function. Numer. Math. 38, 83–114 (1982). https://doi.org/10.1007/BF01395810
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01395810