×

zbMATH — the first resource for mathematics

Secant update version of quasi-Newton PSB with weighted multisecant equations. (English) Zbl 1433.90191
Summary: Quasi-Newton methods are often used in the frame of non-linear optimization. In those methods, the quality and cost of the estimate of the Hessian matrix has a major influence on the efficiency of the optimization algorithm, which has a huge impact for computationally costly problems. One strategy to create a more accurate estimate of the Hessian consists in maximizing the use of available information during this computation. This is done by combining different characteristics. The Powell-Symmetric-Broyden method (PSB) imposes, for example, the satisfaction of the last secant equation, which is called secant update property, and the symmetry of the Hessian [M. J. D. Powell, in: Nonlinear Programming, Proc. Sympos. Math. Res. Center, Univ. Wisconsin, Madison31–65 (1970; Zbl 0228.90043)]. Imposing the satisfaction of more secant equations should be the next step to include more information into the Hessian. However, Schnabel proved that this is impossible (Schnabel in quasi-Newton methods using multiple secant equations, 1983). Penalized PSB (pPSB), works around the impossibility by giving a symmetric Hessian and penalizing the non-satisfaction of the multiple secant equations by using weight factors [S. Gratton et al., Optim. Methods Softw. 30, No. 4, 748–755 (2015; Zbl 1356.90162)]. Doing so, he loses the secant update property. In this paper, we combine the properties of PSB and pPSB by adding to pPSB the secant update property. This gives us the secant update penalized PSB (SUpPSB). This new formula that we propose also avoids matrix inversions, which makes it easier to compute. Next to that, SUpPSB also performs globally better compared to pPSB.

MSC:
90C53 Methods of quasi-Newton type
49M15 Newton-type methods
65H10 Numerical computation of solutions to systems of equations
90C26 Nonconvex programming, global optimization
Software:
KELLEY; minpack
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Ahookhosh, M.; Ghaderi, S., On efficiency of nonmonotone Armijo-type line searches, Appl. Math. Model., 43, 170-190 (2017) · Zbl 1446.65030
[2] Armijo, L., Minimization of functions having Lipschitz continuous first partial derivatives, Pac. J. Math., 16, 1, 1-3 (1966) · Zbl 0202.46105
[3] Bartels, Rh; Stewart, Gw, Solution of the matrix equation AX + XB = C [F4], Commun. ACM, 15, 9, 820-826 (1972) · Zbl 1372.65121
[4] Broyden, C., On the discovery of the “good Broyden” method, Math. Program., 87, 2, 209-213 (2000) · Zbl 0970.90002
[5] Broyden, Cg, A class of methods for solving nonlinear simultaneous equations, Math. Comput., 19, 92, 577-593 (1965) · Zbl 0131.13905
[6] Broyden, Cg, Quasi-Newton methods and their application to function minimisation, Math. Comput., 21, 99, 368-381 (1967) · Zbl 0155.46704
[7] Chen, C.; Luo, L.; Han, C.; Chen, Y., Global convergence of an extended descent algorithm without line search for unconstrained optimization, Parameters, 1, 2 (2018)
[8] Degroote, J.; Bathe, Kj; Vierendeels, J., Performance of a new partitioned procedure versus a monolithic procedure in fluid-structure interaction, Comput. Struct., 87, 11-12, 793-801 (2009)
[9] Degroote, J.; Hojjat, M.; Stavropoulou, E.; Wüchner, R.; Bletzinger, Ku, Partitioned solution of an unsteady adjoint for strongly coupled fluid-structure interactions and application to parameter identification of a one-dimensional problem, Struct. Multidiscip. Optim., 47, 1, 77-94 (2013) · Zbl 1274.74103
[10] Ding, Y.; Lushi, E.; Li, Q., Investigation of Quasi-Newton Methods for Unconstrained Optimization (2004), Burnaby: Simon Fraser University, Burnaby
[11] Dolan, Ed; Moré, Jj, Benchmarking optimization software with performance profiles, Math. Program., 91, 2, 201-213 (2002) · Zbl 1049.90004
[12] Errico, Rm, What is an adjoint model?, Bull. Am. Meteorol. Soc., 78, 11, 2577-2591 (1997)
[13] Gratton, S.; Malmedy, V.; Toint, Pl, Quasi-Newton updates with weighted secant equations, Optim. Methods Softw., 30, 4, 748-755 (2015) · Zbl 1356.90162
[14] Haelterman, R.: Analytical study of the least squares quasi-Newton method for interaction problems. Ph.D. thesis, Ghent University (2009)
[15] Haelterman, R.; Bogaers, A.; Degroote, J.; Boutet, N., Quasi-Newton methods for the acceleration of multi-physics codes, IAENG Int. J. Appl. Math., 47, 3, 352-360 (2017)
[16] Jarlebring, E.: KTH royal institute of technology in Stockholm, lecture notes: numerical methods for Lyapunov equations. https://people.kth.se/ eliasj/NLA/matrixeqs.pdf. Last visited on 07 Jan 2018
[17] Kelley, Ct, Iterative Methods for Optimization (1999), Raleigh: SIAM, Raleigh
[18] Moré, Jj; Garbow, Bs; Hillstrom, Ke, Testing unconstrained optimization software, ACM Trans. Math. Softw. (TOMS), 7, 1, 17-41 (1981) · Zbl 0454.65049
[19] Neumaier, A.: Universität Wien, Personnal Webpage: Global Optimization Test Problems.http://www.mat.univie.ac.at/ neum/glopt/test.html and http://www.mat.univie.ac.at/ neum/glopt/bounds.html. Last visited on 04 Feb 2018
[20] Patelli, E.; Pradlwarter, Hj, Monte Carlo gradient estimation in high dimensions, Int. J. Numer. Methods Eng., 81, 2, 172-188 (2010) · Zbl 1183.65078
[21] Plessix, Re, A review of the adjoint-state method for computing the gradient of a functional with geophysical applications, Geophys. J. Int., 167, 2, 495-503 (2006)
[22] Powell, M.J.D.: A new algorithm for unconstrained optimization. In: Nonlinear Programming, pp. 31-65. Elsevier (1970)
[23] Rheinboldt, W.C.: University of Pittsburgh, Lecture Notes: Quasi-Newton Methods. Url: https://www-m2.ma.tum.de/foswiki/pub/M2/Allgemeines/SemWs09/quasi-newt.pdf. Last visited on 07 Jan 2018
[24] Ruiz, D.: A scaling algorithm to equilibrate both rows and columns norms in matrices. Technical report, CM-P00040415 (2001)
[25] Schnabel, R.B.: Quasi-Newton Methods Using Multiple Secant Equations. Technical report, DTIC Document (1983)
[26] Zhang, J.; Xu, C., Properties and numerical performance of quasi-Newton methods with modified quasi-Newton equations, J. Comput. Appl. Math., 137, 2, 269-278 (2001) · Zbl 1001.65065
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.