Abstract
We consider a new algorithm, an interior-reflective Newton approach, for the problem of minimizing a smooth nonlinear function of many variables, subject to upper and/or lower bounds on some of the variables. This approach generatesstrictly feasible iterates by using a new affine scaling transformation and following piecewise linear paths (reflection paths). The interior-reflective approach does not require identification of an “activity set”. In this paper we establish that the interior-reflective Newton approach is globally and quadratically convergent. Moreover, we develop a specific example of interior-reflective Newton methods which can be used for large-scale and sparse problems.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
L. Armijo, “Minimization of functions having Lipschitz continuous first partial derivatives,”Pacific Journal of Mathematics 16 (1966) 1–3.
A.A. Björck, “A direct method for sparse least squares problem with lower and upper bounds,”Numerische Mathematik 54 (1988) 19–32.
R.H. Byrd, R.B. Schnabel and G.A. Shultz, “Approximate solution of the trust region problem by minimization over two-dimensional subspaces,”Mathematical Programming 40 (1988) 247–264.
T.F. Coleman and C. Hempel, “Computing a trust region step for a penalty function,”SIAM Journal on Scientific and Statistical Computing 11 (1990) 180–201.
T.F. Coleman and L.A. Hulbert, “A direct active set algorithm for large sparse quadratic programs with simple bounds,”Mathematical Programming 45 (1989) 373–406.
T.F. Coleman and L.A. Hulbert, “A globally and superlinearly convergent algorithm for convex quadratic programs with simple bounds,”SIAM Journal on Optimization 3 (1993) 298–321.
T.F. Coleman and Y. Li, “A quadratically-convergent algorithm for the linear programming problem with lower and upper bounds,” in: T.F. Coleman and Y. Li, eds.,Large-scale Numerical Optimization. Proceedings of the Mathematical Sciences Institute Workshop, Cornell University (SIAM, Philadelphia, 1990).
T.F. Coleman and Y. Li, “A global and quadratically-convergent method for linearl ∞ problems,”SIAM Journal on Numerical Analysis 29 (1992) 1166–1186.
T.F. Coleman and Y. Li, “A globally and quadratically convergent affine scaling method for linearl 1 problems,”Mathematical Programming 56 Series A (1992) 189–222.
T.F. Coleman and Y. Li, “A reflective Newton method for minimizing a quadratic function subject to bounds on the variables,” Technical Report TR92-1315, Computer Science Department, Cornell University (Ithaca, NY, 1992).
A.R. Conn, N.I.M. Gould and P.L. Toint, “Testing a class of methods for solving minimization problems with simple bounds on the variables,”Mathematics of Computation 50 (1988) 399–430.
R.S. Dembo and U. Tulowitzki, “On the minimization of quadratic functions subject to box constraints,” Technical Report B-71. Yale University (New Haven, CT, 1983).
I. Dikin, “Iterative solution of problems of linear and quadratic programming,”Doklady Akademiia Nauk SSSR 174 (1967) 747–748.
R. Fletcher and M.P. Jackson, “Minimization of a quadratic function of many variables subject only to lower and upper bounds,”Journal of the Institute for Mathematics and its Applications 14 (1974) 159–174.
P. Gill and W. Murray, “Minimization subject to bounds on the variables,” Technical Report NAC-71, National Physical Laboratory (England, 1976).
D. Goldfarb, “Curvilinear path steplength algorithms for minimization algorithms which use directions of negative curvature,”Mathematical Programming 18 (1980) 31–40.
A. Goldstein, “On steepest descent,”SIAM Journal on Control 3 (1965) 147–151.
J.J. Júdice and F.M. Pires, “Direct methods for convex quadratic programs subject to box constraints,” Technical Report, Departamento de Matemática, Universidade de Coimbra (Portugal, 1989).
Y. Li, “A globally convergent method forl p problems,”SIAM Journal on Optimization 3 (1993) 609–629.
P. Lotstedt, “Solving the minimal least squares problem subject to bounds on the variables,”BIT 24 (1984) 206–224.
J.J. Moré and G. Toraldo, “Algorithms for bound constrained quadratic programming problems,”Numerische Mathematik 55 (1989) 377–400.
D.P. O'Leary, “A generalized conjugate gradient algorithm for solving a class of quadratic programming problems,”Linear Algebra and its Applications 34 (1980) 371–399.
U. Öreborn, “A direct method for sparse nonnegative least squares problems,” Ph. D. Thesis, Linköping University (Linköping, Sweden, 1986).
J.M. Ortega and W. Rheinboldt, “Iterative Solution of Nonlinear Equations in Several Variables” (Academic Press, New York, 1970).
G.A. Schultz, R.B. Schnabel and R.H. Byrd, “A family of trust-region-based algorithms for unconstrained minimization with strong global convergence properties,”SIAM Journal on Numerical Analysis 22 (1) (1985) 47–67.
D. Sorensen, “Trust region methods for unconstrained optimization,”SIAM Journal on Numerical Analysis 19 (1982) 409–426.
M.J. Todd, “Recent developments and new directions in linear programming,” in: M. Iri and K. Tanabe, eds.,Mathematical Programming: Recent Developments and Applications (Kluwer Academic Publishers, Dordrecht, 1989) pp. 109–157.
R.J. Vanderbei, M.S. Meketon and B.A. Freedman, “A modification of Karmarkar's linear programming algorithm,”Algorithmica 1 (1986) 395–407.
E.K. Yang and J.W. Tolle, “A class of methods for solving large convex quadratic programs subject to box constraints,”Mathematical Programming 51 (1991) 223–228.
Author information
Authors and Affiliations
Additional information
Research partially supported by the Applied Mathematical Sciences Research Program (KC-04-02) of the Office of Energy Research of the U.S. Department of Energy under grant DE-FG02-86ER25013.A000, and in part by NSF, AFOSR, and ONR through grant DMS-8920550, and by the Advanced Computing Research Institute, a unit of the Cornell Theory Center which receives major funding from the National Science Foundation and IBM Corporation, with additional support from New York State and members of its Corporate Research Institute.
Corresponding author.
Rights and permissions
About this article
Cite this article
Coleman, T.F., Li, Y. On the convergence of interior-reflective Newton methods for nonlinear minimization subject to bounds. Mathematical Programming 67, 189–224 (1994). https://doi.org/10.1007/BF01582221
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01582221