Abstract
We present an algorithm, partitioning group correction (PGC) algorithm based on trust region and conjugate gradient method, for large-scale sparse unconstrained optimization. In large sparse optimization, computing the whole Hessian matrix and solving the Newton-like equations at each iteration can be considerably expensive when a trust region method is adopted. The method depends on a symmetric consistent partition of the columns of the Hessian matrix and an inaccurate solution to the Newton-like equations by conjugate gradient method. And we allow that the current direction exceeds the trust region bound if it is a good descent direction. Besides, we studies a method dealing with some sparse matrices having a dense structure part. Some good convergence properties are kept and we contrast the computational behavior of our method with that of other algorithms. Our numerical tests show that the algorithm is promising and quite effective, and that its performance is comparable to or better than that of other algorithms available.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Coleman, T.F., Moré, J.J.: Estimation of sparse Hessian matrices and graph coloring problems. Math. Program. 28, 243–270 (1984)
Coleman, T.F., Moré, J.J.: Software for estimation of sparse Hessian matrices. ACM Trans. Math. Softw. 11, 363–377 (1985)
Dembo, R.S., Steihaug, T.: Truncated-Newton algorithms for large-scale unconstrained optimization. Math. Program. 26, 190–212 (1983)
Dembo, R.S., Eisenstat, S.C., Steihaug, T.: Inexact Newton methods. SIAM J. Numer. Anal. 19, 400–408 (1982)
Dennis, J.E. Jr., Mei, H.H.W.: Two new unconstrained optimization algorithms which use function and gradient values. J. Optim. Theory Appl. 28, 453–482 (1979)
Dennis, J.E. Jr., Schnabel, R.B.: Numerical Methods for Unconstrained Optimization and Nonlinear Equations. Society for Industrial and Applied Mathematics, Philadelphia (1996)
Dennis, J.E. Jr., Steihaug, T.: On the successive projections approach to least-squares problems. SIAM J. Numer. Anal. 23, 717–733 (1986)
Feng, G.C.: Iterative Solution Methods for Systems of Nonlinear Equations. Shanghai Science and Technology, Shanghai (1989) (in Chinese)
Griewank, A., Corliss, G.F.: Automatic Differentiation of Algorithms: Theory, Implementation, and Application. SIAM, Philadelphia (1991)
Harrison, J.M., Zeevi, A.: A method for staffing large call centers based on stochastic fluid models. Manuf. Serv. Oper. Manag. 7, 20–36 (2005)
Hebden, M.D.: An algorithm for minimization using exact second derivatives. Tech. Rep. T.P. 515, A.E.R.E., Theoretical Physics Division, Harwell, Berkshire, England (1973)
Li, G.Y.: Successive element correction algorithms for sparse unconstrained optimization. J. Optim. Theory Appl. 77, 523–543 (1993)
Li, J.X.: Numerical methods for large scale sparse minimax problems. Ph.D. Dissertation, Dalian University of Technology, Dalian, China (2008)
Li, J.X., Zhang, H.W.: On the convergence of partitioning group correction algorithms. Appl. Math. Comput. 186, 365–378 (2007)
Li, J.X., Yu, B.: Truncated partitioning group correction algorithms for large scale sparse unconstrained optimization. Appl. Math. Comput. 190, 242–254 (2007)
Moré, J.J.: The Levenberg-Marquardt algorithm: implementation and theory. In: Watson, G.A. (ed.) Numerical Analysis, Proceedings, Biennial Conference, Dundee, 1977. Lecture Notes in Mathematics, vol. 630, pp. 105–132. Springer, New York (1978)
Moré, J.J., Sorensen, D.C.: Computing a trust region step. SIAM J. Sci. Stat. Comput. 4, 553–572 (1983)
Nocedal, J., Yuan, Y.: Combining trust region and line search techniques. In: Yuan, Y. (ed.) Advances in Nonlinear Programming, pp. 153–175. Kluwer Academic, Norwell (1998)
Nocedal, J., Wright, S.J.: Numerical Optimization. Springer, New York (1999)
Powell, M.J.D.: A new algorithm for unconstrained optimization. In: Rosen, J.B., Mangasarian, O.L., Ritter, K. (eds.) Nonlinear Programming, pp. 31–65. Academic Press, New York (1970)
Powell, M.J.D.: Convergence properties of a class of minimization algorithms. In: Mangasarian, O.L., Meyer, R.R., Robinson, S.M. (eds.) Nonlinear Programming 2, pp. 1–27. Academic Press, New York (1975)
Powell, M.J.D., Toint, Ph.L.: On the estimation of sparse Hessian matrices. SIAM J. Numer. Anal. 16, 1060–1074 (1979)
Steihaug, T.: The conjugate gradient method and trust regions in large scale optimization. SIAM J. Numer. Anal. 20, 626–637 (1983)
Wang, Y.F., Yuan, Y.X., Zhang, H.C.: A trust region-CG algorithm for deblurring problem in atmospheric image reconstruction. Sci. China Ser. A 45, 731–740 (2002)
Wen, Z.W., Wang, Y.F.: A new trust region algorithm for image restoration. Sci. China Ser. A 48, 169–184 (2005)
Wolfram, S.: The Mathematica Book, 3rd edn. Cambridge University Press/Wolfram Media, Cambridge (1996)
Yuan, Y.X., Sun, W.Y.: Optimization Theorem and Methods. Science Press, Beijing (2001)
Author information
Authors and Affiliations
Corresponding author
Additional information
This research was supported by the Key Program of National Natural Science Foundation of China (No. 70832005), Program of Shanghai Subject Chief Scientist (No. 10XD1404300) and China Postdoctoral Science Foundation (No. 20100470731).
Rights and permissions
About this article
Cite this article
Li, J., Yan, L., Li, S. et al. Inexact trust region PGC method for large sparse unconstrained optimization. Comput Optim Appl 51, 981–999 (2012). https://doi.org/10.1007/s10589-010-9381-z
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10589-010-9381-z