Article
Full entry |
PDF
(0.4 MB)
Feedback
PDF
(0.4 MB)
Feedback
Keywords:
quadratic programming; conjugate gradients; active set methods
quadratic programming; conjugate gradients; active set methods
Summary:
An algorithm for quadratic minimization with simple bounds is introduced, combining, as many well-known methods do, active set strategies and projection steps. The novelty is that here the criterion for acceptance of a projected trial point is weaker than the usual ones, which are based on monotone decrease of the objective function. It is proved that convergence follows as in the monotone case. Numerical experiments with bound-constrained quadratic problems from CUTE collection show that the modified method is in practice slightly more efficient than its monotone counterpart and has a performance superior to the well-known code LANCELOT for this class of problems.
References:
[1] D. P. Bertsekas: Projected Newton methods for optimization problems with simple constraints. SIAM J. Control Optim. 20 (1982), 141–148. DOI 10.1137/0320018 | MR 0646950 | Zbl 0507.49018
[2] R. H. Bielschowsky, A. Friedlander, F. A. M. Gomes, J. M. Martínez and M. Raydan: An adaptive algorithm for bound constrained quadratic minimization. Investigación Oper. 7 (1997), 67–102.
[3] I. Bongartz, A. R. Conn, N. I. M. Gould and Ph. L. Toint: CUTE: Constrained and Unconstrained Testing Environment. ACM Trans. Math. Software 21 (1995), 123–160. DOI 10.1145/200979.201043
[4] P. Ciarlet: The Finite Element Method for Elliptic Problems. North Holland, Amsterdam, 1978. MR 0520174 | Zbl 0383.65058
[5] T. F. Coleman, L. A. Hulbert: A direct active set algorithm for large sparse quadratic programs with simple bounds. Math. Programming 45 (1989), 373–406. DOI 10.1007/BF01589112 | MR 1038241
[6] 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), 433-460. DOI 10.1137/0725029 | MR 0933734
[7] 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 J. Numer. Anal. 28 (1988), 545–572. MR 1087519
[8] R. Dembo, U. Tulowitzki: On the minimization of quadratic functions subject to box constraints. Working Paper B-71, School of Organization and Management, Yale University, New Haven (1983).
[9] J. E. Dennis, L. N. Vicente: Trust-region interior-point algorithms for minimization problems with simple bounds. In: Applied Mathematics and Parallel Computing (Festschrift for Klaus Ritter) (H. Fischer, B. Riedmüller and S. Schäffer, eds.), Physica-Verlag, Springer-Verlag, 1996, pp. 97–107. MR 1469263
[10] M. A. Diniz-Ehrhardt, M. A. Gomes-Ruggiero and S. A. Santos: Comparing the numerical performance of two trust-region algorithms for large-scale bound-constrained minimization. Investigación Oper. 7 (1997), 23–54.
[11] M. A. Diniz-Ehrhardt, M. A. Gomes-Ruggiero and S. A. Santos: Numerical analysis of leaving-face parameters in bound-constrained quadratic minimization. Relatório de Pesquisa RP52/98, IMECC, UNICAMP, Campinas, Brazil, 1998.
[12] Z. Dostál: Box constrained quadratic programming with proportioning and projections. SIAM J. Optim. 7 (1997), 871–887. DOI 10.1137/S1052623494266250 | MR 1462070
[13] Z. Dostál, A. Friedlander and S. A. Santos: Solution of contact problems of elasticity by FETI domain decomposition. Contemp. Math. 218 (1998), 82–93. DOI 10.1090/conm/218/03003 | MR 1645845
[14] Z. Dostál, F. A. M. Gomes Neto and S. A. Santos: Solution of contact problems by FETI domain decomposition with natural coarse space projection. Comput. Methods Appl. Mech. Engrg. 190 (2000), 1611–1627. DOI 10.1016/S0045-7825(00)00180-8
[15] Z. Dostál, V. Vondrák: Duality based solution of contact problems with Coulomb friction. Arch. Mech. 49 (1997), 453–460. MR 1468556
[16] L. Fernandes, A. Fischer, J. J. Júdice, C. Requejo and C. Soares: A block active set algorithm for large-scale quadratic programming with box constraints. Ann. Oper. Res. 81 (1998), 75–95. DOI 10.1023/A:1018990014974 | MR 1638391
[17] A. Friedlander, J. M. Martínez: On the numerical solution of bound constrained optimization problems. RAIRO Rech. Opér. 23 (1989), 319–341. DOI 10.1051/ro/1989230403191 | MR 1036699
[18] A. Friedlander, J. M. Martínez: On the maximization of a concave quadratic function with box constraints. SIAM J. Optim. 4 (1994), 177–192. DOI 10.1137/0804010 | MR 1260414
[19] A. Friedlander, J. M. Martínez and M. Raydan: A new method for large-scale box constrained quadratic minimization problems. Optimization Methods and Software 5 (1995), 57–74. DOI 10.1080/10556789508805602
[20] A. Friedlander, J. M. Martínez and S. A. Santos: A new trust region algorithm for bound constrained minimization. Appl. Math. Optim. 30 (1994), 235–266. DOI 10.1007/BF01183013 | MR 1288591
[21] P. E. Gill, W. Murray and M. H. Wright: Practical Optimization. Academic Press, London and New York, 1981. MR 0634376
[22] G. H. Golub, Ch. F. Van Loan: Matrix Computations. The Johns Hopkins University Press, Baltimore and London, 1989. MR 1002570
[23] M. R. Hestenes, E. Stiefel: Methods of conjugate gradients for solving linear systems. J. Res. NBS B 49 (1952), 409–436. MR 0060307
[24] J. J. Júdice, F. M. Pires: Direct methods for convex quadratic programming subject to box constraints. Investigação Operacional 9 (1989), 23–56.
[25] Y. Lin, C. W. Cryer: An alternating direction implicit algorithm for the solution of linear complementarity problems arising from free boundary problems. Appl. Math. Optim. 13 (1985), 1–17. DOI 10.1007/BF01442196 | MR 0778418
[26] P. Lötstedt: Numerical simulation of time-dependent contact and friction problems in rigid body mechanics. SIAM J. Sci. Comput. 5 (1984), 370–393. DOI 10.1137/0905028 | MR 0740855
[27] P. Lötstedt: Solving the minimal least squares problem subject to bounds on the variables. BIT 24 (1984), 206–224. MR 0753549
[28] J. J. Moré, G. Toraldo: On the solution of large quadratic programming problems with bound constraints. SIAM J. Optim. 1 (1991), 93–113. DOI 10.1137/0801008 | MR 1094793
[29] R. H. Nickel, J. W. Tolle: A sparse sequential programming algorithm. J. Optim. Theory Appl. 60 (1989), 453–473. DOI 10.1007/BF00940348 | MR 0993010
[30] M. Raydan: On the Barzilai and Borwein choice of steplength for the gradient method. IMA J. Numer. Anal. 13 (1993), 321–326. DOI 10.1093/imanum/13.3.321 | MR 1225468 | Zbl 0778.65045
[31] E. K. Yang, J. W. Tolle: A class of methods for solving large, convex quadratic programs subject to box constraints. Tech. Rep. UNC/ORSA/TR-86-3, Dept. of Oper. Research and Systems Analysis, Univ. of North Carolina, Chapel Hill, NC. (1986).
Search
Partner of
