zbMATH — the first resource for mathematics

On the convergence of interior-reflective Newton methods for nonlinear minimization subject to bounds. (English) Zbl 0842.90106
The authors analyze a new affine-scaling interior-point method for the minimization of a nonlinear function \(f\) subject to simple bounds on the variables. Unlike the Dikin-Karmarker scaling matrix, the scaling matrix \(D(x)\) used in this paper is generated using the distance of the iterates to the bounds and the direction of the gradient. Components of the variables are only scaled by the square root of their distance to the bound if the corresponding component of the negative gradient points to that bound. Using this scaling matrix \(D(x)\), the first order necessary conditions can be written as \(D(x) \nabla f(x) = 0\). Search directions are computed using a modified Newton method applied to \(D(x) \nabla f(x) = 0\). To improve global convergence, in particular to avoid short steps generated because some variables may approach the wrong bounds, reflections of the Newton steps at the bounds are used. Global convergence and local \(q\)-quadratic convergence of this method is proven.

90C30 Nonlinear programming
Full Text: DOI
[1] L. Armijo, ”Minimization of functions having Lipschitz continuous first partial derivatives,”Pacific Journal of Mathematics 16 (1966) 1–3. · Zbl 0202.46105
[2] A.A. Björck, ”A direct method for sparse least squares problem with lower and upper bounds,”Numerische Mathematik 54 (1988) 19–32. · Zbl 0659.65039 · doi:10.1007/BF01403888
[3] 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. · Zbl 0652.90082 · doi:10.1007/BF01580735
[4] 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. · Zbl 0689.65039 · doi:10.1137/0911012
[5] 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. · Zbl 0691.90070 · doi:10.1007/BF01589112
[6] 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. · Zbl 0778.90051 · doi:10.1137/0803014
[7] 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). · Zbl 0726.90057
[8] T.F. Coleman and Y. Li, ”A global and quadratically-convergent method for linearl problems,”SIAM Journal on Numerical Analysis 29 (1992) 1166–1186. · Zbl 0756.65087 · doi:10.1137/0729071
[9] 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. · Zbl 0760.90069 · doi:10.1007/BF01580899
[10] 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).
[11] 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. · Zbl 0645.65033 · doi:10.1090/S0025-5718-1988-0929544-3
[12] 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).
[13] I. Dikin, ”Iterative solution of problems of linear and quadratic programming,”Doklady Akademiia Nauk SSSR 174 (1967) 747–748. · Zbl 0189.19504
[14] 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. · Zbl 0301.90032 · doi:10.1093/imamat/14.2.159
[15] P. Gill and W. Murray, ”Minimization subject to bounds on the variables,” Technical Report NAC-71, National Physical Laboratory (England, 1976). · Zbl 0345.65020
[16] D. Goldfarb, ”Curvilinear path steplength algorithms for minimization algorithms which use directions of negative curvature,”Mathematical Programming 18 (1980) 31–40. · Zbl 0428.90068 · doi:10.1007/BF01588294
[17] A. Goldstein, ”On steepest descent,”SIAM Journal on Control 3 (1965) 147–151. · Zbl 0221.65094
[18] 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).
[19] Y. Li, ”A globally convergent method forl p problems,”SIAM Journal on Optimization 3 (1993) 609–629. · Zbl 0780.65033 · doi:10.1137/0803030
[20] P. Lotstedt, ”Solving the minimal least squares problem subject to bounds on the variables,”BIT 24 (1984) 206–224. · Zbl 0546.65041
[21] J.J. Moré and G. Toraldo, ”Algorithms for bound constrained quadratic programming problems,”Numerische Mathematik 55 (1989) 377–400. · Zbl 0675.65061 · doi:10.1007/BF01396045
[22] 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. · Zbl 0464.65039 · doi:10.1016/0024-3795(80)90173-1
[23] U. Öreborn, ”A direct method for sparse nonnegative least squares problems,” Ph. D. Thesis, Linköping University (Linköping, Sweden, 1986).
[24] J.M. Ortega and W. Rheinboldt, ”Iterative Solution of Nonlinear Equations in Several Variables” (Academic Press, New York, 1970). · Zbl 0241.65046
[25] 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. · Zbl 0574.65061 · doi:10.1137/0722003
[26] D. Sorensen, ”Trust region methods for unconstrained optimization,”SIAM Journal on Numerical Analysis 19 (1982) 409–426. · Zbl 0483.65039 · doi:10.1137/0719026
[27] 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. · Zbl 0683.90044
[28] R.J. Vanderbei, M.S. Meketon and B.A. Freedman, ”A modification of Karmarkar’s linear programming algorithm,”Algorithmica 1 (1986) 395–407. · Zbl 0626.90056 · doi:10.1007/BF01840454
[29] 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. · Zbl 0737.90046 · doi:10.1007/BF01586934
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.