Article Sidebar

Submitted
Apr 26, 2017
Published
Apr 1, 2012
Download
PDF
Statistic
Read Counter : 388 Download : 200

Main Article Content

Abstract

Recently, we have presented a projected structured algorithm for solving constrained nonlinear least squares problems, and established its local two-step Q-superlinear convergence. The approach is based on an adaptive structured scheme due to Mahdavi-Amiri and Bartels of the exact penalty method. The structured adaptation also makes use of the ideas of Nocedal and Overton for handling the quasi-Newton updates of projected Hessians and appropriates the structuring scheme of Dennis, Martinez and Tapia. Here, for robustness, we present a specific nonsmooth line search strategy, taking account of the least squares objective. We also discuss the details of our new nonsmooth line search strategy, implementation details of the algorithm, and provide comparative results obtained by the testing of our program and three nonlinear programming codes from KNITRO on test problems (both small and large residuals) from Hock and Schittkowski, Lukšan and Vlček and some randomly generated ones due to Bartels and Mahdavi-Amiri. The results indeed affirm the practical relevance of our special considerations for the inherent structure of the least squares.  

 

 

Keywords

Constrained nonlinear programming Exact penalty method Nonlinear least squares. Nonsmooth line search Projected structured Hessian update.

Article Details

References

  1. AL-BAALI, M. and FLETCHER, R., 1985. Variational methods for non-linear least squares. Journal of the Operational Research Society, 36: 405-421.
  2. ANITESCU, M., 2005. Global convergence of an elastic mode approach for a class of mathematical programs with complementarity constraints. SIAM J. Optim., 16(1): 120-145.
  3. BARTELS, R.H. and MAHDAVI-AMIRI, N., 1986. On generating test problems for nonlinear programming algorithms. SIAM Journal on Scientific and Statistical Computing, 7(3): 769-798.
  4. BENSON, H.Y., SEN, A., SHANNO, D.F. and VANDERBEI, R.J., 2006. Interior-point algorithms, penalty methods and equilibrium problems. Computational Optimization and Applications, 34(2): 155-182.
  5. BYRD, R.H., GOULD, N.I.M., NOCEDAL, J. and WALTZ, R.A., 2004. An algorithm for nonlinear optimization using linear programming and equality constrained subproblems. Math. Program. Series B, 100(1): 27-48.
  6. BYRD, R.H. and NOCEDAL, J., 1991. An analysis of reduced Hessian method for constrained optimization. Mathematical Programming, 49: 285-323.
  7. BYRD, R.H., NOCEDAL, J. and WALTZ, R.A., 2006. KNITRO: An integrated package for nonlinear optimization. In Large-Scale Nonlinear Optimization, eds G. Di Pillo and M. Roma, Springer, pp. 35-59.
  8. BYRD, R.H., NOCEDAL, J. and WALTZ, R.A., 2008. Steering exact penalty methods for nonlinear programming. Optimization Methods & Software, 23(2): 197-213.
  9. COLEMAN, T.F. and CONN, A.R., 1980. Second-order conditions for an exact penalty function. Math. Program., 19: 155-177.
  10. COLEMAN, T.F. and CONN, A.R., 1982a. Nonlinear programming via an exact penalty function: Asymptotic analysis. Mathematical Programming, 24: 123-136.
  11. COLEMAN, T.F. and CONN, A.R., 1982b. Nonlinear programming via an exact penalty function: Global analysis. Mathematical Programming, 24: 137-161.
  12. COLEMAN, T.F. and CONN, A.R., 1984. On the local convergence of a quasi-Newton method for the nonlinear programming problem. SIAM Journal on Numerical Analysis, 21: 755-769.
  13. CONN, A.R. and PIETRZYKOWSKI, T., 1977. A penalty function method converging directly to a constrained minimum. SIAM Journal on Numerical Analysis, 14: 348-375.
  14. DENNIS, Jr., J.E. 1977. Nonlinear least squares and equations. In The State of the Art of Numerical Analysis, eds D. Jacobs, Academic Press, Orlando, Florida, USA.
  15. DENNIS, Jr., J.E., GAY, D.M. and WELSCH, R.E., 1981. An adaptive nonlinear least squares algorithm. ACM Trans. Math. Soft., 7(3): 348-368.
  16. DENNIS, Jr., J.E., MARTINEZ, H.J. and TAPIA, R.A., 1989. A convergence theory for the structured BFGS secant method with an application to nonlinear least squares. Journal of Optimization Theory and Applications, 61: 161-178.
  17. DENNIS, Jr., J.E. and WALKER, H.F., 1981. Convergence theorems for least-changes secant update methods. SIAM. J. Numer. Anal., 18: 949-987.
  18. ENGELS, J.R. and MARTINEZ, H.J., 1991. Local and superlinear convergence for partially known quasi-Newton methods. SIAM Journal on Optimization, 1: 42-56.
  19. FANG, H.R. and O’LEARY, D.P., 2008. Modified Cholesky algorithm: A catalog with new approaches. Math. Program., 115(2): 319-349.
  20. FLETCHER, R., 1987. Practical Methods of Optimization. (2nd Edition) J. Wiley and Sons, Chichester, England.
  21. FLETCHER, R. and XU, C., 1987. Hybrid methods for nonlinear least squares. IMA Journal of Numerical Analysis, 7: 371-389.
  22. GILL, P.E. and MURRAY, W., 1978. Algorithms for the solution of the nonlinear least squares problem, SIAM J. Numer. Anal., 15(5): 977-992.
  23. GILL, P.E., MURRAY, W. and SAUNDERS, M.A., 2002. SNOPT: An SQP algorithm for large-scale constrained optimization. SIAM J. Optim., 12: 979-1006.
  24. GRIEWANK, A., 1987. On the iterative solution of differential and integral equation using secant updating techniques. In The State of the Art in Numerical Analysis, eds A. Iserles and M.J.D. Powell, Clarendon Press: 299-324.
  25. HOCK, H. and SCHITTKOWSKI, K., 1981. Test Examples for Nonlinear Programming Codes. Lecture Notes in Economic and Mathematical System No.187, Springer-Verlag, New York.
  26. HUSCHENS, J., 1993. Exploiting additional structure in equality constrained optimization by structured SQP secant algorithms. Journal of Optimization Theory and Applications, 77: 359-382.
  27. LEYFFER, S., L´OPEZ-CALVA, G. and NOCEDAL, J., 2006. Interior methods for mathematical programs with complementarity constraints. SIAM Journal on Optimization, 17(1): 52-77.
  28. LUENBERGER, D.G., 1970. Control problem with kinks. IEEE Transactions on Automatic Control, 15: 570-574.
  29. LUKŠAN, L. and VLČEK, J., 1999. Sparse and Partially Separable Test Problems for Unconstrained and Equality Constrained Optimization. Institute of Computer Science, Academy of Sciences of the Czech Republic, Technical Report 767.
  30. MAHDAVI-AMIRI, N. and ANSARI, M.R., 2011a. Superlinearly convergent exact penalty projected structured Hessian updating schemes for constrained nonlinear least squares: Asymptotic analysis. Bulletin of the Iranian Mathematical Society (accepted).
  31. MAHDAVI-AMIRI, N. and ANSARI, M.R., 2011b. Superlinearly convergent exact penalty projected structured Hessian updating schemes for constrained nonlinear least squares: Global analysis. Submitted.
  32. MAHDAVI-AMIRI, N. and BARTELS, R.H., 1989. Constrained nonlinear least squares: An exact penalty approach with projected structured quasi-Newton updates. ACM Transactions on Mathematical Software, 15(3): 220-242.
  33. MURRAY, W. and OVERTON, M.L., 1978. Steplength Algorithms for Minimizing a Class of Nondifferentiable Functions. STAN-CS-78-679, Stanford University, Stanford, California, USA.
  34. NOCEDAL, J. and OVERTON, M.L., 1985. Projected Hessian updating algorithms for nonlinearly constrained optimization. SIAM Journal on Numerical Analysis, 22(5): 821-850.
  35. PIETRZYKOWSKI, T., 1969. An exact potential method for constrained maxima. SIAM Journal on Numerical Analysis, 6: 299-304.
  36. TAPIA, R.A., 1988. On secant updates for use in general constrained optimization. Mathematical Computing, 51: 181-203.
  37. TJOA, I.B. and BIEGLER, L.T., 1991. Simultaneous solution and optimization strategies for parameter estimation of differential-algebraic equation systems. Industrial Engineering Chemical Research, 30: 376-385.