Testing a class of methods for solving minimization problems with simple bounds on the variables
Authors:
Andrew R. Conn, Nicholas I. M. Gould and Philippe L. Toint
Journal:
Math. Comp. 50 (1988), 399430
MSC:
Primary 65K05; Secondary 90C30
MathSciNet review:
929544
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: We describe the results of a series of tests for a class of new methods of trust region type for solving the simple bound constrained minimization problem. The results are encouraging and lead us to believe that the methods will prove useful in solving largescale problems.
 [1]
Dimitri
P. Bertsekas, Constrained optimization and Lagrange multiplier
methods, Computer Science and Applied Mathematics, Academic Press,
Inc. [Harcourt Brace Jovanovich, Publishers], New YorkLondon, 1982. MR 690767
(84k:90068)
 [2]
R.
K. Brayton and J.
Cullum, An algorithm for minimizing a differentiable function
subject to box constraints and errors, J. Optim. Theory Appl.
29 (1979), no. 4, 521–558. MR 552105
(81f:90087), http://dx.doi.org/10.1007/BF00934451
 [3]
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 J. Numer. Anal.
25 (1988), no. 2, 433–460. MR 933734
(89h:90192), http://dx.doi.org/10.1137/0725029
 [4]
E.
E. Cragg and A.
V. Levy, Study on a supermemory gradient method for the
minimization of functions, J. Optimization Theory Appl.
4 (1969), 191–205. MR 0248967
(40 #2217)
 [5]
J.
Cullum and R.
K. Brayton, Some remarks on the symmetric rankone update, J.
Optim. Theory Appl. 29 (1979), no. 4, 493–519.
MR 552104
(81f:90088), http://dx.doi.org/10.1007/BF00934450
 [6]
Ron
S. Dembo, Stanley
C. Eisenstat, and Trond
Steihaug, Inexact Newton methods, SIAM J. Numer. Anal.
19 (1982), no. 2, 400–408. MR 650059
(83b:65056), http://dx.doi.org/10.1137/0719025
 [7]
R. S. Dembo & U. Tulowitzki, On the Minimization of Quadratic Functions Subject to Box Constraints, Working paper series B 71, School of Organization and Management, Yale University, 1983.
 [8]
John
E. Dennis Jr. and Robert
B. Schnabel, Numerical methods for unconstrained optimization and
nonlinear equations, Prentice Hall Series in Computational
Mathematics, Prentice Hall, Inc., Englewood Cliffs, NJ, 1983. MR 702023
(85j:65001)
 [9]
R.
Fletcher, Practical methods of optimization. Vol. 1, John
Wiley & Sons, Ltd., Chichester, 1980. Unconstrained optimization; A
WileyInterscience Publication. MR 585160
(83i:65055a)
 [10]
R.
Fletcher and M.
P. Jackson, Minimization of a quadratic function of many variables
subject only to lower and upper bounds, J. Inst. Math. Appl.
14 (1974), 159–174. MR 0384156
(52 #5033)
 [11]
U.
M. GarcíaPalomares, Superlinearly convergent algorithms for
linearly constrained optimization problems, Nonlinear programming, 2
(Proc. Sympos. Special Interest Group on Math. Programming, Univ.
Wisconsin, Madison, Wis., 1974) Academic Press, New York, 1974,
pp. 101–119. MR 0406522
(53 #10309)
 [12]
P. E. Gill & W. Murray, Minimization Subject to Bounds on the Variables, report NAC 71, National Physical Laboratory, England, 1976.
 [13]
P. E. Gill, W. Murray, M. A. Saunders & M. H. Wright, Some Theoretical Properties of an Augmented Lagrangian Function, Technical Report SOL 866, Department of Operations Research, Stanford University, 1986.
 [14]
Philip
E. Gill, Walter
Murray, and Margaret
H. Wright, Practical optimization, Academic Press, Inc.
[Harcourt Brace Jovanovich, Publishers], LondonNew York, 1981. MR 634376
(83d:65195)
 [15]
A.
Griewank and Ph.
L. Toint, On the unconstrained optimization of partially separable
functions, Nonlinear optimization, 1981 (Cambridge, 1981) NATO Conf.
Ser. II: Systems Sci., Academic Press, London, 1982,
pp. 301–312. MR
775354
 [16]
A.
Griewank and Ph.
L. Toint, Partitioned variable metric updates for large structured
optimization problems, Numer. Math. 39 (1982),
no. 1, 119–137. MR 664541
(83k:65054), http://dx.doi.org/10.1007/BF01399316
 [17]
Willi
Hock and Klaus
Schittkowski, Test examples for nonlinear programming codes,
Lecture Notes in Economics and Mathematical Systems, vol. 187,
SpringerVerlag, BerlinNew York, 1981. MR 611512
(82f:90084)
 [18]
J.
J. Moré, Recent developments in algorithms and software for
trust region methods, Mathematical programming: the state of the art
(Bonn, 1982) Springer, Berlin, 1983, pp. 258–287. MR 717404
(85b:90066)
 [19]
Jorge
J. Moré, Burton
S. Garbow, and Kenneth
E. Hillstrom, Testing unconstrained optimization software, ACM
Trans. Math. Software 7 (1981), no. 1, 17–41.
MR 607350
(83b:90144), http://dx.doi.org/10.1145/355934.355936
 [20]
J.
L. Nazareth, Analogues of Dixon’s and Powell’s theorems
for unconstrained minimization with inexact line searches, SIAM J.
Numer. Anal. 23 (1986), no. 1, 170–177. MR 821913
(87h:90206), http://dx.doi.org/10.1137/0723012
 [21]
Dianne
Prost O’Leary, A generalized conjugate gradient algorithm for
solving a class of quadratic programming problems, Linear Algebra
Appl. 34 (1980), 371–399. MR 591439
(82e:90076), http://dx.doi.org/10.1016/00243795(80)901731
 [22]
M.
J. D. Powell, A new algorithm for unconstrained optimization,
Nonlinear Programming (Proc. Sympos., Univ. of Wisconsin, Madison, Wis.,
1970) Academic Press, New York, 1970, pp. 31–65. MR 0272162
(42 #7043)
 [23]
M.
J. D. Powell, Some global convergence properties of a variable
metric algorithm for minimization without exact line searches,
Nonlinear programming (Proc. Sympos., New York, 1975) Amer. Math. Soc.,
Providence, R. I., 1976, pp. 53–72. SIAMAMS Proc., Vol. IX. MR 0426428
(54 #14371)
 [24]
M.
J. D. Powell, How bad are the BFGS and DFP methods when the
objective function is quadratic?, Math. Programming
34 (1986), no. 1, 34–47. MR 819873
(87c:90197), http://dx.doi.org/10.1007/BF01582161
 [25]
D.
F. Shanno and Kang
Hoh Phua, Matrix conditioning and nonlinear optimization,
Math. Programming 14 (1978), no. 2, 149–160. MR 0474819
(57 #14450)
 [26]
D. C. Sorensen, "An example concerning quasiNewton estimation of a sparse Hessian," SIGNUM Newsletter, v. 16, 1981, pp. 810.
 [27]
Trond
Steihaug, The conjugate gradient method and trust regions in large
scale optimization, SIAM J. Numer. Anal. 20 (1983),
no. 3, 626–637. MR 701102
(84g:49047), http://dx.doi.org/10.1137/0720042
 [28]
Ph.
L. Toint, Some numerical results using a sparse
matrix updating formula in unconstrained optimization, Math. Comp. 32 (1978), no. 143, 839–851. MR 0483452
(58 #3453), http://dx.doi.org/10.1090/S00255718197804834527
 [29]
Ph. L. Toint, "Towards an efficient sparsity exploiting Newton method for minimization," in Sparse Matrices and Their Uses (I. S. Duff, ed.), Academic Press, London and New York, 1981.
 [1]
 D. P. Bertsekas, Constrained Optimization and Lagrange Multiplier Methods, Academic Press, London and New York, 1982. MR 690767 (84k:90068)
 [2]
 R. K. Brayton & J. Cullum, "An algorithm for minimizing a differentiable function subject to box constraints and errors," J. Optim. Theory Appl., v. 29, 1979, pp. 521558. MR 552105 (81f:90087)
 [3]
 A. R. Conn, N. I. M. Gould & Ph. L. Toint, "Global convergence of a class of trust region algorithms for optimization with simple bounds," SIAM J. Numer. Anal., v. 25, 1988, pp. 433460. MR 933734 (89h:90192)
 [4]
 E. E. Cragg & A. V. Levy, "Study on a supermemory gradient method for the minimization of functions," J. Optim. Theory Appl., v. 4, 1969, pp. 191205. MR 0248967 (40:2217)
 [5]
 J. Cullum & R. K. Brayton, "Some remarks on the symmetric rankone update," J. Optim. Theory Appl., v. 29, 1979, pp. 493520. MR 552104 (81f:90088)
 [6]
 R. S. Dembo, S. C. Eisenstat & T. Steihaug, "Inexact Newton methods," SIAM J. Numer. Anal., v. 19, 1982, pp. 400408. MR 650059 (83b:65056)
 [7]
 R. S. Dembo & U. Tulowitzki, On the Minimization of Quadratic Functions Subject to Box Constraints, Working paper series B 71, School of Organization and Management, Yale University, 1983.
 [8]
 J. E. Dennis & R. B. Schnabel, Numerical Methods for Unconstrained Optimization and Nonlinear Equations, PrenticeHall, Englewood Ciffs, N.J., 1983. MR 702023 (85j:65001)
 [9]
 R. Fletcher, Practical Methods of Optimization, Vol. 1, Wiley, Chichester and New York, 1980. MR 585160 (83i:65055a)
 [10]
 R. Fletcher & M. P. Jackson, "Minimization of a quadratic function of many variables subject only to lower and upper bounds," J. Inst. Math. Appl., v. 14, 1974, pp. 159174. MR 0384156 (52:5033)
 [11]
 U. M. GarciaPalomares, "Superlinearly convergent algorithms for linearly constrained optimization," in Nonlinear Programming 2 (O. L. Mangasarian, R. R. Meyer and S. M. Robinson, eds.), Academic Press, London and New York, 1975, pp. 101119. MR 0406522 (53:10309)
 [12]
 P. E. Gill & W. Murray, Minimization Subject to Bounds on the Variables, report NAC 71, National Physical Laboratory, England, 1976.
 [13]
 P. E. Gill, W. Murray, M. A. Saunders & M. H. Wright, Some Theoretical Properties of an Augmented Lagrangian Function, Technical Report SOL 866, Department of Operations Research, Stanford University, 1986.
 [14]
 P. E. Gill, W. Murray & M. H. Wright, Practical Optimization, Academic Press, London and New York, 1981. MR 634376 (83d:65195)
 [15]
 A. Griewank & Ph. L. Toint, "On the unconstrained optimization of partially separable functions," in Nonlinear Optimization, 1981 (M. J. D. Powell, ed.), Academic Press, London and New York, 1982, pp. 301312. MR 775354
 [16]
 A. Griewank & Ph. L. Toint, "Partitioned variable metric updates for large structured optimization problems," Numer. Math., v. 39, 1982, pp. 119137. MR 664541 (83k:65054)
 [17]
 W. Hock & K. Schittkowski, Test Examples for Nonlinear Programming Codes, Lecture Notes in Economics and Mathematical Systems 187, SpringerVerlag, Berlin, 1981. MR 611512 (82f:90084)
 [18]
 J. J. Moré, "Recent developments in algorithms and software for trust region methods," Mathematical Programming, The State of the Art, Bonn 1982 (A. Bachem, M. Grötschel and B. Korte, eds.), SpringerVerlag, Berlin, 1983, pp. 258287. MR 717404 (85b:90066)
 [19]
 J. J. Moré, B. S. Garbow & K. E. Hillstrom, "Testing unconstrained optimization software," ACM Trans. Math. Software, v. 7, 1981, pp. 1741. MR 607350 (83b:90144)
 [20]
 J. L. Nazareth, "Analogues of Dixon's and Powell's theorems for unconstrained minimization with inexact line searches," SIAM J. Numer. Anal., v. 23, 1986, pp. 170177. MR 821913 (87h:90206)
 [21]
 D. P. O'Leary, "A generalized conjugate gradient algorithm for solving a class of quadratic programming problems," Linear Algebra Appl., v. 34, 1980, pp. 371399. MR 591439 (82e:90076)
 [22]
 M. J. D. Powell, "A new algorithm for unconstrained optimization," in Nonlinear Programming (J. B. Rosen, O. L. Mangasarian and K. Ritter, eds.), Academic Press, London and New York, 1970, pp. 3165. MR 0272162 (42:7043)
 [23]
 M. J. D. Powell, Some Global Convergence Properties of a Variable Metric Algorithm for Minimization Without Exact Line Searches, SIAMAMS Proc., vol. 9, Amer. Math. Soc., Providence, R.I., 1976, pp. 5372. MR 0426428 (54:14371)
 [24]
 M. J. D. Powell, "How bad are the BFGS and DFP methods when the objective function is quadratic?," Math. Programming, v. 34, 1986, pp. 3447. MR 819873 (87c:90197)
 [25]
 D. F. Shanno & K. H. Phua, "Matrix conditioning and nonlinear optimization," Math. Programming, v. 14, 1978, pp. 145160. MR 0474819 (57:14450)
 [26]
 D. C. Sorensen, "An example concerning quasiNewton estimation of a sparse Hessian," SIGNUM Newsletter, v. 16, 1981, pp. 810.
 [27]
 T. Steihaug, "The conjugate gradient method and trust regions in large scale optimization," SIAM J. Numer. Anal., v. 20, 1983, pp. 626637. MR 701102 (84g:49047)
 [28]
 Ph. L. Toint, "Some numerical results using a sparse matrix updating formula in unconstrained optimization," Math. Comp., v. 32, 1978, pp. 839851. MR 0483452 (58:3453)
 [29]
 Ph. L. Toint, "Towards an efficient sparsity exploiting Newton method for minimization," in Sparse Matrices and Their Uses (I. S. Duff, ed.), Academic Press, London and New York, 1981.
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC:
65K05,
90C30
Retrieve articles in all journals
with MSC:
65K05,
90C30
Additional Information
DOI:
http://dx.doi.org/10.1090/S00255718198809295443
PII:
S 00255718(1988)09295443
Keywords:
Trust regions,
optimization with simple bounds,
numerical results
Article copyright:
© Copyright 1988
American Mathematical Society
