{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:25:54Z","timestamp":1740122754802,"version":"3.37.3"},"reference-count":15,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2020,11,9]],"date-time":"2020-11-09T00:00:00Z","timestamp":1604880000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,11,9]],"date-time":"2020-11-09T00:00:00Z","timestamp":1604880000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Justus-Liebig-Universit\u00e4t Gie\u00dfen"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Comput Optim Appl"],"published-print":{"date-parts":[[2021,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We consider Broyden class updates for large scale optimization problems in <jats:italic>n<\/jats:italic> dimensions, restricting attention to the case when the initial second derivative approximation is the identity matrix. Under this assumption we present an implementation of the Broyden class based on a coordinate transformation on each iteration. It requires only <jats:inline-formula><jats:alternatives><jats:tex-math>$$2nk + O(k^{2}) + O(n)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mn>2<\/mml:mn>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mi>k<\/mml:mi>\n                    <mml:mo>+<\/mml:mo>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mrow>\n                      <mml:mo>(<\/mml:mo>\n                      <mml:msup>\n                        <mml:mi>k<\/mml:mi>\n                        <mml:mn>2<\/mml:mn>\n                      <\/mml:msup>\n                      <mml:mo>)<\/mml:mo>\n                    <\/mml:mrow>\n                    <mml:mo>+<\/mml:mo>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mrow>\n                      <mml:mo>(<\/mml:mo>\n                      <mml:mi>n<\/mml:mi>\n                      <mml:mo>)<\/mml:mo>\n                    <\/mml:mrow>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> multiplications on the <jats:italic>k<\/jats:italic>th iteration and stores <jats:inline-formula><jats:alternatives><jats:tex-math>$$nK+ O(K^2) + O(n)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mi>K<\/mml:mi>\n                    <mml:mo>+<\/mml:mo>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mrow>\n                      <mml:mo>(<\/mml:mo>\n                      <mml:msup>\n                        <mml:mi>K<\/mml:mi>\n                        <mml:mn>2<\/mml:mn>\n                      <\/mml:msup>\n                      <mml:mo>)<\/mml:mo>\n                    <\/mml:mrow>\n                    <mml:mo>+<\/mml:mo>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mrow>\n                      <mml:mo>(<\/mml:mo>\n                      <mml:mi>n<\/mml:mi>\n                      <mml:mo>)<\/mml:mo>\n                    <\/mml:mrow>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> numbers, where <jats:italic>K<\/jats:italic> is the total number of iterations. We investigate a modification of this algorithm by a scaling approach and show a substantial improvement in performance over the BFGS method. We also study several adaptations of the new implementation to the limited memory situation, presenting algorithms that work with a fixed amount of storage independent of the number of iterations. We show that one such algorithm retains the property of quadratic termination. The practical performance of the new methods is compared with the performance of Nocedal\u2019s (Math Comput 35:773--782, 1980) method, which is considered the benchmark in limited memory algorithms. The tests show that the new algorithms can be significantly more efficient than Nocedal\u2019s method. Finally, we show how a scaling technique can significantly improve both Nocedal\u2019s method and the new generalized conjugate gradient algorithm.<\/jats:p>","DOI":"10.1007\/s10589-020-00239-2","type":"journal-article","created":{"date-parts":[[2020,11,9]],"date-time":"2020-11-09T16:06:28Z","timestamp":1604937988000},"page":"181-203","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Implementing and modifying Broyden class updates for large scale optimization"],"prefix":"10.1007","volume":"78","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3313-4561","authenticated-orcid":false,"given":"Martin","family":"Buhmann","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dirk","family":"Siegel","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,11,9]]},"reference":[{"key":"239_CR1","doi-asserted-by":"publisher","first-page":"937","DOI":"10.1080\/10556788.2013.856909","volume":"29","author":"M Al-Baali","year":"2014","unstructured":"Al-Baali, M., Spedicato, E., Maggioni, F.: Broyden\u2019s quasi-Newton methods for a nonlinear system of equations and unconstrained optimization: a review and open problems. Optim. Methods Softw. 29, 937\u2013954 (2014)","journal-title":"Optim. Methods Softw."},{"key":"239_CR2","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1093\/comjnl\/6.2.163","volume":"6","author":"R Fletcher","year":"1963","unstructured":"Fletcher, R., Powell, M.J.D.: A rapidly convergent descent method for minimization. Comput. J. 6, 163\u2013168 (1963)","journal-title":"Comput. J."},{"key":"239_CR3","doi-asserted-by":"publisher","first-page":"503","DOI":"10.1007\/BF01589116","volume":"45","author":"DC Liu","year":"1989","unstructured":"Liu, D.C., Nocedal, J.: On limited memory BFGS method for large scale optimization. Math. Program. 45, 503\u2013528 (1989)","journal-title":"Math. Program."},{"key":"239_CR4","doi-asserted-by":"publisher","first-page":"773","DOI":"10.1090\/S0025-5718-1980-0572855-7","volume":"35","author":"J Nocedal","year":"1980","unstructured":"Nocedal, J.: Updating quasi-Newton matrices with limited storage. Math. Comput. 35, 773\u2013782 (1980)","journal-title":"Math. Comput."},{"key":"239_CR5","first-page":"733","volume":"20","author":"SS Oren","year":"1974","unstructured":"Oren, S.S., Luenberger, D.G.: Self-scaling variable metric (SSVM) algorithms. Manage. Sci. 20, 733\u2013899 (1974)","journal-title":"Manage. Sci."},{"key":"239_CR6","first-page":"87","volume-title":"Numerical Methods for Nonlinear Equations","author":"MJD Powell","year":"1970","unstructured":"Powell, M.J.D.: A hybrid method for nonlinear equations. In: Rabinowitz, P. (ed.) Numerical Methods for Nonlinear Equations, pp. 87\u2013114. Gordon and Breach, London (1970)"},{"key":"239_CR7","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1093\/imamat\/7.1.21","volume":"7","author":"MJD Powell","year":"1971","unstructured":"Powell, M.J.D.: On the convergence of the variable metric algorithm. J. Inst. Maths. Appl. 7, 21\u201336 (1971)","journal-title":"J. Inst. Maths. Appl."},{"key":"239_CR8","first-page":"53","volume-title":"Nonlinear Programming SIAM-AMS Proceedings","author":"MJD Powell","year":"1976","unstructured":"Powell, M.J.D.: Some global convergence properties of a variable metric algorithm for minimization without exact line searches. In: Cottle, R.W., Lemke, C.E. (eds.) Nonlinear Programming SIAM-AMS Proceedings, vol. IX, pp. 53\u201372. American Mathematical Society, Providence (1976)"},{"key":"239_CR9","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1007\/BF02591941","volume":"27","author":"MJD Powell","year":"1983","unstructured":"Powell, M.J.D.: \u201cThe convergence of variable metric matrices in unconstrained optimization\u201d (with R-P. Ge). Math. Program. 27, 123\u2013143 (1983)","journal-title":"Math. Program."},{"key":"239_CR10","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1007\/BF01582161","volume":"34","author":"MJD Powell","year":"1986","unstructured":"Powell, M.J.D.: How bad are the BFGS and DFP methods when the objective function is quadratic? Math. Program. 34, 34\u201347 (1986)","journal-title":"Math. Program."},{"key":"239_CR11","unstructured":"Powell, M.J.D.: TOLMIN: a Fortran package for linearly constrained optimization calculations. Report DAMTP 1989\/NA2, University of Cambridge (1989)"},{"key":"239_CR12","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1007\/s101070050115","volume":"87","author":"MJD Powell","year":"2000","unstructured":"Powell, M.J.D.: \u201cOn the convergence of the DFP algorithm for unconstrained optimization when there are only two variables\u201d, in Studies in algorithmic optimization. Math. Program. 87, 281\u2013301 (2000)","journal-title":"Math. Program."},{"key":"239_CR13","unstructured":"Siegel, D.: Implementing and modifying Broyden class updates for large scale optimization. DAMTP-Report, University of Cambridge (1992)"},{"issue":"1993","key":"239_CR14","first-page":"45","volume":"66","author":"D Siegel","year":"1993","unstructured":"Siegel, D.: Modifying the BFGS update by a new column scaling technique. Math. Program. 66(1993), 45\u201378 (1993)","journal-title":"Math. Program."},{"key":"239_CR15","doi-asserted-by":"publisher","first-page":"226","DOI":"10.1137\/1011036","volume":"11","author":"P Wolfe","year":"1969","unstructured":"Wolfe, P.: Convergence conditions for ascent methods. SIAM Rev. 11, 226\u2013235 (1969)","journal-title":"SIAM Rev."}],"container-title":["Computational Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-020-00239-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10589-020-00239-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-020-00239-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,1,11]],"date-time":"2021-01-11T13:44:56Z","timestamp":1610372696000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10589-020-00239-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,11,9]]},"references-count":15,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["239"],"URL":"https:\/\/doi.org\/10.1007\/s10589-020-00239-2","relation":{},"ISSN":["0926-6003","1573-2894"],"issn-type":[{"type":"print","value":"0926-6003"},{"type":"electronic","value":"1573-2894"}],"subject":[],"published":{"date-parts":[[2020,11,9]]},"assertion":[{"value":"3 December 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 October 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 November 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}