research-article

Algorithm 943: MSS: MATLAB Software for L-BFGS Trust-Region Subproblems for Large-Scale Optimization

Authors:

Jennifer B. Erway,

Roummel F. MarciaAuthors Info & Claims

ACM Transactions on Mathematical Software (TOMS), Volume 40, Issue 4

Article No.: 28, Pages 1 - 12

https://doi.org/10.1145/2616588

Published: 08 July 2014 Publication History

Abstract

A MATLAB implementation of the Moré-Sorensen sequential (MSS) method is presented. The MSS method computes the minimizer of a quadratic function defined by a limited-memory BFGS matrix subject to a two-norm trust-region constraint. This solver is an adaptation of the Moré-Sorensen direct method into an L-BFGS setting for large-scale optimization. The MSS method makes use of a recently proposed stable fast direct method for solving large shifted BFGS systems of equations [Erway and Marcia 2012; Erway et al. 2012] and is able to compute solutions to any user-defined accuracy. This MATLAB implementation is a matrix-free iterative method for large-scale optimization. Numerical experiments on the CUTEr [Bongartz et al. 1995; Gould et al. 2003]) suggest that using the MSS method as a trust-region subproblem solver can require significantly fewer function and gradient evaluations needed by a trust-region method as compared with the Steihaug-Toint method.

Supplementary Material

ZIP File (943.zip)

Software for MSS: MATLAB Software for L-BFGS Trust-Region Subproblems for Large-Scale Optimization

Download
7.34 KB

References

[1]

M. S. Apostolopoulou, D. G. Sotiropoulos, C. A. Botsaris, and P. E. Pintelas. 2011. A practical method for solving large-scale TRS. Optimiz. Lett. 5, 2, 207--227.

[2]

M. S. Apostolopoulou, D. G. Sotiropoulos, and P. Pintelas. 2008. Solving the quadratic trust-region subproblem in a low-memory BFGS framework. Optimiz. Meth. Softw. 23, 5, 651--674. org/10.1080/10556780802413579

Digital Library

[3]

I. Bongartz, A. R. Conn, N. I. M. Gould, and Philippe L. Toint. 1995. CUTE: Constrained and unconstrained testing environment. ACM Trans. Math. Softw. 21, 1, 123--160.

Digital Library

[4]

J. V. Burke, A. Wiegmann, and L. Xu. 2008. Limited Memory BFGS Updating in a Trust-Region Framework. Tech. Rep. Univ. Washington.

[5]

R. H. Byrd, J. Nocedal, and R. B. Schnabel. 1994. Representations of quasi-Newton matrices and their use in limited-memory methods. Math. Program. 63, 129--156.

Digital Library

[6]

A. R. Conn, N. I. M. Gould, and P. L. Toint. 2000. Trust-Region Methods. SIAM, Philadelphia, PA. xx+959 pages.

Digital Library

[7]

J. E. Dennis, Jr. and Robert B. Schnabel. 1996. Numerical Methods for Unconstrained Optimization and Nonlinear Equations. SIAM, Philadelphia, PA. xvi+378 pages. (Corrected reprint of the 1983 original).

Digital Library

[8]

J. E. Dennis, Jr. and H. H. Mei. 1979. Two new unconstrained optimization algorithms which use function and gradient values. J. Optim. Theory Appl. 28, 453--482.

Digital Library

[9]

E. D. Dolan and J. J. Moré. 2002. Benchmarking optimization software with performance profiles. Math. Program. 91, 2, Ser. A, 201--213.

[10]

J. B. Erway and P. E. Gill. 2009. A subspace minimization method for the trust-region step. SIAM J. Optimiz. 20, 3, 1439--1461.

Digital Library

[11]

J. B. Erway, P. E. Gill, and J. D. Griffin. 2009. Iterative methods for finding a trust-region step. SIAM J. Optim. 20, 2, 1110--1131.

Digital Library

[12]

J. B. Erway, V. Jain, and R. F. Marcia. 2012. Shifted L-BFGS systems. Tech. Rep. 2012-6. Wake Forest Univ.

[13]

J. B. Erway and R. F. Marcia. 2012. Limited-memory BFGS systems with diagonal updates. Linear Algebra Appl. 437, 1, 333--344.

[14]

D. M. Gay. 1981. Computing optimal locally constrained steps. SIAM J. Sci. Statist. Comput. 2, 2, 186--197.

Digital Library

[15]

N. I. M. Gould, S. Lucidi, M. Roma, and P. L. Toint. 1999. Solving the trust-region subproblem using the Lanczos method. SIAM J. Optim. 9, 2, 504--525.

Digital Library

[16]

N. I. M. Gould, D. Orban, and P. L. Toint. 2003. CUTEr and SifDec: A constrained and unconstrained testing environment, revisited. ACM Trans. Math. Softw. 29, 4, 373--394.

Digital Library

[17]

D. C. Liu and J. Nocedal. 1989. On the limited memory BFGS method for large scale optimization. Math. Program. 45, 503--528.

Digital Library

[18]

Z. Lu and R. D. C. Monteiro. 2007. A modified nearly exact method for solving low-rank trust region subproblem. Math. Program. 109, 2, 385--411.

Digital Library

[19]

J. J. Moré and D. C. Sorensen. 1983. Computing a trust region step. SIAM J. Sci. Statist. Comput. 4, 553--572.

Digital Library

[20]

J. Nocedal. 1980. Updating quasi-Newton matrices with limited storage. Math. Comput. 35, 773--782.

[21]

J. Nocedal and S. J. Wright. 2006. Numerical Optimization 2nd Ed. Springer-Verlag, New York.

[22]

M. J. D. Powell. 1970a. A Fortran subroutine for solving systems of nonlinear algebraic equations. In Numerical Methods for Nonlinear Algebraic Equations, P. Rabinowitz, Ed., Gordon and Breach Science Publishers, London, UK, 115--161.

[23]

M. J. D. Powell. 1970b. A hybrid method for nonlinear equations. In Numerical Methods for Nonlinear Algebraic Equations, P. Rabinowitz, Ed., Gordon and Breach Science Publishers, London, UK, 87--114.

[24]

D. C. Sorensen. 1982. Newton's method with a model trust region modification. SIAM J. Numer. Anal. 19, 2, 409--426.

Digital Library

[25]

Y.-X. Yuan. 2000. On the truncated conjugate gradient method. Math. Program. 87, 3, Ser. A, 561--573.

Cited By

Brust JErway JMarcia R(2024)Shape-changing trust-region methods using multipoint symmetric secant matricesOptimization Methods and Software10.1080/10556788.2023.2296441(1-18)Online publication date: 24-Jan-2024
https://doi.org/10.1080/10556788.2023.2296441
Quintana-Ortí GHernando FIgual F(2023)Algorithm 1033: Parallel Implementations for Computing the Minimum Distance of a Random Linear Code on Distributed-memory ArchitecturesACM Transactions on Mathematical Software10.1145/357338349:1(1-24)Online publication date: 21-Mar-2023
https://dl.acm.org/doi/10.1145/3573383
Demeure NChevalier CDenis CDossantos-Uzarralde P(2023)Algorithm 1029: Encapsulated Error, a Direct Approach to Evaluate Floating-Point AccuracyACM Transactions on Mathematical Software10.1145/354920548:4(1-16)Online publication date: 22-Mar-2023
https://dl.acm.org/doi/10.1145/3549205
Show More Cited By

Index Terms

Algorithm 943: MSS: MATLAB Software for L-BFGS Trust-Region Subproblems for Large-Scale Optimization
1. Mathematics of computing
  1. Mathematical software

Recommendations

Algorithm 1030: SC-SR1: MATLAB Software for Limited-memory SR1 Trust-region Methods
We present a MATLAB implementation of the symmetric rank-one (SC-SR1) method that solves trust-region subproblems when a limited-memory symmetric rank-one (L-SR1) matrix is used in place of the true Hessian matrix, which can be used for large-scale ...
A Subspace Minimization Method for the Trust-Region Step

We consider methods for large-scale unconstrained minimization based on finding an approximate minimizer of a quadratic function subject to a two-norm trust-region constraint. The Steihaug-Toint method uses the conjugate-gradient method to minimize the ...
On solving L-SR1 trust-region subproblems

In this article, we consider solvers for large-scale trust-region subproblems when the quadratic model is defined by a limited-memory symmetric rank-one (L-SR1) quasi-Newton matrix. We propose a solver that exploits the compact representation of L-SR1 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Mathematical Software

ACM Transactions on Mathematical Software Volume 40, Issue 4

June 2014

154 pages

ISSN:0098-3500

EISSN:1557-7295

DOI:10.1145/2639949

Editor:
Michael A. Heroux
Sandia National Laboratories

Issue’s Table of Contents

Copyright © 2014 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 08 July 2014

Accepted: 01 November 2013

Revised: 01 July 2013

Received: 01 December 2012

Published in TOMS Volume 40, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Badges

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Division of Civil, Mechanical and Manufacturing Innovation

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
486
Total Downloads

Downloads (Last 12 months)19
Downloads (Last 6 weeks)1

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Brust JErway JMarcia R(2024)Shape-changing trust-region methods using multipoint symmetric secant matricesOptimization Methods and Software10.1080/10556788.2023.2296441(1-18)Online publication date: 24-Jan-2024
https://doi.org/10.1080/10556788.2023.2296441
Quintana-Ortí GHernando FIgual F(2023)Algorithm 1033: Parallel Implementations for Computing the Minimum Distance of a Random Linear Code on Distributed-memory ArchitecturesACM Transactions on Mathematical Software10.1145/357338349:1(1-24)Online publication date: 21-Mar-2023
https://dl.acm.org/doi/10.1145/3573383
Demeure NChevalier CDenis CDossantos-Uzarralde P(2023)Algorithm 1029: Encapsulated Error, a Direct Approach to Evaluate Floating-Point AccuracyACM Transactions on Mathematical Software10.1145/354920548:4(1-16)Online publication date: 22-Mar-2023
https://dl.acm.org/doi/10.1145/3549205
Erway JRezapour M(2023)A new multipoint symmetric secant method with a dense initial matrixOptimization Methods and Software10.1080/10556788.2023.216799338:4(698-722)Online publication date: 6-Feb-2023
https://doi.org/10.1080/10556788.2023.2167993
Brust JBurdakov OErway JMarcia R(2022)Algorithm 1030: SC-SR1: MATLAB Software for Limited-memory SR1 Trust-region MethodsACM Transactions on Mathematical Software10.1145/355026948:4(1-33)Online publication date: 19-Dec-2022
https://dl.acm.org/doi/10.1145/3550269
Brust JMarcia RPetra C(2019)Large-scale quasi-Newton trust-region methods with low-dimensional linear equality constraintsComputational Optimization and Applications10.1007/s10589-019-00127-4Online publication date: 5-Sep-2019
https://doi.org/10.1007/s10589-019-00127-4
Brust JErway JMarcia R(2017)On solving L-SR1 trust-region subproblemsComputational Optimization and Applications10.1007/s10589-016-9868-366:2(245-266)Online publication date: 1-Mar-2017
https://dl.acm.org/doi/10.1007/s10589-016-9868-3
Burdakov OGong LZikrin SYuan Y(2016)On efficiently combining limited-memory and trust-region techniquesMathematical Programming Computation10.1007/s12532-016-0109-79:1(101-134)Online publication date: 27-Jun-2016
https://doi.org/10.1007/s12532-016-0109-7
Bates JShiozaki T(2015)Fully relativistic complete active space self-consistent field for large molecules: Quasi-second-order minimax optimizationThe Journal of Chemical Physics10.1063/1.4906344142:4Online publication date: 27-Jan-2015
https://doi.org/10.1063/1.4906344

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents