Constrained nonlinear least squares: an exact penalty approach with projected structured quasi-Newton updates

ABSTRACT

This paper is concerned with the development, numerical implementation, and testing of an algorithm for solving constrained nonlinear least squares problems. The algorithm is an adaptation of the least squares case of an exact penalty method for solving nonlinearly constrained optimization problems due to Coleman and Conn. It also uses the ideas of Nocedal and Overton for handling quasi-Newton updates of projected Hessians, those of Dennis, Gay, and Welsch for approaching the structure of nonlinear least squares Hessians, and those of Murray and Overton for performing line searches. This method has been tested on a selection of problems listed in the collection of Hock and Schittkowski. The results indicate that the approach taken here is a viable alternative for least squares problems to the general nonlinear methods studied by Hock and Schittkowski.

REFERENCES

• 1: BOGGS, P. T., AND DENNIS, J. E., JR. A stability analysis for perturbed nonlinear iterative methods. Math. Comput. 30 (1976), 1-17.
• 2: BROYDEN, C.G. The convergence of a class of double-rank minimization algorithms. J. Inst. Math. Appl. 6 (1970), 76-90.
• 3: Senad Busovaca, Handling degeneracy in a nonlinear l(,1) algorithm, 1985
• 4: R H Byrd , R B Schnabel, Continuity of the null space basis and constrained optimization, Mathematical Programming: Series A and B, v.35 n.1, p.32-41, May 1986 [doi>10.1007/BF01589439]
• 5: CHAMBERLAIN, R. M., POWELL, M. J. D., LEMARI~CHAL, C., AND PEDERSEN, H. C. The watchdog technique for forcing convergence in algorithms for constrained optimization. Math. Program. Stud. 16 (1982), 1-17.
• 6: COLEMAN, T. F., AND CONN, A. R. Second-order conditions for an exact penalty function. Math. Program. 19 (1980), 155-177.
• 7: COLEMAN, T. F., AND CONN, A. R. Nonlinear programming via an exact penalty function: Global analysis. Math. Program. 24 (1982), 137-161.
• 8: COLEMAN, T. F., AND CONN, A. R. Nonlinear programming via an exact penalty function: Asymptotic analsyis. Math. Program. 24 (1982), 123-136.
• 9: COLEMAN, T. F., AND CONN, A.R. On the local convergence of a quasi-Newton method for the nonlinear programming problem. SIAM J. Numer. Anal. 21 (1984), 755-769.
• 10: COLEMAN, T. F., AND SORENSEN, D.C. A note on the computation of an orthogonal basis for the null space of a matrix. Math. Program. 29, 2 (1984), 234-242.
• 11: DAVIDON, W.C. Variable metric method for minimization. ANL-5990 Review, Argonne National Laboratory, Argonne, Ill., 1959.
• 12: DENNIS, J. E., JR. Nonlinear Least Squares and Equations. In The State of the Art of Numerical Analysis, D. Jacobs, Ed. Academic Press, Orlando, Fla., 1977.
• 13: DENNIS, J. E., JR. Techniques for nonlinear least squares and robust regression. Commun. Stat.-Simul. Comput. B 7, 4 (1978), 345-359.
• 14: DENNIS, J. E., JR., AND Moal~, J.J. Quasi-Newton methods: Motivation and theory. SIAM Rev. 19 (1977), 46-89.
• 15: John E. Dennis, Jr. , David M. Gay , Roy E. Walsh, An Adaptive Nonlinear Least-Squares Algorithm, ACM Transactions on Mathematical Software (TOMS), v.7 n.3, p.348-368, Sept. 1981 [doi>10.1145/355958.355965]
• 16: DENNIS, J. E., JR:, MARTINEZ, H. J., AND TAPIA, R.A. A convergence theory for the structured BFGS secant method with an application to nonlinear least squares. Tech. Rep. 87-15, Rice University, Department of Mathematical Sciences, Houston, Tex., 1987.
• 17: FLETCHER, R. A new approach to variable metric algorithms. Comput. J. 13 (1970), 317-322.
• 18: FLETCHER, R., AND POWELL, M. J.D. A rapidly convergent descent method for minimization. Comput. J. 6 (1963), 163-168.
• 19: Christina Fraley, Solution of nonlinear least-squares problems, 1987
• 20: GILL, P. E., AND MURRAY, W. Algorithms for the solution of the nonlinear least-squares problem. SIAM J. Numer. Anal. 15~ 5 (1978), 977-992.
• 21: GILL, P. E., MURRAY, W., AND WRIGHT, M.H. Practical Optimization. Academic Press, Orlando, Fla., 1981.
• 22: GILL, P. E., MURRAY, W., SAUNDERS, M. A., STEWART, G. W., AND WRIGHT, M.H. Properties of a representation of a basis for the null space. Math. Program. 33, 2 (1985), 172-186.
• 23: GOLDFARB, D. A family of variable metric updates derived by variational means. Math. Com put. 24 (1970), 23-26.
• 24: HAN, S.-P. Variable metric methods for minimizing a class of nondifferentiable functions. Math. Program. 20 (1981), 1-13.
• 25: Willi Hock , K. Schittkowski, Test Examples for Nonlinear Programming Codes, Springer-Verlag New York, Inc., Secaucus, NJ, 1981
• 26: Walter Murray , Michael L. Overton, Steplength algorithms for minimizing a class of nondifferentiable functions, Stanford University, Stanford, CA, 1978
• 27: NOCEDAL, J., AND OVERTON, M. L. Projected Hessian updating algorithms for nonlinearly constrained optimization. SIAM J. Numer. Anal. 22, 5 (1985), 821-850.
• 28: PIETRZYKOWSKI, T. An exact potential method for constrained maxima. SIAM J. Anal. 6 (1969), 299-304.
• 29: M J D Powell, How bad are the BFGS and DFP methods when the objective function is quadratic?, Mathematical Programming: Series A and B, v.34 n.1, p.34-47, Jan. 1986 [doi>10.1007/BF01582161]
• 30: SHANNO, D.F. Conditioning of quasi-Newton methods for function minimization. Mathematics of Computation 24 (1970), 647-656.
• 31: WEDIN, P-A. The nonlinear least squares problem from a numerical point of view. Technical Memoranda I and II, Lund University, Lund, Sweden, 1972.
• 32: WEDIN, P-~k. On the Gauss-Newton method for the non-linear least squares problem. ITM Arbetsrapport No. 24, Institute for Tellampad Matematik, Box 5073, Stockholm 5, Sweden, 1974.
• 33: WEDIN, P-~k. Oil surface dependent properties of methods for separable nonlinear least squares problems. ITM Arbetsrapport NO. 23, Institute for Tellampad Matematik, Box 5073, Stockholm, 5, Sweden, 1974.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

General Terms:
Algorithms