1887

Abstract

Summary

Although the Gauss-Newton trust-region sub-problem (GNTRS) solver using inverse-quadratic model (GNTRS-IQ) performs more efficiently than other direct solvers using matrix factorization and more robustly than available iterative solvers, it cannot compute the desired GN search step for many least-squares problems in which the Hessian is (near) singular. A popular approach to handle a singular matrix is to apply singular-value-decomposition (SVD). However, it is quite expensive to compute the SVD of a large matrix.

In this paper, we developed an integrated GNTRS solver by combining different methods together. For problems with a positive-definite Hessian, the GN search step is computed by solving a linear equation with N=min(Nd,Nm) unknowns, where Nd is the number of data and Nm the number of unknown parameters. Otherwise, we apply a linear transformation to reduce the dimension from Nm to r (the rank of Hessian) and then compute the GN step by solving a linear equation with r unknowns. When r=Nd< Nm, we use the sensitivity matrix J as the transformation matrix. When r is smaller than min(ND,Nm), we first compute the compact-SVD of J and then use the compact form of the right-singular matrix as the transformation matrix. For performance comparison, we also developed two GNTRS solvers using the traditional-SVD and compact-SVD formulation.

The three GNTRS solvers are validated and their performances are benchmarked on three sets of synthetic test problems. Each set contains 500 problems with different number of parameters and observed data. For small-scale and intermediate-scale problems, the solutions obtained by the three solvers have comparable accuracy. However, for large-scale problems, the solutions obtained by the solver using the traditional-SVD deviate from the solutions obtained by other solvers with unacceptably large errors. The integrated GNTRS solver performs most efficiently, and it can reduce the CPU time by a factor ranging from 1 to 173 and from 1 to 14585 when compared to the two solvers using the compact- and traditional-SVD. Our numerical tests confirm that the integrated GNTRS solver is efficient, robust, and applicable to least squares problems with singular Hessian. Finally, we applied the newly developed GN trust region search optimization method using the integrated GNTRS solver to a Gaussian-Mixture-Model (GMM) fitting problem. Compared with the one using the old version GNTRS-IQ solver, the new optimizer can reduce the CPU time used to construct an acceptable GMM by a factor of 8.

Loading

Article metrics loading...

/content/papers/10.3997/2214-4609.202035136
2020-09-14
2024-03-29
Loading full text...

Full text loading...

References

  1. [1]Brust, J., Erway, J.B. and Marcia, R.F.On Solving L-SR1 Trust-Region Subproblems.Computational Optimization and Applications, 9(1): 101–134, 2017.
    [Google Scholar]
  2. [2]Burdakov, O., Gong, L., Zikrin, S. and Yuan, Y.On Efficiently Combining Limited-Memory and Trust-Region Techniques.Mathematical Programming Computation, 66(2): 245–266, 2017.
    [Google Scholar]
  3. [3]Ding, Y., Lushi, E. and Li, Q.Investigation of Quasi-Newton methods for Unconstrained Optimization. (http://people.math.sfu.ca/∼elushi/project_833.pdf), Simon Fraser University, Canada, 2004.
    [Google Scholar]
  4. [4]Dolan, E.D. and More, J.J.Benchmarking Optimization Software with Performance Profiles.Mathematical Programming, 91(2): 201–213, 2002.
    [Google Scholar]
  5. [5]Erway, J.B., Gill, P.E. and Griffin, J.D.Iterative Methods for Finding a Trust-Region Step.SIAM J. Optim., 20(2): 1110–1131, 2009.
    [Google Scholar]
  6. [6]Gao, G.Gao, G. et al.A Parallelized and Hybrid Data-Integration Algorithm for History Matching of Geologically Complex Reservoirs.SPE J., 21(6): 2155–2174, 2016.
    [Google Scholar]
  7. [7]Gao, G., et al.Distributed Gauss-Newton Optimization Method for History Matching Problems with Multiple Best Matches.Computational Geosciences, 21(5–6): 1325–1342, 2017a.
    [Google Scholar]
  8. [8]Gao, G. et al.A Gauss-Newton Trust Region Solver for Large Scale History Matching Problems.SPE J, 22(6), December 2017b (DOI: http://dx.doi.org/10.2118/182602-PA).
    [Google Scholar]
  9. [9]Gao, et al.Gaussian Mixture Model Fitting Method for Uncertainty Quantification by Conditioning to Production Data.Computational Geosciences (published online), June 2019a.
    [Google Scholar]
  10. [10]Gao, et al.Performance Enhancement of Gauss-Newton Trust Region Solver for Distributed Gauss-Newton Optimization methods.Computational Geosciences (published online), June 2019b.
    [Google Scholar]
  11. [11]Gao, et al.Reduced-Degrees-of-Freedom Gaussian-Mixture-Model Fitting Method for Large-Scale History-Matching Problems.SPE J. (published online), September 2019c.
    [Google Scholar]
  12. [12]Gould, N.I.M., et al.Solving the Trust-Region Subproblem Using the Lanczos Method.SIAM J. Optim., 9(2): 504–525, 1999.
    [Google Scholar]
  13. [13]Gould, N.I.M., Orban, D., and Toint, Ph. L.GALAHAD, a library of thread-safe Fortran 90 packages for large-scale nonlinear optimization.ACM Trans. Math. Software, 29(4): 353–372, 2004.
    [Google Scholar]
  14. [14]Gould, N.I.M., Robinson, D. and Thorne, H.S.On Solving Trust-Region and Other Regularized Subproblems in Optimization, Math. Prog. Comp., 2(1): 21–57, 2010.
    [Google Scholar]
  15. [15]Jansen, J.D.Adjoint-based Optimization of Multi-phase Flow through Porous Media—A Review.Computers & Fluids, 46(1): 40–51, 2011.
    [Google Scholar]
  16. [16]Levenberg, K.A Method for the Solution of Certain Non-Linear Problems in Least Squares.Quarterly of Applied Mathematics.2(2): 164–168, 1944.
    [Google Scholar]
  17. [17]Li, R., Reynolds, A.C. and Oliver, D.S.History Matching of Three-Phase Flow Production Data.SPE J., 8(4), 2003.
    [Google Scholar]
  18. [18]Marquardt, D.An Algorithm for Least-Squares Estimation of Nonlinear Parameters.SIAM Journal on Applied Mathematics, 11(2): 431–441, 1963.
    [Google Scholar]
  19. [19]More, J.J. and Sorensen, D.C.Computing a Trust Region Step, SIAM Journal, on Scientific and Statistical Computing, 4(3): 553–572, 1983.
    [Google Scholar]
  20. [20]Nocedal, J. and Wright, S.J.Numerical Optimization. Springer, New York City, 1999.
    [Google Scholar]
  21. [21]Oliver, D.S. and Chen, Y.Recent Progress on Reservoir History Matching: a Review.Computational Geoscience, 15(1):185 – 211, 2011.
    [Google Scholar]
  22. [22]Oliver, D.S., Reynolds, A.C., and Liu. Inverse Theory for Petroleum Reservoir Characterization and History Matching.Cambridge University Press, 2008.
    [Google Scholar]
  23. [23]Rojas, M., Santos, S.A. and Sorensen, D.C.Algorithm 873: LSTRS: MATLAB Software for Large-Scale Trust-Region Subproblems and Regularization.ACM Trans. Math. Software.34(2): 1–28, 2008.
    [Google Scholar]
  24. [24]Sturler, E.D. and Kilmer, M.E.A Regularized Gauss-Newton Trust Region Approach to Imaging in Diffuse Optical Tomography.SIAM J. Sci. Compt.33(5): 3057–3086, 2011.
    [Google Scholar]
  25. [25]Tarantola, A.Inverse Problem Theory and Methods for Model Parameter Estimation. SIAM. 2005.
    [Google Scholar]
  26. [26]Volkov, O. and Voskov, D.Effect of time stepping strategy on adjoint-based production optimization.Computational Geosciences, 20(3): 707–722, 2016.
    [Google Scholar]
  27. [27]Zhou, W. and Zhang, L.Global Convergence of a Regularized Factorized Quasi-Newton Method for Nonlinear Least Squares Problems.Computational & Applied Mathematics, 29(2): 195–214, 2010.
    [Google Scholar]
http://instance.metastore.ingenta.com/content/papers/10.3997/2214-4609.202035136
Loading
/content/papers/10.3997/2214-4609.202035136
Loading

Data & Media loading...

This is a required field
Please enter a valid email address
Approval was a Success
Invalid data
An Error Occurred
Approval was partially successful, following selected items could not be processed due to error