A quadratic-tensor model algorithm for nonlinear least-squares problems with linear constraints

ABSTRACT

A new algorithm is presented for solving nonlinear least-squares and nonlinear equation problems. The algorithm is based on approximating the nonlinear functions using the quadratic-tensor model proposed by Schnabel and Frank. The problem statement may include simple bounds or more general linear constraints on the unknowns. The algorithm uses a trust-region defined by a box containing the current values of the unknowns. The objective function (Euclidean length of the functions) is allowed to increase at intermediate steps. These increases are allowed as long as our predictor indicates that a new set of best values exists in the trust-region. There is logic provided to retreat to the current best values, should that be required. The computations for the model-problem require a constrained nonlinear least-squares solver. This is done using a simpler version of the algorithm. In its present form the algorithm is effective for problems with linear constraints and dense Jacobian matrices. Results on standard test problems are presented in the Appendix. The new algorithm appears to be efficient in terms of function and Jacobian evaluations.

REFERENCES

• 1: CHAMBERLAIN, R. M., POWELL, M. J. D., LEMERECHAL, C., AND PEDERSEN, H. C. The Watchdog technique for forcing convergence for constrained optimization. Math. Program Stud. 16 (1982), 1-17.
• 2: John E. Dennis, Jr. , David M. Gay , Roy E. Welsch, Algorithm 573: NL2SOL—An Adaptive Nonlinear Least-Squares Algorithm [E4], ACM Transactions on Mathematical Software (TOMS), v.7 n.3, p.369-383, Sept. 1981 [doi>10.1145/355958.355966]
• 3: DONGARRA, J. J., BUNCH, J. R., MOLER, C. B., AND STEWART, G. W. LINPACK Users' Guide. SIAM, Philadelphia, Pa., 1979.
• 4: Richard J Hanson, Linear least squares with bounds and liner constraints, SIAM Journal on Scientific and Statistical Computing, v.7 n.3, p.826-834, July 1986 [doi>10.1137/0907055]
• 5: HANSON, R. J., AND KROGH, F. T. Testing nonlinear }east squares system solvers using performance profiling. Available by writing either author, 1987.
• 6: KROGH, F. T. A Newton method subroutine for nonlinear least squares. In JPL-CIT Fortran V Subprogram Directory. Edition 5 (Feb. 1, 1975), 8.1-1.
• 7: LYNESS, J.N. Performance profiles and software evaluation. Argonne National Labs. Rep. TM 343, Aug. 1979.
• 8: Jorge J. Moré , Burton S. Garbow , Kenneth E. Hillstrom, Testing Unconstrained Optimization Software, ACM Transactions on Mathematical Software (TOMS), v.7 n.1, p.17-41, March 1981 [doi>10.1145/355934.355936]
• 9: MOR~, J.J. The Levenberg-Marquardt algorithm: Implementation and theory. In Numerical Analysis, G. A. Watson, Ed. Lecture Notes in Mathematics 630, Springer-Verlag, New York, 1977, 105-116.
• 10: SCHNABEL, R. B., AND FRANK, P. D. Tensor methods for nonlinear equations. SIAM J Numer. Anal. 2l, 5 (Oct. 1984), 815-843.
• 11: WRIGHT, S. J., AND HOLT, J. N. Algorithms for nonlinear least squares with linear inequality constraints. SlAM J. Sci. Stat. Comput. 6, 4 (Oct. 1985), 1033-1048.
• 12: I. S. Duff , J. Nocedal , J. K. Reid, The use of linear programming for the solution of sparse sets of nonlinear equations, SIAM Journal on Scientific and Statistical Computing, v.8 n.2, p.99-108, March 1, 1987 [doi>10.1137/0908024]
• 13: WEDIN, P.-~k. On the use of a quadratic merit function for constrained nonlinear least square. Rep. UMINF-135.87, Univ. of Ume~, S-9021 87 Ume~, Sweden.
• 14: LINDSTROM, P. Algorithms for nonlinear least squares--Particularly problems with constraints. UNINF406.83, Ph.D. dissertation, Univ. of Ume~, S-9021 87 Ume~, Sweden.
• 15: SCHITTKOWSKI, K. Solving constrained nonlinear least squares problems by a general-purpose SQP method. Rep., Institut f. Informatik, Univ. Stuttgart, Germany, 1985. o
• 16: WEDIN, P.-A., AND LINDSTROM, P. Methods and software for nonlinear least squares problems. Rep. UMINF-133,87, Univ. of Ume~, S-9021 87 Ume~, Sweden, 1988.
• 17: HILLS, R. G. ESTIM: A parameter estimation computer program Contractor Rep. SAND 87-7063, Sandia National Labs., Albuquerque, NM, 87185, Aug. 1987.
• 18: STEIN, C. L., AND McTIGuE, D.F. Chromium Distribution Beneath a Contaminated Site: A Case Study for Model Validation. In Proceedings of the International Conference and Workshop on the Validation of Flow and Transport Models for the Unsaturated Zone, (Ruidoso, N.M., May 23-26, 1988), pp. 392-400.
• 19: WANG, T.-C., STANFORD. R. C., SUNSERI, R. F., AND BRECKHEIMER, P.J. Survey of optimization techniques for nonlinear spacecraft trajectory searches. AIAA-88-4285-CP. In AIAA/AAS Astrodynamics Conference, (Minneapolis, Minn., Aug. 15-17, 1988), pp. 519-531.
• 20: Numerical Optimization Software Library Reference Manual. Division of Numerical Comput~ ing, National Physical Lab., England, 1978.
• 21: MAHDAvI-AMIRI, N., AND BARTELS, R. H. Constrained nonlinear least-squares: an exact penalty approach with structured quasi-Newton updates. Res. Rep. CS-86-10, Faculty of Mathematics, Univ. of Waterloo, Ontario, Mar. 1986.
• 22: DENNIS, J. E., JR., GAY, D. M., AND VU, P.A. A new nonlinear equations test problem. Rice Univ., Dept. of Mathematics Rep. 83-16, 1983, 1985.
• 23: Fred T Krogh, Making hard constraints soft, ACM SIGNUM Newsletter, v.22 n.1, p.11-11, Jan. 1987 [doi>10.1145/24680.24683]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Nonlinear programming

General Terms:
Algorithms, Performance

Keywords:
constrained least squares, nonlinear least-squares