×

A reduced-space line-search method for unconstrained optimization via random descent directions. (English) Zbl 1428.90136

Summary: In this paper, we propose an iterative method based on reduced-space approximations for unconstrained optimization problems. The method works as follows: among iterations, samples are taken about the current solution by using, for instance, a Normal distribution; for all samples, gradients are computed (approximated) in order to build reduced-spaces onto which descent directions of cost functions are estimated. By using such directions, intermediate solutions are updated. The overall process is repeated until some stopping criterion is satisfied. The convergence of the proposed method is theoretically proven by using classic assumptions in the line search context. Experimental tests are performed by using well-known benchmark optimization problems and a non-linear data assimilation problem. The results reveal that, as the number of sample points increase, gradient norms go faster towards zero and even more, in the data assimilation context, error norms are decreased by several order of magnitudes with regard to prior errors when the assimilation step is performed by means of the proposed formulation.

MSC:

90C26 Nonconvex programming, global optimization
49K10 Optimality conditions for free problems in two or more independent variables
49M05 Numerical methods based on necessary conditions
49M15 Newton-type methods
65K05 Numerical mathematical programming methods

Software:

EnKF-MC; GQTPAR; L-BFGS
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Asch, M.; Bocquet, M.; Nodet, M., Data Assimilation: Methods, Algorithms, and Applications, 11 (2016), SIAM · Zbl 1361.93001
[2] Nino-Ruiz, E. D.; Sandu, A.; Deng, X., An ensemble Kalman filter implementation based on modified Cholesky decomposition for inverse covariance matrix estimation, SIAM J. Sci. Comp., 40, 2, A867-A886 (2018) · Zbl 1454.62278
[3] Nino-Ruiz, E. D.; Ardila, C.; Capacho, R., Local search methods for the solution of implicit inverse problems, Soft Comput., 22, 1-14 (2017)
[4] Vanderplaats, G. N., Numerical Optimization Techniques for Engineering Design: With Applications, 1 (1984), McGraw-Hill New York · Zbl 0613.90062
[5] Wright, S.; Nocedal, J., Numerical Optimization, 35, 7 (1999), Springer Science · Zbl 0930.65067
[6] Savard, G.; Gauvin, J., The steepest descent direction for the nonlinear bilevel programming problem, Oper. Res. Lett., 15, 5, 265-272 (1994) · Zbl 0816.90122
[7] Hager, W. W.; Zhang, H., A survey of nonlinear conjugate gradient methods, Pac. J. Optim., 2, 1, 35-58 (2006) · Zbl 1117.90048
[8] Fletcher, R.; Reeves, C. M., Function minimization by conjugate gradients, Comput. J., 7, 2, 149-154 (1964) · Zbl 0132.11701
[9] Lewis, R. M.; Torczon, V.; Trosset, M. W., Direct search methods: then and now, J. Comput. Appl. Math., 124, 1-2, 191-207 (2000) · Zbl 0969.65055
[10] Battiti, R., First-and second-order methods for learning: between steepest descent and Newton’s method, Neural Comput., 4, 2, 141-166 (1992)
[11] Grippo, L.; Lampariello, F.; Lucidi, S., A truncated newton method with nonmonotone line search for unconstrained optimization, J. Optim. Theory Appl., 60, 3, 401-419 (1989) · Zbl 0632.90059
[12] Pan, V. Y.; Branham, S.; Rosholt, R. E.; Zheng, A.-L., Newton’s iteration for structured matrices, Fast Reliable Algorithms for Matrices with Structure, 189-210 (1999), SIAM
[13] Shanno, D. F., Conditioning of quasi-newton methods for function minimization, Math. Comput., 24, 111, 647-656 (1970) · Zbl 0225.65073
[14] Nocedal, J., Updating quasi-newton matrices with limited storage, Math. Comput., 35, 151, 773-782 (1980) · Zbl 0464.65037
[15] Loke, M. H.; Barker, R., Rapid least-squares inversion of apparent resistivity pseudosections by a quasi-newton method, Geophys. Prospect., 44, 1, 131-152 (1996)
[16] Knoll, D. A.; Keyes, D. E., Jacobian-free newton-krylov methods: a survey of approaches and applications, J. Comput. Phys., 193, 2, 357-397 (2004) · Zbl 1036.65045
[17] Cervantes, A. M.; Wächter, A.; Tütüncü, R. H.; Biegler, L. T., A reduced space interior point strategy for optimization of differential algebraic systems, Comput. Chem. Eng., 24, 1, 39-51 (2000)
[18] Epperly, T. G.; Pistikopoulos, E. N., A reduced space branch and bound algorithm for global optimization, J. Global Optim., 11, 3, 287-311 (1997) · Zbl 1040.90567
[19] Logsdon, J. S.; Biegler, L. T., A relaxed reduced space sqp strategy for dynamic optimization problems, Comput. Chem. Eng., 17, 4, 367-372 (1993)
[20] Grippo, L.; Lampariello, F.; Lucidi, S., A nonmonotone line search technique for Newtons method, SIAM J. Numer. Anal., 23, 4, 707-716 (1986) · Zbl 0616.65067
[21] Uschmajew, A.; Vandereycken, B., Line-search methods and rank increase on low-rank matrix varieties, Proceedings of the 2014 International Symposium on Nonlinear Theory and its Applications (NOLTA2014), 52-55 (2014)
[22] Hosseini, S.; Huang, W.; Yousefpour, R., Line search algorithms for locally Lipschitz functions on Riemannian manifolds, SIAM J. Optim., 28, 1, 596-619 (2018) · Zbl 1387.49019
[23] Conn, A. R.; Gould, N. I.; Toint, P. L., Trust Region Methods, 1 (2000), Siam · Zbl 0958.65071
[24] Moré, J. J.; Sorensen, D. C., Computing a trust region step, SIAM J. Sci. Stat. Comput., 4, 3, 553-572 (1983) · Zbl 0551.65042
[25] Curtis, F. E.; Robinson, D. P.; Samadi, M., A trust region algorithm with a worst-case iteration complexity of \(O(\epsilon^{- 3 / 2})\) for nonconvex optimization, Math. Prog., 162, 1-2, 1-32 (2017) · Zbl 1360.49020
[26] Shi, Z.-J., Convergence of line search methods for unconstrained optimization, Appl. Math. Comput., 157, 2, 393-405 (2004) · Zbl 1072.65087
[27] Zhou, W.; Akrotirianakis, I.; Yektamaram, S.; Griffin, J., A matrix-free line-search algorithm for nonconvex optimization, Optim. Methods Softw., 1-24 (2017) · Zbl 1416.90023
[28] Byrd, R. H.; Nocedal, J.; Schnabel, R. B., Representations of quasi-newton matrices and their use in limited memory methods, Math. Prog., 63, 1-3, 129-156 (1994) · Zbl 0809.90116
[29] Pozrikidis, C., Numerical Computation in Science and Engineering, 6 (1998), Oxford University Press: Oxford University Press New York · Zbl 0971.65001
[30] Hager, W. W., Updating the inverse of a matrix, SIAM Rev., 31, 2, 221-239 (1989) · Zbl 0671.65018
[31] Yamashita, N., Sparse quasi-newton updates with positive definite matrix completion, Math. Prog., 115, 1, 1-30 (2008) · Zbl 1151.90059
[32] Goldfarb, D., Matrix factorizations in optimization of nonlinear functions subject to linear constraints, Math. Prog., 10, 1, 1-31 (1976) · Zbl 0374.90060
[33] Li, X.; Tang, K.; Omidvar, M. N.; Yang, Z.; Qin, K.; China, H., Benchmark functions for the CEC 2013 special session and competition on large-scale global optimization, Gene, 7, 33, 8 (2013)
[34] Tang, K.; Yáo, X.; Suganthan, P. N.; MacNish, C.; Chen, Y.-P.; Chen, C.-M.; Yang, Z., Benchmark Functions for the CEC 2008 Special Session and Competition on Large Scale Global Optimization, 24 (2007)
[35] Golub, G. H.; Hansen, P. C.; O’Leary, D. P., Tikhonov regularization and total least squares, SIAM J. Matrix Anal. Appl., 21, 1, 185-194 (1999) · Zbl 0945.65042
[36] Honerkamp, J.; Weese, J., Tikhonovs regularization method for ill-posed problems, Contin. Mech. Thermodyn., 2, 1, 17-30 (1990) · Zbl 0825.76669
[37] Natterer, F., Error bounds for tikhonov regularization in hilbert scales, Appl. Anal., 18, 1-2, 29-37 (1984) · Zbl 0504.65031
[38] Hansen, P. C., Truncated singular value decomposition solutions to discrete ill-posed problems with ill-determined numerical rank, SIAM J. Sci. Stat. Comput., 11, 3, 503-518 (1990) · Zbl 0699.65029
[39] Chan, T. F.; Hansen, P. C., Computing truncated singular value decomposition least squares solutions by rank revealing qr-factorizations, SIAM J. Sci. Stat. Comput., 11, 3, 519-530 (1990) · Zbl 0699.65030
[40] Brand, M., Incremental singular value decomposition of uncertain data with missing values, Proceedings of the European Conference on Computer Vision, 707-720 (2002), Springer · Zbl 1034.68580
[41] Ruiz, E. D.N.; Sandu, A.; Anderson, J., An efficient implementation of the ensemble Kalman filter based on an iterative Sherman-morrison formula, Stat. Comput., 25, 3, 561-577 (2015) · Zbl 1331.62357
[42] Ruiz, E. D.N.; Sandu, A., A derivative-free trust region framework for variational data assimilation, J. Comput. Appl. Math., 293, 164-179 (2016) · Zbl 1326.65070
[43] Nino-Ruiz, E. D.; Sandu, A., Ensemble kalman filter implementations based on shrinkage covariance matrix estimation, Ocean Dyn., 65, 11, 1423-1439 (2015)
[44] Nino-Ruiz, E. D.; Sandu, A.; Deng, X., A parallel implementation of the ensemble Kalman filter based on modified Cholesky decomposition, J. Comput. Sci. (2017)
[45] Nino-Ruiz, E. D.; Sandu, A., Efficient parallel implementation of DDDAS inference using an ensemble Kalman filter with shrinkage covariance matrix estimation, Cluster Comput., 1-11 (2017)
[46] Nino-Ruiz, E. D., A matrix-free posterior ensemble Kalman filter implementation based on a modified Cholesky decomposition, Atmosphere, 8, 7, 125 (2017)
[47] Nino-Ruiz, E. D.; Cheng, H.; Beltran, R., A robust non-gaussian data assimilation method for highly non-linear models, Atmosphere, 9, 4, 126 (2018)
[48] Gottwald, G. A.; Melbourne, I., Testing for chaos in deterministic systems with noise, Phys. D Nonlinear Phenom., 212, 1-2, 100-110 (2005) · Zbl 1097.37024
[49] Karimi, A.; Paul, M. R., Extensive chaos in the lorenz-96 model, Chaos Interdiscip. J. Nonlinear Sci., 20, 4, 043105 (2010)
[50] Wilks, D. S., Comparison of ensemble-mos methods in the lorenz’96 setting, Meteorol. Appl., 13, 3, 243-256 (2006)
[51] Fertig, E. J.; Harlim, J.; Hunt, B. R., A comparative study of 4d-var and a 4d ensemble Kalman filter: perfect model simulations with lorenz-96, Tellus A, 59, 1, 96-100 (2007)
[52] Van Leeuwen, P. J.; Cheng, Y.; Reich, S., Nonlinear Data Assimilation, 2 (2015), Springer · Zbl 1330.62004
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.