Abstract
A new algorithm for solving smooth large-scale minimization problems with bound constraints is introduced. The way of dealing with active constraints is similar to the one used in some recently introduced quadratic solvers. A limited-memory multipoint symmetric secant method for approximating the Hessian is presented. Positive-definiteness of the Hessian approximation is not enforced. A combination of trust-region and conjugate-gradient approaches is used to explore useful information. Global convergence is proved for a general model algorithm. Results of numerical experiments are presented.
Similar content being viewed by others
References
R. Andreani, A. Friedlander and J.M. Martínez, On the solution of finite-dimensional variational inequalities using smooth optimization with simple bounds, Journal on Optimization Theory and Applications 94 (1997) 635–657.
R. Andreani and J.M. Martínez, On the solution of the extended linear complementarity problem, Linear gebra and its Applications 281 (1998) 247–257.
R. Andreani and J.M. Martínez, On the reformulation of nonlinear complementarity problems using the Fischer-Burmeister function, Applied Mathematics Letters 12 (1999) 7–12.
R. Andreani and J.M. Martínez, Reformulation of variational inequalities on a simplex and the compactification of complementarity problems, SIAM Journal on Optimization 10 (2000) 878–895.
R. Bielschowsky, A. Friedlander, F.A.M. Gomes, J.M. Martínez and M. Raydan, An adaptive algorithm for bound constrained quadratic minimization, Investigación Operativa 7 (1998) 67–102.
A.G. Biryukov, On the difference-approximation approach to the solution of systems of nonlinear equations, Soviet Mathematics. Doklady 17 (1983) 660–664.
A. Bjorck, Numerical Methods for Least-Squares Problems (SIAM, Philadelphia, 1996).
I. Bongartz, A.R. Conn, N.I.M. Gould and Ph.L. Toint, CUTE: constrained and unconstrained testing environment, ACM Transactions on Mathematical Software 21 (1995) 123–160.
O.P. Burdakov, Methods of secant type for systems of equations with symmetric Jacobian matrix, Numerical Functional Analysis and Optimization 6 (1983) 183–195.
O.P. Burdakov, Stable versions of the secant method for solving systems of equations, USSR Computational Mathematics and Mathematical Physics 23 (1983) 1–10.
O.P. Burdakov, On superlinear convergence of some stable variants of the secant method, ZAMM 66 (1986) 615–622.
O.P. Burdakov, Stable symmetric secant methods with restarts, Cybernetics 27 (1991) 390–396.
R.H. Byrd, P. Lu, J. Nocedal and C. Zhu, A limited memory algorithm for bound constrained minimization, SIAM Journal on Scientific Computing 16 (1995) 1190–1208.
R.H. Byrd, J. Nocedal and R.B. Schnabel, Representations of quasi-Newton matrices and their use in limited memory methods, Mathematical Programming 63 (1994) 129–156.
P.H. Calamai and J.J. Moré, Projected gradient methods for linearly constrained problems, Mathematical Programming 39 (1987) 93–116.
A.R. Conn, N.I.M. Gould and Ph.L. Toint, Global convergence of a class of trust region algorithms for optimization with simple bounds, SIAM Journal on Numerical Analysis 25 (1988) 433–460.
A.R. Conn, N.I.M. Gould and Ph.L. Toint, A globally convergent augmented Lagrangian algorithm for optimization with general constraints and simple bounds, SIAM Journal on Numerical Analysis 28 (1991) 545–572.
A.R. Conn, N.I.M. Gould and Ph.L. Toint, LANCELOT: a Fortran Package for Large-Scale Nonlinear Optimization (Release A) (Springer, Berlin, 1992).
A.R. Conn, N.I.M. Gould and Ph.L. Toint, Trust-Region Methods (SIAM-MPS, 2000).
A. Dax, A modified Gram-Schmidt algorithm with iterative orthogonalization and column pivoting, Linear Algebra and its Applications 310 (2000) 25–42.
R.S. Dembo, S.C. Eisenstat and T. Steihaug, Inexact Newton methods, SIAM Journal on Numerical Analysis 19 (1982) 400–408.
J.E. Dennis and R.B. Schnabel, Numerical Methods for Unconstrained Optimization and Nonlinear Equations (Prentice-Hall, New York, 1983).
Z. Dostál, Box constrained quadratic programming with proportioning and projections, SIAMJournal on Optimization 7 (1997) 871–887.
Z. Dostál, A. Friedlander and S.A. Santos, Solution of contact problems using subroutine BOXQUACAN, Investigación Operativa 7 (1997) 13–22.
Z. Dostál, A. Friedlander and S.A. Santos, Analysis of block structures by augmented Lagrangians with adaptive precision control, in: Proceedings of GEOMECHANICS '96, ed. Z. Rakowski (A.A. Balkema, Rotterdam, 1997) pp. 175–180.
Z. Dostál, A. Friedlander and S.A. Santos, Solution of coercive and semicoercive contact problems by FETI domain decomposition, in: The Tenth International Conference on Domain Decomposition Methods, Boulder, CO, Contemporary Mathematics, Vol. 218, eds. J. Mandel, C. Farhat and X. Cai (1998) pp. 82–93.
Z. Dostál, A. Friedlander and S.A. Santos, Augmented Lagrangians with adaptive precision control for quadratic programming with equality constraints, Computational Optimization and Applications 14 (1999) 1–17.
Z. Dostál, A. Friedlander, S.A. Santos and J. Malík, Analysis of semicoercive contact problems using symmetric BEM and augmented Lagrangians, Engineering Analysis with Boundary Elements 18 (1997) 195–201.
Z. Dostál, F.A.M. Gomes and S.A. Santos, Duality-based domain decomposition with natural coarsespace for variational inequalities, Journal of Computational and Applied Mathematics 126 (2000) 397–415.
J. Facchinei, J. Júdice and J. Soares, An active set Newton algorithm for large scale nonlinear programs with box constraints, SIAM Journal on Optimization 8 (1998) 158–186.
A. Friedlander and J.M. Martínez, On the numerical solution of bound constrained optimization problems, RAIRO Operations Research 23 (1989) 319–341.
A. Friedlander and J.M. Martínez, New algorithms for maximization of concave functions with box constraints, RAIRO Operations Research 26 (1992) 209–236.
A. Friedlander and J.M. Martínez, On the maximization of a concave quadratic function with box constraints, SIAM Journal on Optimization 4 (1994) 177–192.
A. Friedlander, J.M. Martínez and S.A. Santos, A new trust region algorithm for bound constrained minimization, Applied Mathematics and Optimization 30 (1994) 235–266.
P.E. Gill and M.W. Leonard, Reduced-Hessian quasi-Newton methods for unconstrained optimization, SIAM Journal on Optimization 12 (2001) 209–237.
G.H. Golub and C.F. Van Loan, Matrix Computations (Johns Hopkins University Press, 1989).
N. Krejić, J.M. Martínez, M.P. Mello and E.A. Pilotta, Validation of an augmented Lagrangian algorithm with a Gauss-Newton Hessian approximation using a set of hard-spheres problems, Computational Optimization and Applications 16 (2000) 247–263.
C.J. Lin and J.J. Moré, Newton's method for large bound-constrained optimization problems, SIAM Journal on Optimization 9 (1999) 1100–1127.
J.M. Martínez, Three new algorithms based on the sequential secant method, BIT 19 (1979) 236–243.
J.M. Martínez, E.A. Pilotta and M. Raydan, Spectral gradient method for linearly constrained optimization, Technical Report 22/99, IMECC, University of Campinas (UNICAMP), Campinas, Brazil (1999).
J.J. Moré and D.J. Thuente, Line search algorithms with guaranteed sufficient decrease, ACM Transactions on Mathematical Software 20 (1994) 286–307.
J.M. Ortega and W. Rheinboldt, Iterative Solution of Nonlinear Equations in Several Variables (Academic Press, New York, 1970).
M. Raydan, On the Barzilai and Borwein choice of steplength for the gradient method, SIAM Journal on Optimization 7 (1993) 26–33.
R.B. Schnabel, Quasi-Newton methods using multiple secant equations, Technical Report CU-CS-247–83, Department of Computer Science, University of Colorado, Boulder, CO (1983).
T. Steihaug, The conjugate gradient method and trust regions in large scale optimization, SIAM Journal on Numerical Analysis 20 (1983) 626–637.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Burdakov, O.P., Martínez, J.M. & Pilotta, E.A. A Limited-Memory Multipoint Symmetric Secant Method for Bound Constrained Optimization. Annals of Operations Research 117, 51–70 (2002). https://doi.org/10.1023/A:1021561204463
Issue Date:
DOI: https://doi.org/10.1023/A:1021561204463